primate - PRIMe Algorithm TEster
NOTE: The prime number algorithms tested
with this program are described in greater detail in
tests my prime-number functions in LIBGPL's
Check if a number is prime:
% primate number
List all primes in the range, [start...end], inclusive:
% primate -list start-end
List count primes beginning with start:
% primate -list start,count
Find the next prime after a number (even if the number itself is prime):
% primate -next number
Verify that the prime functions generate the correct primes in 3 ranges.
The generic "-verify last" option chooses the appropriate bit width for the
CPU's unsigned longs. The pre-computed tables against which generated
primes are matched have entries for 32- and 64-bit unsigned longs. If
unsigned longs are less than 32 bits wide, there's no point in trying
"last32" verification. Likewise, if unsigned longs are less than 64 bits
wide, there is no point in trying "last64" verification.
% primate -verify first # First 1000 prime numbers.
% primate -verify last # Last 1000 prime numbers in unsigned long.
% primate -verify last32 # Last 1000 prime numbers in 32-bit integer.
% primate -verify last64 # Last 1000 prime numbers in 64-bit integer.
Time an operation; most output is suppressed in timing mode. If the
operation is very quick, repeat the operation count times to get
meaningful times for comparison purposes.
% primate -time [-repeat count] ... (other options) ...
Use an alternate is-prime? function rather than the default
nbrIsPrime() library function. (Option names and arguments can be
abbreviated as far as desired, so "-a s" is as good as "-alternate
# Check every single divisor (hard-coded).
% primate -alt ones ... (other options) ...
# Check odd divisors, skip evens (hard-coded).
% primate -alt odds ... (other options) ...
# Skip odds divisible by 3 and evens (hard-coded).
% primate -alt skip23 ... (other options) ...
# Built-in version of nbrIsPrime() (sequence-driven).
% primate -alt diffs ... (other options) ...
Select a different skip-through prime for the default nbrIsPrime() or
built-in "diffs" functions; the default is STP 7. This option also
generates the sequence of differences for the new skip-through prime; the
often lengthy time taken to generate a sequence is not included in timing
% primate -qprime stp ... (other options) ...
Print information (sequence length, range, etc.) about all skip-through
primes that can be used without overflow according to the size of an
% primate -qinfo
List the sequence of differences for a skip-through prime:
% primate -qgen stp
Rarely used options not discussed here: "-qc#kpi stp", "-qmax
stp", and "-q128info".
% primate [-debug] [-help]
[-qc#kpi stp] [-qgen stp] [-qmax stp]
[-verify first|last|last32|last64] [-xtra]
[-repeat count] [-time]
- turns debug on.
- prints out a help message.
- generates a list of prime numbers. If "start" alone is
specified, the program generates prime numbers beginning at the
start number (which may or may not be prime itself); the program
will continue running until ULONG_MAX is reached and checked.
If "start,count" is specified and count
is negative, the last count prime numbers preceding and
ending with start are generated (in reverse order). If
count is positive, the first count prime numbers
beginning with and following start are generated. If a
range is specified, "start-end", the program
will generate a list of the prime numbers in that range, including
the start and/or end numbers if they're prime.
- checks if the pre-computed, largest 32- or 64-bit prime numbers
are prime (which, of course, they are). "primate -max 64" takes
nearly 40 seconds on my old, Fedora Core 15 computer to test
the primality of the largest 64-bit prime (using the default
skip-through prime of 7).
- prints out the next prime number after the given number, regardless
if the given number is itself prime.
- generates a listing of the values of i coprime with c#,
where c is the specified skip-through prime. These values are
associated with the c#k+i form for primes; see
the file prolog in nbr_util.c for a detailed description. The program
derives the values of i from the skip-through prime's sequence
of differences, so the same memory and time constraints of the
"-qprime stp" option apply. (The "p" in "c#kpi" means
"plus", i.e., "c#k+i".)
- generates and lists the sequence of differences for skip-through
prime stp. This operation requires allocating memory
for the sequence of differences. My computer (64-bit Linux)
successfully allocated the 1GB sequence for STP 29, but failed
when trying to allocate the 30GB sequence for STP 31. Large
skip-through primes have long sequences, so be aware that the
output of this option can be voluminous; for example, one billion
numbers are listed for STP 29.
- determines the maximum difference in the sequence of differences for
skip-through prime stp. The algorithm used is identical to
the algorithm used by "-qgen stp", but it is not necessary to
allocate memory for the sequence. As each difference is generated,
it is compared to the maximum seen so far and then discarded.
Consequently, this operation is useful as a stand-in for
"-qgen stp" when benchmarking sequence generation for
skip-through primes whose sequences require more memory than the
system can allocate. Be aware that this is a time-consuming process
for larger skip-through primes. On my computer, it took 11
seconds — at 100% CPU usage — to scan the
differences for STP 23, nearly 7 minutes for STP 29, 3.5 hours for
STP 31, and 6.4 days for STP 37!
- displays a table of the characteristics of all possible skip-through
primes and their sequences of differences, given the size of unsigned
longs on the CPU.
- displays a listing of the characteristics of all possible skip-through
primes and their sequences of differences for 128-bit, unsigned
integers. (The numbers are very, very big, so a table was out of the
question.) This option takes advantage of GCC's (and others')
non-standard implementation of 128-bit arithmetic on 64-bit CPUs.
This option is only available if C preprocessor symbol HAVE___INT128
is defined as 1 when this program is compiled with GCC. This GCC
extension for 128-bit integers is not used elsewhere in
the program or in the NBR_UTIL library. So, the checking, listing,
and verifying of 128-bit integers is not supported (unless the CPU's
"unsigned long" data type is actually 128 bits wide).
- verifies that the prime function generates the correct prime numbers
in certain ranges. The verification immediately terminates with an
error message if a non-prime number is generated or if an actual prime
number is skipped. The generated prime numbers are compared to one of
the tables of pre-computed primes in 3 ranges:
NOTE that "-verify last" on a CPU with 64-bit longs takes
a very long time. On my old Fedora Core 15 machine, 24.8 hours to
- "-verify first" verifies the first 1000 prime numbers.
- "-verify last" verifies the last 1000 prime numbers that can
be represented in an unsigned long. If the width of an
unsigned long is 64 bits or greater, the last 1000 prime
numbers preceding 264 are verified. If the width
is less than 64 bits, the last 1000 prime numbers preceding
232 are verified.
- "-verify last32" verifies the last 1000 prime numbers preceding
232; this option is also useful if the native
unsigned longs are wider than 32 bits (e.g., 64 bits).
- checks if 4294945091 is prime (it isn't). A shorthand option for me
when I was developing this program.
- checks if the given number is prime.
- use an alternate is-prime? function for comparison purposes:
- The "ones" function implements a "fast", hand-coded loop
that checks every single divisor: 2, 3, 4, 5, 6, 7, ...
- The "odds" function implements a fast, hand-coded loop
that checks all odd divisors. Using this option along
with "-time" provides baseline timing against which more
optimized functions can be compared.
- The "skip23" function implements a fast, hand-coded loop
that skips divisors divisible by 2 or by 3; this is
equivalent to having a skip-through prime of 3, but
it does not use the generic, sequence of differences
- The "diffs" function implements the generic, sequence
of differences algorithm for different skip-through
primes. This function is virtually identical to the
library function, nbrIsPrime(), except you can modify
or replace the function in the test program in order
to experiment with your own optimizations. As with
nbrIsPrime(), the default skip-through prime is 7;
a different skip-through prime can be specified with
the "-qprime stp" option.
- specifies the skip-through prime to use with the library function,
nbrIsPrime(), or with this program's internal "-alternate diffs"
function. For these functions to use the desired skip-through
prime, the "-qprime stp" option must generate the sequence
of differences for the STP. On my computer, it took 11 seconds to
generate the sequence for STP 23 and nearly 7 minutes for STP 29.
The system couldn't allocate enough memory for STP 31's sequence,
but it would take 3.5 hours to generate STP 31's sequence and
6.4 days to generate STP 37's sequence!
- repeats certain operations the specified number of times. This is
useful, for example, when timing checking if a number is prime.
A single check might take too little time to make a meaningful
comparison with, say, an alternate is-prime? function;
repeat the check 1,000 times or 10,000 times and a more realistic
comparison can be made.
- measures and displays the time it takes to perform an operation (or
count iterations of the operation if "-repeat count"
is also given on the command line). Almost all output is suppressed
to keep I/O from affecting the timing. If the "-qprime stp"
option was specified, the skip-through prime's sequence of differences
is generated before the timer is started.