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:
“I believe if we introduced the Lord’s Prayer here, senators would propose a large number of amendments to it.”
—Henry Wilson (1812–1875)
“Everything to which we concede existence is a posit from the standpoint of a description of the theory-building process, and simultaneously real from the standpoint of the theory that is being built. Nor let us look down on the standpoint of the theory as make-believe; for we can never do better than occupy the standpoint of some theory or other, the best we can muster at the time.”
—Willard Van Orman Quine (b. 1908)