Math Topics and Software

Home ] Nonlinear ] Linear ] Integration ] Roots ] XBCD_Math ] Parsers ]

This page has links to mathematical topics, algorithms and software. Much of the material accessible from this page is unique or not readily available elsewhere.  Some files you will find include:

The polynomial root finders will find all real and complex roots of real polynomials and include a port of the Jenkins-Traub method from FORTRAN to C++. Some of the C/C++ code are translations of the original FORTRAN code found in Zhang and Jin, "Computation of Special Functions", John Wiley and Sons, 1996.

Gamma Function

The following source files supporting the Gamma function are available in these links:

Psi Function

Routines for computing the psi function for real and complex arguments are provided here.

Elliptic Integrals of 1st and 2nd Kind

The file ell_ag.cpp is a port of the subroutine for the integrals Elliptic 'F' (1st kind) and Elliptic 'E' (2nd kind) from the FORTRAN code in the book by Zhang and Jin cited in the next paragraph. This code uses a method based on the arithmetic-geometric mean. Sever minor changes have been made, including the change in the argument from degrees to radians, and re-ordering of the input parameters so that the argument comes first, followed by the modulus.

Bessel Functions

This archive contains a port of the Bessel functions in "Computation of Special Functions", by Zhang and Jin, John Wiley and Sons, 1996. The files include C++ versions of the algorithms and a header file. Please consult the above cited publication for details on input and output naming conventions and function usage.

Individual files are available in the following links:

XBCD_Math

This extended precision, high performance math library supports logs, exponentials, trig and inverse trig functions, hyperbolic and inverse hyperbolic functions, as well as generalized factorial and the gamma function. Details and downloads are in XBCD.

Prime Numbers

The following executables deal with prime numbers in the limited range of 32-bit unsigned integers, i.e. 232 - 1. Because of the restricted range, they should only be considered as tools for benchmarking the accuracy or performance of similar algorithms.

Prime Count

This executable, crb_primepi.exe, counts the number of primes which are less than or equal to a given positive integer in the range from 0 to 4,294,967,295 (232 - 1). The restricted range is not be sufficient for general use or research,  but the implementation is modest in size and reasonably fast. It is undemanding of system resources as it does not use recursion or allocate additional external memory. The time required to compute the prime count is displayed for benchmarking. The timer employs the Pentium CPU time stamp counter so the application will not work on other platforms. No feature testing is used, so make sure you have the proper hardware before running this executable.

Nth Prime

crb_nprime.exe finds the nth prime number, given the number 'n'. Again, the range of valid prime numbers is restricted to those expressible by an unsigned 32-bit integer. The number of primes in this range is such that the range of 'n' is from 1 to 203280221. This application uses a method similar to that in the prime count program above. It is reasonably fast and is not resource intensive. A benchmarking timer is included. The timer employs the Pentium CPU time stamp counter so the application will not work on other platforms. No feature testing is used, so make sure you have the proper hardware before running this executable.

Factoring

The following applications are not meant to be competitive with advanced factoring machines dealing with RSA sized integers. They should be considered only as 'toy' applications with severely limited range, suitable for benchmarking the accuracy or performance of similar programs.

Sieve Method

This program xfactor.exe will decompose any positive integer smaller than 2^32 into its prime factors. Although the algorithm is only a simple variant of a sieve, its benchmark timings reveal excellent performance over the range supported. Timing for each invocation is indicated along with the list of prime factors. NOTE: This executable requires the Pentium time stamp counter for benchmarking. Elapsed time is computed for a 2GHz Pentium and must be scaled for other platforms. No feature checking is provided, so make certain your system includes the proper hardware.

Fermat's Method

A variant of Fermat's method for factoring integers is described in Knuth1, as Algorithm C. It is implemented here as xfermat.exe and in this executable support for integers larger than 32-bits is provided. It will generally not outperform xfactor.exe for number smaller than 2^32 and only outputs one pair of (not necessarily prime) factors, but for larger numbers it is efficient and can invoked recursively on any factors found to completely decompose a composite integer into its prime factors. NOTE: This executable requires the Pentium time stamp counter for benchmarking. Elapsed time is computed for a 2Ghz Pentium and must be scaled for other platforms. No feature checking is provided, so make certain your system  includes the proper hardware.

Source code for an extremely simple and compact version of Knuth's Algorithm C is available in fermat.cpp. This code does not include benchmark timing capability, but its performance is much better over the range of 32-bit integers than either of the above programs.

1 Donald E. Knuth, "The Art of Computer Programming", Vol. 2 / Seminumerical Algorithms, 2nd Ed., Addison-Wesley Publishing Co., 1980, p.371.

Expression Evaluators

Go to parsers to find source code for expression evaluators supporting double precision, complex double precision, and extended precision numeric types.