数学运算的计算复杂性

数学运算的计算复杂性

The following tables list the running time of various algorithms for common mathematical operations. Here, complexity refers to the time complexity of performing computations on a multitape Turing machine.[1] See big O notation for an explanation of the notation used. 算术函数（Arithmetic functions）

操作 加 Addition 减 Subtraction 输入 两个n位数 两个n位数 输出 一个n+1位的数 一个n+1位的数 算法 Schoolbook addition Θ(n) with carry Schoolbook subtraction borrow Schoolbook multiplication Karatsuba algorithm 3-way k-way O(n1.585复杂度 Θ(n) with long O(n2) ) 2n位的数 Toom–Cook O(n1.465) Toom–Cook O(nlog (2k ? 1)/log k) O(n 2√2 log nmultiplication multiplication Mixed-level Toom–Cook Sch?nhage–Strassen O(nlog n log log n) algorithm Fürer's algorithm O(n log n 2log* n乘 Multiplication 两个n位数 log n) ) 除 Division 两个n位数 一个n位的数 Schoolbook division long O(n2) O(M(n)) O(M(n)) O(2M(n)) and kNewton–Raphson division Newton's method Repeated multiplication reduction Exponentiation Square root 模幂一个n位数 一个n位的数 一个n位的数 Modular 两个n位数和一个k位的指数 exponentiation by O(k M(n)) squaring 幂的平方 Exponentiation Montgomery reduction with O(k M(n)) Schnorr and Stumpf conjectured that no fastest algorithm for multiplication exists.

乘法没有最快的算法。

代数函数

操作 Polynomial evaluation 多项式评价 输入 输出 算法 复杂度 Θ(n) One polynomial One fixed-size Direct evaluation of degree n with number 直接评估 fixed-size 一个固定大小的数 polynomial Horner's method coefficients 霍纳方法 Euclidean algorithm 欧几里德算法 Θ(n) Polynomial gcd Two polynomials One polynomial (over Z[x] or F[x]) of degree n with of degree at most fixed-size n polynomial coefficients O(n) 2Fast Euclidean O(n (log n)2 log log n) algorithm

特殊功能

基本功能

The elementary functions are constructed by composing arithmetic operations, the exponential function (exp), the natural logarithm (log), trigonometric functions (sin, cos), and their inverses.（初等函数是由指数函数；自然对数；三角函数，以及他们的反函数） The complexity of an elementary function is

equivalent to that of its inverse,（初等函数的复杂度与其反函数是一样的） since all elementary functions are analytic and hence invertible（可逆的） by means of Newton's method. In particular, if either exp or log can be computed with some complexity, then that complexity is attainable for all other elementary functions.

Below, the size n refers to the number of digits of precision at which the function is to be evaluated.

（n涉及到对函数进行评估的精度） Algorithms 算法 Taylor series（泰勒级数）; repeated argument reduction Taylor series; FFT-based acceleration Taylor series; binary splitting + bit burst method Arithmetic-geometric mean iteration 算术几何平局迭代 Applicability 适用性 exp ; log ; sin ; cos exp ; log ; sin ; cos exp ; log ; sin ; cos log 复杂度 O(nO(n1/21/3 M(n)) (log n) M(n)) 22O((log n) M(n)) O(log n M(n)) It is not known whether O(log n M ( n )) is the optimal complexity for elementary functions. The best known lower bound is the trivial bound Ω( M ( n )).

(并不能确定O(log n M ( n )) 是不是初等函数的最佳复杂度，最公认的下界是非渐近紧确的 Ω( M ( n )) )

非初等函数Non-elementary functions

函数 Gamma function 伽玛函数 输入 n-digit number 一个n位数 算法 Complexity复杂性 Series approximation O(n1/2 (log n)2 M(n)) of the incomplete gamma function 不完全γ函数级数近似 Fixed rational number 确定的有理数 Hypergeometric series O((log n)2 M(n)) 几何级数 Arithmetic-geometric O(log n M(n)) mean iteration 算术-几何平均迭代 (As described in O(n1/2 (log n)2 M(n)) Borwein & Borwein) Hypergeometric series O((log n)2 M(n)) 几何级数 m/24, m an integer Hypergeometric function pFq 超几何函数 n-digit number Fixed rational number 数学常数Mathematical constants This table gives the complexity of computing approximations to the given constants to n correct digits.（这个表格给出了近似计算n的复杂度）

Constant 常数 Algorithm 算法 Newton's method 复杂度 Golden ratio, φ Square root of 2, √2 Euler's number, e O(M(n) Newton's method O(M(n)) Binary splitting of the Taylor series O(log n M(n)) for the exponential function Newton inversion of the natural O(log n M(n)) logarithm Pi, π Binary splitting of the arctan series O((log n)2 M(n)) in Machin's formula Salamin–Brent algorithm O(log n M(n)) Euler's constant, γ Sweeney's method (approximation O((log n)2 M(n)) in terms of the exponential integral) 数论

Algorithms for number theoretical calculations are studied in computational number theory. Operation操作 最大公约数Greatest common divisor 输入 两个n位数 输出 一个最多为n位的数 One number with at most n digits 算法 复杂度 Euclidean algorithm O(n2) 欧几里得算法 Binary algorithm GCD O(n2) 二进制GCD算法 Left/right binary k-ary O(n2/ log n) GCD algorithm左右k元二进制GCD算法 Stehlé–Zimmermann O(log n M(n)) algorithm Sch?nhage O(log n M(n)) controlled Euclidean descent algorithm Sch?nhage O(log nM(n)) controlled Euclidean descent algorithm Stehlé–Zimmermann O(log nM(n)) algorithm 施特勒齐默尔曼算法 Jacobi symbol 雅可比符号 Two n-digit numbers 0 或 1 或 -1 两个n位数 Factorial 阶乘 A fixed-size number m One O(m log m)-digit 一个固定大小的number 数m Bottom-up multiplication 自下向上的乘法 Binary splitting 二进位分裂 O(m2 log m) O(log mM(m log m)) Exponentiation of O(log log mM(m the prime factors of log m)), m O(M(m log m))