유클리드 알고리즘의 시간 복잡성

유클리드 알고리즘의 시간 복잡성

---

Euclid의 최대 공통 분모 알고리즘의 시간 복잡도를 결정하는 데 어려움이 있습니다. 의사 코드의이 알고리즘은 다음과 같습니다.

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

a 와 b 에 의존하는 것 같습니다 . 내 생각은 시간 복잡도가 O (a % b)라는 것입니다. 그 맞습니까? 그것을 작성하는 더 좋은 방법이 있습니까?

---

Euclid 알고리즘의 시간 복잡성을 분석하는 한 가지 트릭은 두 번의 반복에서 발생하는 일을 따르는 것입니다.

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

이제 a와 b가 모두 감소하므로 분석이 더 쉬워집니다. 케이스로 나눌 수 있습니다.

• 작은 A : 2a <= b
• 작은 B : 2b <= a
• 작은 A : 2a > b하지만a < b
• 작은 B : 2b > a하지만b < a
• 같은: a == b

이제 모든 단일 케이스가 합계 a+b를 최소 1/4 만큼 감소시키는 것을 보여줍니다 .

• Tiny A : b % (a % b) < a및 2a <= b, 그래서 b최소한 절반으로 a+b감소 하므로 최소한25%
• Tiny B : a % b < b및 2b <= a, 그래서 a최소한 절반으로 a+b감소 하므로 최소한25%
• 작은 A는 : b될 것입니다 b-a보다 작은, b/2감소, a+b최소한으로 25%.
• 작은 B는 : a될 것입니다 a-b보다 작은, a/2감소, a+b최소한으로 25%.
• 같음 :로 a+b떨어집니다 0. 이는 분명히 a+b적어도 25%.

따라서 사례 분석에 따르면 모든 이중 단계 a+b는 최소한 25%. a+b아래로 떨어질 때까지이 문제가 발생할 수있는 최대 횟수가 있습니다 1. S0에 도달 할 때까지 의 총 단계 수 ( )는을 충족해야합니다 (4/3)^S <= A+B. 이제 작업하십시오.

(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)

따라서 반복 횟수는 입력 자릿수에서 선형입니다. cpu 레지스터에 맞는 숫자의 경우 반복을 일정한 시간으로 모델링 하고 gcd 의 총 실행 시간이 선형 인 척하는 것이 합리적 입니다.

물론, 큰 정수를 다루는 경우 각 반복 내의 모듈러스 연산에 일정한 비용이 발생하지 않는다는 사실을 고려해야합니다. 대략적으로 말하면 총 점근 적 실행 시간은 다대수 인자의 n ^ 2 배가 될 것입니다. 같은 것 n^2 lg(n) 2^O(log* n) . 대신 이진 gcd 를 사용하여 다대수 인자를 피할 수 있습니다 .

---

알고리즘을 분석하는 적절한 방법은 최악의 시나리오를 결정하는 것입니다. 유클리드 GCD의 최악의 경우는 피보나치 쌍이 관련 될 때 발생합니다. void EGCD(fib[i], fib[i - 1]), 여기서 i> 0.

예를 들어, 배당이 55이고 제수가 34 인 경우를 선택해 봅시다 (우리는 여전히 피보나치 수를 처리하고 있음을 기억하십시오).

아시다시피이 작업에는 8 번의 반복 (또는 재귀 호출)이 필요했습니다.

Let's try larger Fibonacci numbers, namely 121393 and 75025. We can notice here as well that it took 24 iterations (or recursive calls).

You can also notice that each iterations yields a Fibonacci number. That's why we have so many operations. We can't obtain similar results only with Fibonacci numbers indeed.

Hence, the time complexity is going to be represented by small Oh (upper bound), this time. The lower bound is intuitively Omega(1): case of 500 divided by 2, for instance.

Let's solve the recurrence relation:

We may say then that Euclidean GCD can make log(xy) operation at most.

---

There's a great look at this on the wikipedia article.

It even has a nice plot of complexity for value pairs.

It is not O(a%b).

It is known (see article) that it will never take more steps than five times the number of digits in the smaller number. So the max 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 bound by O(ln^2 b) where b is the smaller number. That's an upper limit, and the actual time is usually less.

---

See here.

In particular this part:

Lamé showed that the number of steps needed to arrive at the greatest common divisor for two numbers less than n is

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

---

Here's intuitive understanding of runtime complexity of Euclid's algorithm. The formal proofs are covered in various texts such as Introduction to Algorithms and TAOCP Vol 2.

First think about what if we tried to take gcd of two Fibonacci numbers F(k+1) and F(k). You might quickly observe that Euclid's algorithm iterates on to F(k) and F(k-1). That is, with each iteration we move down one number in Fibonacci series. As Fibonacci numbers are O(Phi ^ k) where Phi is golden ratio, we can see that runtime of GCD was O(log n) where n=max(a, b) and log has base of Phi. Next, we can prove that this would be the worst case by observing that Fibonacci numbers consistently produces pairs where the remainders remains large enough in each iteration and never become zero until you have arrived at the start of the series.

We can make O(log n) where n=max(a, b) bound even more tighter. Assume that b >= a so we can write bound at O(log b). First, observe that GCD(ka, kb) = GCD(a, b). As biggest values of k is gcd(a,c), we can replace b with b/gcd(a,b) in our runtime leading to more tighter bound of O(log b/gcd(a,b)).

---

The worst case of Euclid Algorithm is when the remainders are the biggest possible at each step, ie. for two consecutive terms of the Fibonacci sequence.

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

Note that complexities are always given in terms of the sizes of inputs, in this case the number of digits.

---

Worst case will arise when both n and m are consecutive Fibonacci numbers.

gcd(Fn,Fn−1)=gcd(Fn−1,Fn−2)=⋯=gcd(F1,F0)=1 and nth Fibonacci number is 1.618^n, where 1.618 is the Golden ratio.

So, to find gcd(n,m), number of recursive calls will be Θ(logn).

---

For the iterative algorithm, however, 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 looks like the following:

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, it is exactly the same thing.

We also know that, in an earlier response for the same question, there is a prevailing decreasing factor: factor = m / (n % m).

Therefore, to shape the iterative version of the Euclidean GCD in a defined form, we may depict as a "simulator" like this:

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, small Oh because the simulator tells the number of iterations at most. Non Fibonacci pairs would take a lesser number of iterations than Fibonacci, when probed on Euclidean GCD.

---

Gabriel Lame's Theorem bounds the number of steps by log(1/sqrt(5)*(a+1/2))-2, where the base of the log is (1+sqrt(5))/2. This is for the the worst case scenerio for the algorithm and it occurs when the inputs are consecutive Fibanocci numbers.

A slightly more liberal bound is: log a, where the base of the log is (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 given approximately by k=loga.

Here is a detailed analysis of the bitwise complexity of Euclid Algorith:

Although in most references the bitwise complexity of Euclid Algorithm is given by O(loga)^3 there exists a tighter bound 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

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

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

By a Claim in Koblitz's book( A course in number Theory and Cryptography) is can be proven that: ri+1<(ri-1)/2 .................(2)

Again in Koblitz the number of bit operations required to divide a k-bit positive integer by an l-bit positive integer (assuming k>=l) is given as: (k-l+1).l ...................(3)

By (1) and (2) the number of divisons is O(loga) and so by (3) the total complexity is O(loga)^3.

Now this may be reduced to O(loga)^2 by a remark in Koblitz.

consider ki= logri +1

(1)과 (2)에 의해 우리는 i = 0,1, ..., m-2, m-1의 경우 ki + 1 <= ki, i = 0의 경우 ki + 2 <= (ki) -1 , 1, ..., m-2

(3) m 디비전의 총 비용은 i = 0,1,2, .., m에 대해 SUM [(ki-1)-((ki) -1))] * ki로 제한됩니다.

재정렬하기 : SUM [(ki-1)-((ki) -1))] * ki <= 4 * k0 ^ 2

따라서 Euclid 알고리즘의 비트 복잡도는 O (loga) ^ 2입니다.

참고 URL : https://stackoverflow.com/questions/3980416/time-complexity-of-euclids-algorithm