Computational Complexity of Mathematical Operations - Number Theory

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:

    [The] elderly and timid single gentleman in Paris ... never drove down the Champs Elysees without expecting an accident, and commonly witnessing one; or found himself in the neighborhood of an official without calculating the chances of a bomb. So long as the rates of progress held good, these bombs would double in force and number every ten years.
    Henry Brooks Adams (1838–1918)

    The theory [before the twentieth century] ... was that all the jobs in the world belonged by right to men, and that only men were by nature entitled to wages. If a woman earned money, outside domestic service, it was because some misfortune had deprived her of masculine protection.
    Rheta Childe Dorr (1866–1948)