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:

    Without claiming superiority of intellectual over visual understanding, one is nevertheless bound to admit that the cinema allows a number of æsthetic-intellectual means of perception to remain unexercised which cannot but lead to a weakening of judgment.
    Johan Huizinga (1872–1945)

    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)