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:

    Under the dominion of an idea, which possesses the minds of multitudes, as civil freedom, or the religious sentiment, the power of persons are no longer subjects of calculation. A nation of men unanimously bent on freedom, or conquest, can easily confound the arithmetic of statists, and achieve extravagant actions, out of all proportion to their means; as, the Greeks, the Saracens, the Swiss, the Americans, and the French have done.
    Ralph Waldo Emerson (1803–1882)

    The mind is a finer body, and resumes its functions of feeding, digesting, absorbing, excluding, and generating, in a new and ethereal element. Here, in the brain, is all the process of alimentation repeated, in the acquiring, comparing, digesting, and assimilating of experience. Here again is the mystery of generation repeated.
    Ralph Waldo Emerson (1803–1882)