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:
“O! O! another stroke! that makes the third.
He stabs me to the heart against my wish.
If that be so, thy state of health is poor;
But thine arithmetic is quite correct.”
—A.E. (Alfred Edward)
“When Western people train the mind, the focus is generally on the left hemisphere of the cortex, which is the portion of the brain that is concerned with words and numbers. We enhance the logical, bounded, linear functions of the mind. In the East, exercises of this sort are for the purpose of getting in tune with the unconscious—to get rid of boundaries, not to create them.”
—Edward T. Hall (b. 1914)