The time complexity of the Euclidean algorithm

Question

I can hardly decide how complicated the time complexity of the algorithm of the largest common denominator is Euclid. This algorithm in pseudo code:

function gcd(a, b) while b ≠ 0 t := b b := a mod b a := t return a 

It seems to depend on a and b. I believe the time complexity is O (a% b). It's right? Is there a better way to write this?

Answer 1

One trick to analyze the time complexity of the Euclidean algorithm is what happens during two iterations:

 a', b' := a % b, b % (a % b) 

Now a and b will decrease, not just one, which will simplify the analysis. You can divide it into cases:

• Tiny A: 2a <= b
• Tiny B: 2b <= a
• Small A: 2a > b , but a < b
• Little B: 2b > a but b < a
• Equals: a == b

Now we show that each individual case reduces the total a+b by at least a quarter:

• Tiny A: b % (a % b) < a and 2a <= b , so b decreases by at least half, therefore a+b decreases by at least 25%
• Tiny B: a % b < b and 2b <= a , so a decreases by at least half, so a+b decreases by at least 25%
• Small A: b will become ba , which is less than b/2 , decreasing a+b at least 25% .
• Little B: a will become ab , which is less than a/2 , decreasing a+b at least 25% .
• Equally: a+b drops to 0 , which, obviously, decreases a+b no less than 25% .

Therefore, when analyzing the case, each double step decreases a+b by at least 25% . The maximum number of times this can happen before a+b drops below 1 . The total number of steps ( S ), until we reach 0, must satisfy (4/3)^S <= A+B Now just execute it:

 (4/3)^S <= A+B S <= lg[4/3](A+B) S is O(lg[4/3](A+B)) S is O(lg(A+B)) S is O(lg(A*B)) //because A*B asymptotically greater than A+B S is O(lg(A)+lg(B)) //Input size N is lg(A) + lg(B) S is O(N) 

Thus, the number of iterations is linear in the number of input digits. For numbers that fit into the processor registers, it is reasonable to model iterations as a constant time and pretend that the total gcd runtime is linear.

Of course, if you are dealing with large integers, you must take into account the fact that the module operations in each iteration do not have a constant cost. Roughly speaking, the total asymptotic runtime will be 2 times the polylogarithmic factor. Something like n^2 lg(n) 2^O(log* n) . The polylogarithmic factor can be avoided by using binary gcd.

Answer 2

A suitable way to analyze an algorithm is to identify its worst-case scenarios. The Euclidean GCD worst case occurs when Fibonacci pairs are involved. void EGCD(fib[i], fib[i - 1]) , where i> 0.

For example, let me choose the case where the dividend is 55 and the divisor is 34 (recall that we are still dealing with Fibonacci numbers).

As you can see, this operation cost 8 iterations (or recursive calls).

Let's try to increase the Fibonacci numbers, namely 121393 and 75025. We can also notice here that for this it took 24 iterations (or recursive calls).

You may also notice that each iteration gives a Fibonacci number. That is why we have so many operations. We cannot get similar results only with Fibonacci numbers.

Therefore, the time complexity will be represented by a small O (upper bound), this time. The lower bound is intuitively omega (1): case 500 divided by 2, for example.

We solve the recurrence relation:

We can say that the Euclidean GCD can do the operation log (xy) no more .

Answer 3

Here you can look at the wikipedia article article .

It even has a nice plot of difficulty for pairs of meanings.

This is not O (a% b).

It is known (see article) that he will never take more steps than five times as many digits of a smaller number. Thus, the maximum number of steps grows as the number of digits (ln b). The cost of each step also grows as the number of digits, so the complexity is related to O (ln ^ 2 b), where b is the smaller nubmer. This is the upper limit, and the actual time is usually less.

Answer 4

See here .

In particular, this part:

Lame showed that the number of steps required to achieve the greatest common factor for two numbers less than n is

So O(log min(a, b)) is a good upper bound.

Answer 5

Here's an intuitive understanding of the complexity of the Euclidean algorithm. Formal proofs are covered in various texts, such as Introduction to Algorithms and TAOCP Vol 2.

First, think that if we tried to take gcd of two Fibonacci numbers F (k + 1) and F (k). You can quickly notice that the Euclidean algorithm iterates over F (k) and F (k-1). That is, with each iteration we move one number in the Fibonacci series. Since the Fibonacci numbers are O (Phi ^ k), where Phi is the golden ratio, we can see that the GCD execution time was O (log n), where n = max (a, b), and log has the base Phi. We can then prove that this would be the worst case if we notice that the Fibonacci numbers sequentially produce pairs, where the residues remain large enough at each iteration and never become zero until you reach the start of the series.

We can make O (log n), where n = max (a, b) are connected even more rigid. Suppose b> = a, so we can write in O (log b). First, note that GCD (ka, kb) = GCD (a, b). Since the largest values ​​of k are gcd (a, c), we can replace b with b / gcd (a, b) in our runtime, which will lead to a tighter O (log b / gcd (a, b)) binding.

Answer 6

The worst version of the Euclidean algorithm is when the residuals are the largest at each step, i.e. for two consecutive members of the Fibonacci sequence.

When n and m are the number of digits a and b, if n> = m, the algorithm uses O (m) divisions.

Note that complexity is always specified in terms of input sizes, in this case the number of digits.

Answer 7

However, for an iterative algorithm, we have:

 int iterativeEGCD(long long n, long long m) { long long a; int numberOfIterations = 0; while ( n != 0 ) { a = m; m = n; n = a % n; numberOfIterations ++; } printf("\nIterative GCD iterated %d times.", numberOfIterations); return m; } 

With Fibonacci pairs, there is no difference between iterativeEGCD() and iterativeEGCDForWorstCase() , where the latter is as follows:

 int iterativeEGCDForWorstCase(long long n, long long m) { long long a; int numberOfIterations = 0; while ( n != 0 ) { a = m; m = n; n = a - n; numberOfIterations ++; } printf("\nIterative GCD iterated %d times.", numberOfIterations); return m; } 

Yes, with Fibonacci pairs, n = a % n and n = a - n , this is exactly the same.

We also know that in an earlier answer to the same question there is a predominant decreasing factor: factor = m / (n % m) .

Therefore, in order to form an iterative version of the Euclidean GCD in a certain form, we can depict it as a “simulator” as follows:

 void iterativeGCDSimulator(long long x, long long y) { long long i; double factor = x / (double)(x % y); int numberOfIterations = 0; for ( i = x * y ; i >= 1 ; i = i / factor) { numberOfIterations ++; } printf("\nIterative GCD Simulator iterated %d times.", numberOfIterations); } 

Based on the work (last slide) of Dr. Jauhar Ali, the loop above is logarithmic.

Yes, little O, because the simulator reports no more iterations. Non-Fibonacci parties took fewer iterations than Fibonacci parties if they were tested on a Euclidean GCD.

Answer 8

Gabriel Lamé's theorem limits the number of steps in log (1 / sqrt (5) * (a + 1/2)) - 2, where the base of the log is (1 + sqrt (5)) / 2. This refers to the worst case scenario for the algorithm, and this happens when the inputs are Fibanoxy sequential numbers.

A slightly more liberal border: log a, where the log base (sqrt (2)) is implied by Koblitz.

For cryptographic purposes, we usually consider the bitwise complexity of the algorithms, taking into account that the bit size is set at approximately k = loga.

Here is a detailed analysis of the bitwise complexity of the Euclidean algorithm:

Although in most references the bitwise complexity of the Euclidean algorithm is given by O (loga) ^ 3, there is a more stringent estimate, which is O (loga) ^ 2.

Consider; r0 = a, r1 = b, r0 = q1.r1 + r2. ,, ri-1 = qi.ri + ri + 1,. ,, rm-2 = qm-1.rm-1 + rm rm-1 = qm.rm

note that: a = r0> = b = r1> r2> r3 ...> rm-1> rm> 0 .......... (1)

and rm is the greatest common factor of a and b.

According to the statement in the book of Koblitz (course in number theory and cryptography), it can be proved that: ri + 1 <(ri-1) / 2 ................. (2)

Again in Koblitz, the number of bit operations necessary to divide a k-bit positive integer by a 1-bit positive integer (provided k> = l) is specified as: (kl + 1) .l ....... ............ (3)

By (1) and (2), the number of divisions is O (loga), and therefore (3) the total complexity is O (loga) ^ 3.

Now this can be reduced to O (loga) ^ 2 remark in Koblitz.

consider ki = logri +1

by (1) and (2) we have: ki + 1 <= ki for i = 0,1, ..., m-2, m-1 and ki + 2 <= (ki) -1 for = 0,1 , ..., t-2

and (3) the total cost of m-divisions is limited: SUM [(ki-1) - ((ki) -1))] ki for i = 0,1,2, ..., t

rearranging this: SUM [(ki-1) - ((ki) -1))] * ki <= 4 * k0 ^ 2

Thus, the bitwise complexity of the Euclidean algorithm is O (loga) ^ 2.