Miller–Rabin primality test: Difference between revisions
Content added Content deleted
(Realize in F#) |
(Add OCaml implementation) |
||
Line 3,549: | Line 3,549: | ||
echo("\nnumber of primes < ",num, " are ", primes.len) |
echo("\nnumber of primes < ",num, " are ", primes.len) |
||
echo (epochTime()-te).formatFloat(ffDecimal, 6) |
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> |
</lang> |
||