3

What is the bit-complexity invloved in calculating the greatest common divisor of two n-bit values x and y using Euclids Extended algorithm i.e. the complexity in terms of n

I observed the following pattern while calculating the GCD using a standard Extended Euclid Algorithm in the worst cases for different bit size. enter image description here

The complexity in terms of the magnitude of the two values x and y is close to the value:

enter image description here

Source

How do arrive at the theoretical bit-complexity to verify my observations?

Tabish Mir
  • 717
  • 6
  • 26
  • 3
    The cited formula does not seem to be correct. Have a look for example here: https://math.stackexchange.com/questions/258596/what-is-the-time-complexity-of-euclids-algorithm-upper-bound-lower-bound-and-a Also, the "extended" is irrelevant for the asymptotic complexity. It contributes just a constant factor. – Henry Feb 21 '19 at 12:34

1 Answers1

7

I hope you're fitting to the peaks, since you're looking for worst-case complexity.

Anyway...

If a and b are N bits long, then in the worst case (Fibonacci pairs), the extended Euclidean algorithm will take O(N) iterations.

Let f(N) be the cost of a single iteration. Certainly f(N) will be at least linear, but still polynomial, and nearly half of the iterations in each case will involve arguments at least N/2 bits long, so the total complexity will be in O(N * f(N))

Now, what exactly f(N) is will depend in the particulars of how large-integer operations are implemented in your library. The division/remainder operation will dominate, although wikipedia says that if you use Newton–Raphson division then the complexity of that is the same as multiplication (although there will certainly be a constant multiplier!).

Multiplication costs O(N * log N * log log N) in the limit with the Schönhage–Strassen, and hopefully your library will use that eventually... so when the numbers get really big, the extended Euclidean algorithm should take O(N2 * log N * log log N) in the worst case.

Matt Timmermans
  • 53,709
  • 3
  • 46
  • 87