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)
“Adolescents, for all their self-involvement, are emerging from the self-centeredness of childhood. Their perception of other people has more depth. They are better equipped at appreciating others’ reasons for action, or the basis of others’ emotions. But this maturity functions in a piecemeal fashion. They show more understanding of their friends, but not of their teachers.”
—Terri Apter (20th century)