nbr_util - Number Utilities

NOTE: The prime number and square root algorithms implemented in this package are described in greater detail in "Primality Testing" and "Fast Integer Square Roots", respectively.

The NBR_UTIL package is a collection of functions dealing with numbers in some way or another. I wanted to remove the calculation of the first (next) prime number after the expected table size from my HASH_UTIL package and "prmNextPrime()" didn't really appeal to me, so I decided on a prefix of NBR. Perhaps I'll add some other number-related functions in the future. (And so I did with the integer square root function!)

Function nbrUnsignedSQRT() returns the floor of the square root of an unsigned integer (i.e., the real square root with the fractional part, if any, discarded):

    #include  <stdio.h>                     -- Standard I/O definitions.
    #include  "nbr_util.h"                  -- Number utilities.
    unsigned  long  number = 34 ;           -- Real square root is 5.8
    unsigned  long  root = nbrUnsignedSQRT (number, NULL) ;
    printf ("Square root = %lu\n", root) ;  -- Prints floor[5.8] = 5

The prime number functions are used to test if unsigned integers are prime and to step through successive primes:

                                            -- # is 34, from above
    boolean  isPrime = nbrIsPrime (number, NULL) ;
    printf ("%lu is %s\n",                  -- Prints "34 is composite"
            number, isPrime ? "prime" : "composite") ;

    number = nbrNextPrime (number, NULL) ;
    printf ("%lu\n", number) ;              -- Prints 37
    printf ("%lu\n",                        -- Prints 43 (37 -> 41 -> 43)
            nbrNextPrime (nbrNextPrime (number, NULL), NULL)) ;

Public Procedures

nbrIsPrime() - checks if a number is a prime number. This is the full-blown version that works with different skip-through primes and sequences of differences. It's faster and not really much bigger than the following ...

nbrIsPrime() - checks if a number is a prime number. This version has a small memory footprint and is hard-coded for skip-through prime 3. A C Preprocessor symbol must be defined for this version to be used; one or the other version will be compiled into the object file, but not both at the same time.

nbrNextPrime() - determines the next prime number following a given value.
nbrNextPrimeF() - determines, using a caller-supplied check-prime function, the next prime number following a given value.
nbrPrimeConfigCreate() - creates a prime determination configuration.
nbrPrimeConfigDestroy() - destroys a prime determination configuration.
nbrPrimeSeqDiffs() - generates a sequence of differences.
nbrPrimeSeqDiffsLength() - calculates the length of a sequence of differences.
nbrPrimeSeqDiffsMax() - determines the maximum difference in a sequence of differences.
nbrPrimeSeqDiffsRange() - determines the range of divisors in a sequence of differences.
nbrUnsignedSQRT() - computes the unsigned integer square root of a number.

Source Files


Alex Measday  /  E-mail