数学运算的计算复杂性
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 两个n位数 一个n+1位的数 Schoolbook addition
with carry Θ(n)
减 Subtraction 两个n位数 一个n+1位的数 Schoolbook
subtraction with
borrow Θ(n)
乘
Multiplication
两个n位数
2n位的数 Schoolbook long
multiplication O(n2)
Karatsuba algorithm O(n1.585)
3-way Toom–Cook
multiplication O(n1.465)
k-way Toom–Cook
multiplication O(nlog (2k − 1)/log k)
Mixed-level
Toom–Cook O(n 2√2 log n log n)
Schönhage–Strassen
algorithm O(nlog n log log n)
Fürer's algorithm O(n log n 2log* n)
除 Division 两个n位数 一个n位的数 Schoolbook long
division O(n2)
Newton–Raphson
division O(M(n))
Square root 一个n位数 一个n位的数 Newton's method O(M(n))
模幂Modular
exponentiation 两个n位数和一个k位的指数 一个n位的数 Repeated
multiplication and
reduction O(2kM(n))
Exponentiation by
squaring 幂的平方 O(k M(n))
Exponentiation with
Montgomery
reduction O(k M(n))
Schnorr and Stumpf conjectured that no fastest algorithm for multiplication exists. 乘法没有最快的算法。
代数函数
操作 输入 输出
算法 复杂度
Polynomial
evaluation
多项式评价 One polynomial
of degree n with
fixed-size
polynomial
coefficients One
fixed-size
number
一个固定大小的数 Direct evaluation
直接评估 Θ(n)
Horner's method
霍纳方法 Θ(n)
Polynomial gcd
(over Z[x] or F[x]) Two polynomials
of degree n with
fixed-size
polynomial
coefficients One polynomial
of degree at most
n Euclidean
algorithm
欧几里德算法 O(n2)
Fast Euclidean
algorithm O(n (log n)2 log log n)
特殊功能
基本功能
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 算法 Applicability 适用性 复杂度
Taylor series（泰勒级数）; repeated argument reduction exp ; log ; sin ; cos O(n1/2 M(n))
Taylor series; FFT-based acceleration exp ; log ; sin ; cos O(n1/3 (log n)2 M(n))
Taylor series; binary splitting + bit burst method exp ; log ; sin ; cos O((log n)2 M(n))
Arithmetic-geometric mean iteration 算术几何平局迭代 log 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
函数 输入 算法 Complexity复杂性
Gamma function
伽玛函数 n-digit number
一个n位数 Series approximation
of the incomplete
gamma function
不完全γ函数级数近似 O(n1/2 (log n)2 M(n))
Fixed rational number
确定的有理数 Hypergeometric series
几何级数 O((log n)2 M(n))
m/24, m an integer Arithmetic-geometric
mean iteration
算术-几何平均迭代 O(log n M(n))
Hypergeometric
function pFq
超几何函数 n-digit number (As described in
Borwein & Borwein) O(n1/2 (log n)2 M(n))
Fixed rational number Hypergeometric series
几何级数 O((log n)2 M(n))
数学常数Mathematical constants
This table gives the complexity of computing approximations to the given constants to n correct
digits.（这个表格给出了近似计算n的复杂度）
Constant 常数 Algorithm 算法 复杂度
Golden ratio, φ Newton's method O(M(n)
Square root of 2, √2 Newton's method O(M(n))
Euler's number, e Binary splitting of the Taylor series
for the exponential function O(log n M(n))
Newton inversion of the natural
logarithm O(log n M(n))
Pi, π Binary splitting of the arctan series
in Machin's formula O((log n)2 M(n))
Salamin–Brent algorithm O(log n M(n))
Euler's constant, γ Sweeney's method (approximation
in terms of the exponential integral) O((log n)2 M(n))