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:

    Today, almost forty years later, I grow dizzy when I recall that the number of manufactured tanks seems to have been more important to me than the vanished victims of racism.
    Albert Speer (1905–1981)

    A theory of the middle class: that it is not to be determined by its financial situation but rather by its relation to government. That is, one could shade down from an actual ruling or governing class to a class hopelessly out of relation to government, thinking of gov’t as beyond its control, of itself as wholly controlled by gov’t. Somewhere in between and in gradations is the group that has the sense that gov’t exists for it, and shapes its consciousness accordingly.
    Lionel Trilling (1905–1975)