Anonymous user
Miller–Rabin primality test: Difference between revisions
Add OCaml implementation
(Realize in F#) |
(Add OCaml implementation) |
||
Line 3,549:
echo("\nnumber of primes < ",num, " are ", primes.len)
echo (epochTime()-te).formatFloat(ffDecimal, 6)
</lang>
=={{Header|OCaml}}==
A direct translation of the wikipedia pseudocode (with helper function translated from scheme implementation). This code uses the Zarith and Bigint (bignum) libraries.
<lang OCaml>
(* Translated from the wikipedia pseudo-code *)
let miller_rabin n ~iter:k =
(* return r and d where n = 2^r*d (from scheme implementation) *)
let get_rd n =
let rec loop r d =
if not (Z.equal Z.(d mod ~$2) Z.zero) then
(r,d)
else
loop Z.(r + one) Z.(div d ~$2)
in
loop Z.zero n
in
let single_miller n r d =
(* (random (n - 4)) + 2 *)
let a = Bigint.to_zarith_bigint
Bigint.((random ((of_zarith_bigint n) - (of_int 4))) + (of_int 2))
in
let x = Z.(powm a d n) in
if Z.(equal x ~$1) || Z.(equal x (n - ~$1)) then true
else
let rec loop i x =
if Z.(equal ~$i (r - ~$1)) then false
else
let x = Z.(powm x ~$2 n) in
if Z.(equal x (n - ~$1)) then true
else loop (i + 1) x
in
loop 0 x
in
if Z.(equal n one) then false
else if Z.(equal n ~$3) then false
else if Z.(equal (n mod ~$2) zero) then false
else
let r, d = get_rd Z.(n - one) in
let rec loop i bool =
if i = k then bool
else loop (i + 1) (bool && single_miller n r d)
in
loop 0 true
</lang>
| |||