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)
“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)