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:
“How often should a woman be pregnant? Continually, or hardly ever? Or must there be a certain number of pregnancy anniversaries established by fashion? What do you, at the age of forty-three, have to say on the subject? Is it a fact that the laws of nature, or of the country, or of propriety, have ordained this time of life for sterility?”
—Philip Dormer Stanhope, 4th Earl Chesterfield (1694–1773)
“The theory of rights enables us to rise and overthrow obstacles, but not to found a strong and lasting accord between all the elements which compose the nation.”
—Giuseppe Mazzini (1805–1872)