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:

    There is something tragic about the enormous number of young men there are in England at the present moment who start life with perfect profiles, and end by adopting some useful profession.
    Oscar Wilde (1854–1900)

    Could Shakespeare give a theory of Shakespeare?
    Ralph Waldo Emerson (1803–1882)