Number Theory
Algorithms for number theoretical calculations are studied in computational number theory.
| Operation | Input | Output | Algorithm | Complexity |
|---|---|---|---|---|
| Greatest common divisor | Two n-digit numbers | One number with at most n digits | Euclidean algorithm | O(n2) |
| Binary GCD algorithm | O(n2) | |||
| Left/right k-ary binary GCD algorithm | O(n2/ log n) | |||
| Stehlé–Zimmermann algorithm | O(log n M(n)) | |||
| Schönhage controlled Euclidean descent algorithm | O(log n M(n)) | |||
| Jacobi symbol | Two n-digit numbers | 0, −1, or 1 | ||
| Schönhage controlled Euclidean descent algorithm | O(log n M(n)) | |||
| Stehlé–Zimmermann algorithm | O(log n M(n)) | |||
| Factorial | A fixed-size number m | One O(m log m)-digit number | Bottom-up multiplication | O(m2 log m) |
| Binary splitting | O(log m M(m log m)) | |||
| Exponentiation of the prime factors of m | O(log log m M(m log m)), O(M(m log m)) |
Read more about this topic: Computational Complexity Of Mathematical Operations
Famous quotes containing the words number and/or theory:
“In view of the fact that the number of people living too long has risen catastrophically and still continues to rise.... Question: Must we live as long as modern medicine enables us to?... We control our entry into life, it is time we began to control our exit.”
—Max Frisch (1911–1991)
“There could be no fairer destiny for any physical theory than that it should point the way to a more comprehensive theory in which it lives on as a limiting case.”
—Albert Einstein (1879–1955)