Elementary and Special Functions
- Summation:
- Kahan summation algorithm
- Pairwise summation — slightly worse than Kahan summation but cheaper
- Binary splitting
- Multiplication:
- Multiplication algorithm — general discussion, simple methods
- Karatsuba algorithm — the first algorithm which is faster than straightforward multiplication
- Toom–Cook multiplication — generalization of Karatsuba multiplication
- Schönhage–Strassen algorithm — based on Fourier transform, asymptotically very fast
- Fürer's algorithm — asymptotically slightly faster than Schönhage–Strassen
- Exponentiation:
- Exponentiation by squaring
- Addition-chain exponentiation
- Polynomials:
- Horner's method
- Estrin's scheme — modification of the Horner scheme with more possibilities for parallellization
- Clenshaw algorithm
- De Casteljau's algorithm
- Square roots and other roots:
- Integer square root
- Methods of computing square roots
- nth root algorithm
- Shifting nth root algorithm — similar to long division
- hypot — the function (x2 + y2)1/2
- Alpha max plus beta min algorithm — approximates hypot(x,y)
- Fast inverse square root — calculates 1 / √x using details of the IEEE floating-point system
- Elementary functions (exponential, logarithm, trigonometric functions):
- Trigonometric tables — different methods for generating them
- CORDIC — shift-and-add algorithm using a table of arc tangents
- BKM algorithm — shift-and-add algorithm using a table of logarithms and complex numbers
- Gamma function:
- Lanczos approximation
- Spouge's approximation — modification of Stirling's approximation; easier to apply than Lanczos
- AGM method — computes arithmetic–geometric mean; related methods compute special functions
- FEE method (Fast E-function Evaluation) — fast summation of series like the power series for ex
- Gal's accurate tables — table of function values with unequal spacing to reduce round-off error
- Spigot algorithm — algorithms that can compute individual digits of a real number
- Approximations of π:
- Liu Hui's π algorithm — first algorithm that can compute π to arbitrary precision
- Leibniz formula for π — alternating series with very slow convergence
- Wallis product — infinite product converging slowly to π/2
- Gauss–Legendre algorithm — iteration which converges quadratically to π, based on arithmetic–geometric mean
- Borwein's algorithm — iteration which converges quartically to 1/π, and other algorithms
- Chudnovsky algorithm — fast algorithm that calculates a hypergeometric series
- Bailey–Borwein–Plouffe formula — can be used to compute individual hexadecimal digits of π
- Bellard's formula — faster version of Bailey–Borwein–Plouffe formula
- List of formulae involving π
Read more about this topic: List Of Numerical Analysis Topics
Famous quotes containing the words elementary, special and/or functions:
“Listen. We converse as we live—by repeating, by combining and recombining a few elements over and over again just as nature does when of elementary particles it builds a world.”
—William Gass (b. 1924)
“It is surely a matter of common observation that a man who knows no one thing intimately has no views worth hearing on things in general. The farmer philosophizes in terms of crops, soils, markets, and implements, the mechanic generalizes his experiences of wood and iron, the seaman reaches similar conclusions by his own special road; and if the scholar keeps pace with these it must be by an equally virile productivity.”
—Charles Horton Cooley (1864–1929)
“In today’s world parents find themselves at the mercy of a society which imposes pressures and priorities that allow neither time nor place for meaningful activities and relations between children and adults, which downgrade the role of parents and the functions of parenthood, and which prevent the parent from doing things he wants to do as a guide, friend, and companion to his children.”
—Urie Bronfenbrenner (b. 1917)