Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- (** Basic arithmetics with built-in integers *)
- open Builtin
- (* Greater common divisor and smaller common multiple
- implemetations.
- *)
- (** Greater common (positive) divisor of two non-zero integers.
- @param a non-zero integers
- @param b non-zero integer
- *)
- let rec gcd a b = if b = 0 then a else gcd b (modulo a b);;
- (* Extended Euclidean algorithm. Computing Bezout Coefficients. *)
- (** Extended euclidean division of two integers NOT OCAML DEFAULT.
- Given non-zero entries a b computes triple (u, v, d) such that
- a*u + b*v = d and d is gcd of a and b.
- @param a non-zero integer
- @param b non-zero integer.
- *)
- let rec bezout a b = if b = 0 then 1, 0, a else let (x, y, d) = bezout b (modulo a b) in (y, x - a/b*y, d);;
- let modinv a m = let (u, _, d) = bezout a m in if d <> 1 then invalid_arg "a and m not coprime" else modulo u m;;
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement