kitfre / ocaml-primes Goto Github PK
View Code? Open in Web Editor NEWA small library for dealing with prime numbers in OCaml
A small library for dealing with prime numbers in OCaml
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.
This repo is mentioned as the upstream for the opam package called primes
. However, for some reason I failed to see, the package available on opam (OCaml 4.06.1) is not at all in sync with this repo.
me@home:~$ opam update
me@home:~$ opam show primes
package: primes
version: 1.3.5
repository: default
upstream-url: https://github.com/KitFreddura/OCaml-Primes/archive/1.3.5.tar.gz
upstream-kind: http
upstream-checksum: 583f2e27c00a06465719ae84aa4f79f2
homepage: https://github.com/KitFreddura/OCaml-Primes
bug-reports: https://github.com/KitFreddura/OCaml-Primes/issues/new
dev-repo: https://github.com/KitFreddura/OCaml-Primes.git
author: Kit Freddura <[email protected]>
license: MIT License
depends: ocamlfind & zarith & gen
installed-version:
available-versions: 1.3.3, 1.3.5
description: A small library for dealing with primes.
Primes is a library for finding and testing prime numbers in OCaml, see the .mli file for interface details. Please check out the git for issues, concerns, suggestions or if you wish to contribute!
me@home:~$ opam install primes
So I got version 1.3.5, although the latest version is 1.3.3 according to the opam
file in this repo. The interface I got through opam is missing important bits:
utop # #show Primes ;;
module Primes :
sig
val big_primes : int -> Z.t list
val primes : int -> int list
val is_prime : int -> bool
val prime_factors : int -> int list
end
Functions big_is_prime
and miller_rabin_test
are missing (the first one is missing from the .mli
file even in this repo).
Even worse, function is_prime
is seriously flawed (but seemingly not because of a dummy implementation, because returning true
still takes quite a long time):
utop # for n = 1 to 4_000 do assert (Primes.is_prime n) done ;;
- : unit = ()
So what’s going on?
'is_prime' seems working only for 2-3-5-7-11-13-17 and 19
(23 -> false - therefore 'prime-factors 23' gives the wrong list [] ). Interesting !
Note 1 : please don't use Core for the only '~f:' syntax. This is crazy :)
You can have the same result with the (one and only) OCaml Standard Library by writing
'ListLabels.filter ...' or 'ListLabels.map ...'.
(Suppress Core but add 'Gen' as dependency in your README.md file)
Note 2 : your source code is ugly: lot of useless whitespaces and a bad
indentation. (I suggest 'opam install ocp-indent'. ocp-indent can be integrated in your editor
or can be used as a separate program)
needs one. badly. @KitFreddura - I'm indifferent. Can we settle on one for this project so tests can be written for the critical functions?
Might be worth functorizing over the numerical type so you can generate different versions of the top level api. (The inner api can be a specific numerical type though if it makes sense, probably zarith as sometimes the calculations exceed int space even if the answer does not).
using dune
to compile my module using primes
:
gcc: error: /home/opam/.opam/5.0/lib/primes/primes.a: No such file or directory
$ ls -al /home/opam/.opam/5.0/lib/primes/
total 536
drwxr-xr-x 2 opam opam 4096 Sep 5 18:27 .
drwxr-xr-x 1 opam opam 4096 Sep 5 18:33 ..
-rw-r--r-- 1 opam opam 159 Jul 26 2016 META
-rw-r--r-- 1 opam opam 484074 Sep 5 18:25 primes.cma
-rw-r--r-- 1 opam opam 849 Sep 5 18:24 primes.cmi
-rw-r--r-- 1 opam opam 2643 Sep 5 18:25 primes.cmo
-rw-r--r-- 1 opam opam 5217 Sep 5 18:24 primes.cmti
-rw-r--r-- 1 opam opam 1012 Sep 5 18:25 primes.cmx
-rw-r--r-- 1 opam opam 585 Sep 5 18:25 primes.cmxa
-rw-r--r-- 1 opam opam 782 Jul 26 2016 primes.mli
-rw-r--r-- 1 opam opam 13872 Sep 5 18:25 primes.o
I imagine that we want to make signatures for various common number theoretic functions or tests, if only to make the api manageable as different implementations arise. Maybe something like this for prime testing?
(* Number.ml- we may be able to find this interface in Base or Containers *)
module type S =
sig
type t
val add : t -> t -> t
(* ... etc. *)
end
(* Optional_args.ml *)
module type S =
sig
type t (** type of default argument. *)
val default : t (** A default value used when not specified.*)
end
(* Primes.ml *)
module type S =
sig
module Number : Number.S
module Optional_args : Optional_args.S
val is_prime : ?Optional_args.t -> Number.t -> bool
end
(* Random brute force example *)
module Iter_args = struct type t = {max_iters:int} let default = {max_iters=1000} end
module Brute_force : Primes.S with
module Number = Z and
module Optional_args = Iter_args =
struct
module Number = Z
module Optional_args = Iter_args
open Optional_args
let is_prime ?opt x = (* randomly try up to opt.max_iters to find a divisor *)
end
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.