A couple of weeks ago, I cleaned up my prime number library for OCaml. This library has a number of primality-testing methods in it, but my favorite is the Miller-Rabin primality test. It’s fast and rather accurate.
If you’d like to take a look at the library, please check out the camlprime GitHub page. The library is pretty easy to use. If you download and compile the library, you’ll end up with a toplevel that you can play with.
test.ml file has some examples of how to use the primality tests. However, my favorite thing about this library is that it includes a lazy list implementation of prime numbers. The following example shows how to set up a lazy list of prime numbers proved using the MR algorithm in the toplevel.
# open Num ;; # let prime_list = Prime.make (Prime.miller_rabin 500) (num_of_int 500) ;; val prime_list : Num.num LazyList.t = LazyList.Node (Int 503, <lazy>) # Prime.nth prime_list 500 ;; - : Num.num = Int 4363
The library is pretty fast, even for really large numbers. I’ve tested it on 300-digit prime numbers, and I’m sure it will scale to sizes much larger than that.
Any thoughts or improvements? Let me know in the comments.