[Computation of] mathematical functions

The number of bit operations needed to add two n-digit numbers is of order n. The number of operations m[n] needed to multiply them increases just slightly more rapidly than n (see page 1093). (Even if one can do operations on all digits in parallel it still takes of order n steps in a system like a cellular automaton for the effects of different digits to mix together—though see also page 1149.) The number of operations to evaluate Mod[a, b] is of order n if a has n digits and b is small. Many standard continuous mathematical functions just increase or decrease smoothly at large x (see page 917). The main issue in evaluating those that exhibit regular oscillations at large x is to find their oscillation period with sufficient precision. Thus for example if x is an integer with n digits then evaluating Sin[x] or FractionalPart[x c] requires respectively finding π or c to n-digit precision. It is known how to evaluate π (see page 912) and all standard elementary functions to n-digit precision using about Log[n] m[n] operations. (This can be done by repeatedly making use of functional relations such as Exp[2x]  Exp[x]² which express f[2x] as a polynomial in f[x]; such an approach is known to work for elementary, elliptic, modular and other functions associated with ArithmeticGeometricMean and for example DedekindEta.) Known methods for high-precision evaluation of special functions—usually based in the end on series representations—typically require of order n^1/s m[n] operations, where s is often 2 or 3. (Examples of more difficult cases include HypergeometricPFQ[a, b, 1] and StieltjesGamma[k], where logarithmic series can require an exponential number of terms. Evaluation of BernoulliB[x] is also difficult.) Any iterative procedure (such as FindRoot) that yields a constant multiple more digits at each step will take about Log[n] steps to get n digits. Roots of polynomials can thus almost always be found with NSolve in about Log[n] m[n] operations. If one evaluates NIntegrate or NDSolve by effectively fitting functions to order s polynomials the difficulty of getting results with n-digit precision typically increases like 2^n/s. An adaptive algorithm such as Romberg integration reduces this to about 2^√n. The best-known algorithms for evaluating Zeta[1/2 +  x] (see page 918) to fixed precision take roughly √x operations—or 2^n/2 operations if x is an n-digit integer. (The evaluation is based on the Riemann–Siegel formula, which involves sums of about √x cosines.) Unlike for continuous mathematical functions, known algorithms for number theoretical functions such as FactorInteger[x] or MoebiusMu[x] typically seem to require a number of operations that grows faster with the number of digits n in x than any power of n (see page 1090).