Crates.io | machine-prime |
lib.rs | machine-prime |
version | 1.3.0 |
source | src |
created_at | 2023-04-24 18:55:51.305437 |
updated_at | 2024-06-27 17:48:28.529239 |
description | ne plus ultra primality testing for machine-sized integers |
homepage | |
repository | https://github.com/JASory/machine-prime |
max_upload_size | |
id | 847729 |
size | 1,466,404 |
Machine prime is a simple efficient primality test for 64-bit integers, constructed in a reproducible manner with the F-Analysis library, and Feitsma/Galway's base-2 pseudoprime table. It is available on crates.io.
Two functions are provided with a C-style api to enable calling in other languages.
is_prime is optimised for the average case and is intended as a general primality test. is_prime_wc is optimised for the worst case and is intended to be used in functions that the number is already suspected to be prime. For instance factorisation where trial division has already been performed. It performs absolutely minimal checks, and is permitted to have a handful of known failure points leaving it up to the user to decide if it is necessary to expend the cost to check for them.
This function api will never change. is_prime will always correctly evaluate any 64-bit integer, however is_prime_wc failure points may change.
Three modes are available for these functions, Default and Small and Tiny. Memory use decreases but the complexity increases with each successive mode.
The Default utilizes a large hashtable, and trial division by prime inverse multiplication
to_hashtable(Some(262144),Some(1276800789),Some(65535))
.
Compute the EPF pseudoprimes to Feitsma's table and apply the hashtable method to reproduce the
hashtable used. See the "hashtable" example in f-analysis for an explicit implementation.SSMR is identical to Default but branches to use the SSMR algorithm for integers less than 2^40
The parameters and failure cases are identical to the SSMR crate
Due to branching, cache-utilisation and calculation modifications, it is slower than the SSMR crate
Only use this variant if the SSMR crate doesn't provide a large enough interval
Small forgoes the hashtable but still uses the trial division
Tiny simply uses the Fermat bases implemented in Small, the only difference therefore between is_prime and is_prime_wc is the latter forgoes any additional checks to ensure correctness. It saves a small amount of memory over Small.
Note that all failures will panic in debug mode but are overridden by optimization, the dynamic library produced by the Makefile will not panic for any.
Due to some barriers to compiling no-std libraries, the version in crates.io and the repository are slightly different, although using the exact same algorithms. crates.io version is configured for stable compilers, while the repository is configured for nightly compiler, as the intention is to use it to build dynamic libraries.
To use from crates.io, simply include it in your cargo.toml file with the feature "small" or "tiny" if you want those versions. Default will be the fastest with the hashtable.
To use as a dynamic library, make sure you are running rustc nightly; git clone
this repository and run make
to compile the Default mode, make small
for the Small mode and make tiny
for the Tiny mode. This will create the library, and make install
will install it to /lib/libprime.so
. (Make sure you are superuser). Installing the library is recommended but not strictly necessary. Link to it using -lprime
if you are using gcc.
See the "binding" folder in the repository for various language bindings. Several languages including Ada,C,Fortran,Julia, and Python are supported.
Many number-theoretic functions either require a primality test or use a primality test for greater efficiency. Examples include the Legendre symbol and factorization.While primality testing is rarely the bottleneck for these functions, it is a limiting factor in highly optimized computations. By providing an fast public domain implementation that can be called in many languages and architectures, the work towards constructing such a function is minimised.
This primality test is not intended to be the fastest in every interval, but rather faster in general and the average case. There are small tests that are faster for 32-bit, however this is such a miniscule interval that branching to account for them would result in a reduction in efficiency in general. See Performance for some benchmarks and comparison to other efficient primality tests.
There are fast functions that can be used to optimise for memory better. However, they use floating point arithmetic. The intent of this library is to be extremely fast, but flexible enough to be used when only integer arithmetic is supported. Consequently, floating point arithmetic, inline assembly and SIMD are not utilised. Additionally this is why low memory variants are provided, as not everyone is able or willing to use over 500 kilobytes of memory.
Approximate size of binary dynamic library varies with your compiler however the following are reasonable estimates: Default-542.4kb, Small-18.1kb, Tiny-14kb
Building for embedded systems has not been tested, however there is no known cause for failure.
This software is in public domain, and all the values can be deterministically recomputed using the open-source auditable f-analysis library.