search

kitfre / OCaml-Primes

A small library for dealing with prime numbers in OCaml
6 stars 1 forks source link

is_prime implementation #1

Open danaj opened 8 years ago

danaj commented 8 years ago

primes.mli indicates the implementation is 1000 (!) iterations of Miller-Rabin.

README.md indicates the test is AKS.

primes.ml seems to implement an exponential time binomial test, which is a very inefficient way to implement naive trial division. Perhaps this idea came from the numberphile video, which incorrectly describes this opening lemma as AKS (it is not), or from the Rosettacode page which is incorrectly named.

kitfre commented 8 years ago

Very true, I've make the AKS test much more efficient using the gen library and updated the .mli to reflect this

danaj commented 8 years ago

It's still not the AKS test though.

kitfre commented 8 years ago

Noted - making it true to the AKS test will be added to the list of things to update, I'll update the readme to reflect this addition to the todo list

struktured commented 8 years ago

I added the Miller-Rabin probablistic test for the mean time with PR #3 .