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:
“There are crimes which become innocent and even glorious through their splendor, number and excess.”
—François, Duc De La Rochefoucauld (1613–1680)
“The things that will destroy America are prosperity-at-any- price, peace-at-any-price, safety-first instead of duty-first, the love of soft living, and the get-rich-quick theory of life.”
—Theodore Roosevelt (1858–1919)