nbr_util- Number Utilities
NOTE: The algorithms implemented in this package are described in greater detail in:
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)) ;
The NBR_UTIL package is divided among the three source files listed below.
Programs only need to include the single header file,
to access all the 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.
Prime number functions (see
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.
Fast integer square root function (see
"Fast Integer Square Roots")
nbrUnsignedSQRT()- computes the unsigned integer square root of a number.
libgpl for the
complete source, including support routines and build files.)