Computational Complexity of Mathematical Operations - Arithmetic Functions

Arithmetic Functions

Operation Input Output Algorithm Complexity
Addition Two n-digit numbers One n+1-digit number Schoolbook addition with carry Θ(n)
Subtraction Two n-digit numbers One n+1-digit number Schoolbook subtraction with borrow Θ(n)
Multiplication Two n-digit numbers
One 2n-digit number 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 (Knuth 4.3.3-T) O(n 2√2 log n log n)
Schönhage–Strassen algorithm O(n log n log log n)
Fürer's algorithm O(n log n 2log* n)
Division Two n-digit numbers One n-digit number Schoolbook long division O(n2)
Newton–Raphson division O(M(n))
Square root One n-digit number One n-digit number Newton's method O(M(n))
Modular exponentiation Two n-digit numbers and a k-bit exponent One n-digit number 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.

Read more about this topic:  Computational Complexity Of Mathematical Operations

Famous quotes containing the words arithmetic and/or functions:

    I hope I may claim in the present work to have made it probable that the laws of arithmetic are analytic judgments and consequently a priori. Arithmetic thus becomes simply a development of logic, and every proposition of arithmetic a law of logic, albeit a derivative one. To apply arithmetic in the physical sciences is to bring logic to bear on observed facts; calculation becomes deduction.
    Gottlob Frege (1848–1925)

    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)