nbr_util - Number Utilities

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

The NBR_UTIL package is divided among the three source files listed below. Programs only need to include the single header file, nbr_util.h, to access all the functions.

Source file: nbr_util.c - Assorted functions

nbrFactorsOf() - generates the prime factors of a number.

nbrBinaryGCD() - computes the GCD of two numbers using the binary variant of Euclid's algorithm.

nbrModuloGCD() - computes the GCD of two numbers using the modulo-based, standard Euclid's algorithm.

nbrSubtractGCD() - computes the GCD of two numbers using the subtraction-based variant of Euclid's algorithm.

Source file: nbr_util_primes.c - Prime number functions (see "Primality Testing")

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.

Source file: nbr_util_roots.c - Fast integer square root function (see "Fast Integer Square Roots")

nbrUnsignedSQRT() - computes the unsigned integer square root of a number.

Source Files

nbr_util.c

nbr_util_primes.c

nbr_util_roots.c

nbr_util.h

(See libgpl for the complete source, including support routines and build files.)