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:
“Nothing ever prepares a couple for having a baby, especially the first one. And even baby number two or three, the surprises and challenges, the cosmic curve balls, keep on coming. We can’t believe how much children change everything—the time we rise and the time we go to bed; the way we fight and the way we get along. Even when, and if, we make love.”
—Susan Lapinski (20th century)
“The theory of the Communists may be summed up in the single sentence: Abolition of private property.”
—Karl Marx (1818–1883)