library(nan_numerics_prime)

Module prime provides predicates to test (positive integer) numbers for primality, find divisors and factor numbers, generate prime numbers in some interval, find consecutive prime numbers, and save/load all prime numbers up to some value to/from a file or stream.

All predicates in module prime are safe, i.e. validate input arguments and ensure steadfastness. For maximum performance, user code can directly call the unsafe public (not exported) predicates in module prime_lgc.

Implements a variant of the Miller-Rabin primality test that is deterministic for numbers up to 3317044064679887385961980, otherwise it is probabilistic with the number of iterations fixed at 20.

For better performance, leverages a prime wheel of level 4, i.e. generated by the first 4 consecutive prime numbers, and the memoization of pairs of consecutive prime numbers.

NOTE: Since the primality test in use is probabilistic in general, this module is not suitable for cryptographic applications.

This library was developed and tested with: SWI-Prolog 7.3.25 - http://www.swi-prolog.org/

Usage example:

?- pack_install(nan_numerics_prime).
true.

?- use_module(library(nan_numerics_prime)).
true.

?- time(prime_right(1234567891012345678901234567890123456789011111, P)).
% 1,205 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
P = 1234567891012345678901234567890123456789011139.

?- time(prime_lgc:right_(1234567891012345678901234567890123456789011111, P)).
% 1,197 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
P = 1234567891012345678901234567890123456789011139.

author

- Julio P. Di Egidio

version

- 1.2.5-beta

copyright

- 2016 Julio P. Di Egidio

license

- GNU GPLv3

To be done

- Implement prime counting/n-th prime functions.

- Implement probabilitic test error estimates?

- Implement deterministic tests (elliptic curves)?

- Implement dynamic wheel with option for level?

- Implement option for num. of probabilistic iterations?

- Improve compatibility with other Prolog systems.

 prime_test(+N:posint) is semidet

 prime_div(+N:posint, -P:prime) is semidet

 prime_div_rev(+N:posint, -P:prime) is semidet

 prime_fact(+N:posint, -PFs:list(pfact)) is det

 prime_gen(-P:prime) is multi

 prime_gen(+Inf:posint, -P:prime) is multi

 prime_gen(+Inf:posint, +Sup:posint, -P:prime) is nondet

 prime_gen_rev(+Sup:posint, -P:prime) is nondet

 prime_gen_rev(+Inf:posint, +Sup:posint, -P:prime) is nondet

 prime_next(+N:posint, -P:prime) is det

 prime_prev(+N:posint, -P:prime) is semidet

 prime_right(+N:posint, -P:prime) is det

 prime_left(+N:posint, -P:prime) is semidet

 prime_mem_clear is det

 prime_mem_fill(+Sup:posint) is det

 prime_mem_count(-Count:nonneg) is det

 prime_det_max(-Max:posint) is det

 prime_prb_mul(-Mul:posint) is det

 prime_whl_lev(-Lev:posint) is det

 prime_load_file(+File:file) is det

 prime_load_file(+File:file, +Sup:posint) is semidet

 prime_save_file(+File:file, +Sup:posint) is semidet

 prime_load_stream(+Stream:stream) is det

 prime_load_stream(+Stream:stream, +Sup:posint) is semidet

 prime_save_stream(+Stream:stream, +Sup:posint) is semidet

 error:has_type(+Type:atom, @Term:any) is semidet[multifile]