﻿ Math

# Mathematical Topics, Algorithms and Software

## "computer techniques and methods"

This section contains links to a variety of mathematical topics, methods algorithms and software. Much of the material is unique or not readily available elsewhere.

The contents of the navigation subsections are:

• LINEAR — a collection of linear solvers and ports from other languages,
• NON-LINEAR — non-linear solvers, including Newton's and Broyden's,
• INTEGRATION — integrators, including QUADPACK and double exponential,
• POLY ROOTS — advanced polynomial root-finders, original methods and ports,
• XBCD-MATH — an extended precision BCD math package for calculator use.

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.

Here are some links to specific topics in this section.

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

• Psi -- Psi function for real arguments.
• CPsi -- Psi function for complex arguments.

## 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. Several 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:

• Bessjy -- Bessel functions Jn and Yn for real argument and integer or real order.
• Bessik -- Modified Bessel function In and Kn for real argument and integer or real order.
• CBessjy -- Bessel functions Jv and Yv for real or complex arguments and real order.
• CBessik -- Modified Bessel functions Iv and Kv for complex arguments and real order.

## 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. 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, cbprimepi.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. 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

cbprime.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 Knuth 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 be 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.

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