primate - PRIMe Algorithm TEster

NOTE: The prime number algorithms tested with this program are described in greater detail in "Primality Testing".

primate tests my prime-number functions in LIBGPL's NBR_UTIL package.

Basic Usage

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.

Advanced Usage

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 skip23".)

                    # 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 benchmarks ("-time").

% 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 unsigned long:

% primate -qinfo

Print the same information for 128-bit unsigned integers (using a GCC extension for 128-bit integers which is only used in this program for generating this information):

% primate -q128info

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".

Invocation:

% primate [-debug] [-help]
                                        # Operations
          [-list start]
          [-list start,[-]count]
          [-list start-end]
          [-maximum 32|64]
          [-next number]
          [-qc#kpi stp] [-qgen stp] [-qmax stp]
          [-qinfo] [-q128info]
          [-verify first|last|last32|last64] [-xtra]
          [number]
                                        # Modifiers
          [-alternate ones|odds|skip23|diffs]
          [-qprime stp]
          [-repeat count] [-time]

where

-debug

turns debug on.

-help

prints out a help message.

-list start

-list start,[-]count

-list start-end

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.

-maximum 32|64

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).

-next number

prints out the next prime number after the given number, regardless if the given number is itself prime.

-qc#kpi stp

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".)

-qgen stp

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.

-qmax stp

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!

-qinfo

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.

-q128info

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).

-verify first|last|last32|last64

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:

1. "-verify first" verifies the first 1000 prime numbers.
2. "-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 2⁶⁴ are verified. If the width is less than 64 bits, the last 1000 prime numbers preceding 2³² are verified.
3. "-verify last32" verifies the last 1000 prime numbers preceding 2³²; this option is also useful if the native unsigned longs are wider than 32 bits (e.g., 64 bits).

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 be exact!

-xtra

checks if 4294945091 is prime (it isn't). A shorthand option for me when I was developing this program.

number

checks if the given number is prime.

-alternate ones|odds|skip23|diffs

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 algorithm.
• 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.

-qprime stp

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!

-repeat count

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.

-time

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.