List of Numerical Analysis Topics - Elementary and Special Functions

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 π