This is documentation for Mathematica 4, which was
based on an earlier version of the Wolfram Language.
View current documentation (Version 11.1)
Wolfram Research, Inc.

Basic System FeaturesAlgebra and Calculus

A.9.4 Numerical and Related Functions

Number representation and numerical evaluation

FilledSmallCircle Large integers and high-precision approximate numbers are stored as arrays of base or digits, depending on the lengths of machine integers.

FilledSmallCircle Precision is internally maintained as a floating-point number.

FilledSmallCircleIntegerDigits and related base conversion functions use a recursive divide-and-conquer algorithm.

FilledSmallCircleN uses an adaptive procedure to increase its internal working precision in order to achieve whatever overall precision is requested.

FilledSmallCircleFloor, Ceiling and related functions use an adaptive procedure similar to N to generate exact results from exact input.

Basic arithmetic

FilledSmallCircle Multiplication of large integers and high-precision approximate numbers is done using interleaved Karatsuba and FFT algorithms.

FilledSmallCircle Integer powers are found by an algorithm based on Horner's rule.

FilledSmallCircle Reciprocals and rational powers of approximate numbers use Newton's method.

FilledSmallCircle Exact roots start from numerical estimates.

FilledSmallCircle Significance arithmetic is used for all arithmetic with approximate numbers beyond machine precision.

FilledSmallCircle Basic arithmetic uses approximately 400 pages of C source code.

Pseudorandom numbers

FilledSmallCircleRandom uses the Wolfram rule 30 cellular automaton generator for integers.

FilledSmallCircle It uses a Marsaglia-Zaman subtract-with-borrow generator for real numbers.

Number-theoretical functions

FilledSmallCircleGCD uses the Jebelean-Weber accelerated GCD algorithm, together with a combination of Euclid's algorithm and an algorithm based on iterative removal of powers of 2.

FilledSmallCirclePrimeQ first tests for divisibility using small primes, then uses the Miller-Rabin strong pseudoprime test base 2 and base 3, and then uses a Lucas test.

FilledSmallCircle As of 1997, this procedure is known to be correct only for , and it is conceivable that for larger it could claim a composite number to be prime.

FilledSmallCircle The package NumberTheory`PrimeQ` contains a much slower algorithm which has been proved correct for all . It can return an explicit certificate of primality.

FilledSmallCircleFactorInteger switches between removing small primes by trial division and using the Pollard , Pollard rho and quadratic sieve algorithm.

FilledSmallCircle The package NumberTheory`FactorIntegerECM` contains an elliptic curve algorithm suitable for factoring some very large integers.

FilledSmallCirclePrime and PrimePi use sparse caching and sieving. For large , the Lagarias-Miller-Odlyzko algorithm for PrimePi is used, based on asymptotic estimates of the density of primes, and is inverted to give Prime.

FilledSmallCircleLatticeReduce uses the Lenstra-Lenstra-Lovasz lattice reduction algorithm.

FilledSmallCircle To find a requested number of terms ContinuedFraction uses a modification of Lehmer's indirect method, with a self-restarting divide-and-conquer algorithm to reduce the numerical precision required at each step.

FilledSmallCircleContinuedFraction uses recurrence relations to find periodic continued fractions for quadratic irrationals.

FilledSmallCircleFromContinuedFraction uses iterated matrix multiplication optimized by a divide-and-conquer method.

Combinatorial functions

FilledSmallCircle Most combinatorial functions use sparse caching and recursion.

FilledSmallCircleFactorial, Binomial and related functions use a divide-and-conquer algorithm to balance the number of digits in subproducts.

FilledSmallCircleFibonacci[n] uses an iterative method based on the binary digit sequence of n.

FilledSmallCirclePartitionsP[n] uses Euler's pentagonal formula for small n, and the non-recursive Hardy-Ramanujan-Rademacher method for larger n.

FilledSmallCircleClebschGordan and related functions use generalized hypergeometric series.

Elementary transcendental functions

FilledSmallCircle Exponential and trigonometric functions use Taylor series, stable recursion by argument doubling, and functional relations.

FilledSmallCircle Log and inverse trigonometric functions use Taylor series and functional relations.

Mathematical constants

FilledSmallCircle Values of constants are cached once computed.

FilledSmallCircle Binary splitting is used to subdivide computations of constants.

FilledSmallCirclePi uses the Chudnovsky formula for computations up to ten million digits.

FilledSmallCircleE is computed from its series expansion.

FilledSmallCircleEulerGamma uses the Brent-McMillan algorithm.

FilledSmallCircleCatalan is computed from a linearly convergent Ramanujan sum.

Special functions

FilledSmallCircle For machine precision most special functions use Mathematica-derived rational minimax approximations. The notes that follow apply mainly to arbitrary precision.

FilledSmallCircle Orthogonal polynomials use stable recursion formulas for polynomial cases and hypergeometric functions in general.

FilledSmallCircleGamma uses recursion, functional equations and the Binet asymptotic formula.

FilledSmallCircle Incomplete gamma and beta functions use hypergeometric series and continued fractions.

FilledSmallCirclePolyGamma uses Euler-Maclaurin summation, functional equations and recursion.

FilledSmallCirclePolyLog uses Euler-Maclaurin summation, expansions in terms of incomplete gamma functions and numerical quadrature.

FilledSmallCircleZeta and related functions use Euler-Maclaurin summation and functional equations. Near the critical strip they also use the Riemann-Siegel formula.

FilledSmallCircleStieltjesGamma uses Keiper's algorithm based on numerical quadrature of an integral representation of the zeta function.

FilledSmallCircle The error function and functions related to exponential integrals are all evaluated using incomplete gamma functions.

FilledSmallCircle The inverse error functions use binomial search and a high-order generalized Newton's method.

FilledSmallCircle Bessel functions use series and asymptotic expansions. For integer orders, some also use stable forward recursion.

FilledSmallCircle The hypergeometric functions use functional equations, stable recurrence relations, series expansions and asymptotic series. Methods from NSum and NIntegrate are also sometimes used.

FilledSmallCircleProductLog uses high-order Newton's method starting from rational approximations and asymptotic expansions.

FilledSmallCircle Elliptic integrals are evaluated using the descending Gauss transformation.

FilledSmallCircle Elliptic theta functions use series summation with recursive evaluation of series terms.

FilledSmallCircle Other elliptic functions mostly use arithmetic-geometric mean methods.

FilledSmallCircle Mathieu functions use Fourier series. The Mathieu characteristic functions use generalizations of Blanch's Newton method.

Numerical integration

FilledSmallCircle With Method->Automatic, NIntegrate uses GaussKronrod in one dimension, and MultiDimensional otherwise.

FilledSmallCircle If an explicit setting for MaxPoints is given, NIntegrate by default uses Method->QuasiMonteCarlo.

FilledSmallCircleGaussKronrod: adaptive Gaussian quadrature with error estimation based on evaluation at Kronrod points.

FilledSmallCircleDoubleExponential: non-adaptive double-exponential quadrature.

FilledSmallCircleTrapezoidal: elementary trapezoidal method.

FilledSmallCircleOscillatory: transformation to handle integrals containing trigonometric and Bessel functions.

FilledSmallCircleMultiDimensional: adaptive Genz-Malik algorithm.

FilledSmallCircleMonteCarlo: non-adaptive Monte Carlo.

FilledSmallCircleQuasiMonteCarlo: non-adaptive Halton-Hammersley-Wozniakowski algorithm.

Numerical sums and products

FilledSmallCircle If the ratio test does not give 1, the Wynn epsilon algorithm is applied to a sequence of partial sums or products.

FilledSmallCircle Otherwise Euler-Maclaurin summation is used with Integrate or NIntegrate.

Numerical differential equations

FilledSmallCircle With Method->Automatic, NDSolve switches between a non-stiff Adams method and a stiff Gear method. Based on LSODE.

FilledSmallCircleAdams: implicit Adams method with order between 1 and 12.

FilledSmallCircleGear: backward difference formula method with order between 1 and 5.

FilledSmallCircleRungeKutta: Fehlberg order 4-5 Runge-Kutta method for non-stiff equations.

FilledSmallCircle For linear boundary value problems the Gel'fand-Lokutsiyevskii chasing method is used.

FilledSmallCircle For 1+1-dimensional PDEs the method of lines is used.

FilledSmallCircle The code for NDSolve is about 500 pages long.

Approximate equation solving and minimization

FilledSmallCircle Polynomial root finding is done based on the Jenkins-Traub algorithm.

FilledSmallCircle For sparse linear systems, Solve and NSolve use several efficient numerical methods, mostly based on Gauss factoring with Markowitz products (approximately 250 pages of code).

FilledSmallCircle For systems of algebraic equations, NSolve computes a numerical Gröbner basis using an efficient monomial ordering, then uses eigensystem methods to extract numerical roots.

FilledSmallCircleFindRoot uses a damped Newton's method, the secant method and Brent's method.

FilledSmallCircle With Method->Automatic, FindMinimum uses various methods due to Brent: the conjugate gradient in one dimension, and a modification of Powell's method in several dimensions.

FilledSmallCircle If the function to be minimized is a sum of squares, FindMinimum uses the Levenberg-Marquardt method (Method->LevenbergMarquardt).

FilledSmallCircle With Method->Newton FindMinimum uses Newton's method. With Method->QuasiNewton FindMinimum uses the BFGS version of the quasi-Newton method.

FilledSmallCircleConstrainedMax and related functions use an enhanced version of the simplex algorithm.

Data manipulation

FilledSmallCircleFourier uses the FFT algorithm with decomposition of the length into prime factors. When the prime factors are large, fast convolution methods are used to maintain asymptotic complexity.

FilledSmallCircle For real input, Fourier uses a real transform method.

FilledSmallCircleListConvolve and ListCorrelate use FFT algorithms when possible. For exact integer inputs, enough digits are computed to deduce exact integer results.

FilledSmallCircleInterpolatingFunction uses divided differences to construct Lagrange or Hermite interpolating polynomials.

FilledSmallCircleFit works by computing the product of the response vector with the pseudoinverse of the design matrix.

Approximate numerical linear algebra

FilledSmallCircle Machine-precision matrices are typically converted to a special internal representation for processing.

FilledSmallCircle Algorithms similar to those of LINPACK, EISPACK and LAPACK are used when appropriate.

FilledSmallCircleLUDecomposition, Inverse, RowReduce and Det use Gaussian elimination with partial pivoting. LinearSolve uses the same methods, together with iterative improvement for high-precision numbers.

FilledSmallCircleSingularValues uses the QR algorithm with Givens rotations. PseudoInverse and NullSpace are based on SingularValues.

FilledSmallCircleQRDecomposition uses Householder transformations.

FilledSmallCircleSchurDecomposition uses QR iteration.

FilledSmallCircleMatrixExp uses Schur decomposition.

Exact numerical linear algebra

FilledSmallCircleInverse and LinearSolve use efficient row reduction based on numerical approximation.

FilledSmallCircle With Modulus->n, modular Gaussian elimination is used.

FilledSmallCircleDet uses modular methods and row reduction, constructing a result using the Chinese Remainder Theorem.

FilledSmallCircleEigenvalues works by interpolating the characteristic polynomial.

FilledSmallCircleMatrixExp uses Putzer's method or Jordan decomposition.

Basic System FeaturesAlgebra and Calculus