Time complexity of Euclid s Algorithm

Question

I am having difficulty deciding what the time complexity of Euclid s greatest common denominator algorithm is  This algorithm in pseudo-code is   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  My thinking is that the time complexity is O a   b   Is that correct  Is there a better way to write that

User · Answer

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.

User · Answer

Here is the analysis in the book Data Structures and Algorithm Analysis in C by Mark Allen Weiss  second edition  2 4 4       Euclid s algorithm works by continually computing remainders until 0 is reached  The last nonzero remainder is the answer     Here is the code   unsigned int Gcd unsigned int M  unsigned int N         unsigned int Rem      while  N  gt  0            Rem   M   N          M   N          N   Rem            Return M      Here is a THEOREM that we are going to use      If M   N  then M mod N  lt  M 2    PROOF      There are two cases  If N  lt   M 2  then since the remainder is smaller   than N  the theorem is true for this case  The other case is N   M 2    But then N goes into M once with a remainder M - N  lt  M 2  proving the   theorem    So  we can make the following inference   Variables    M      N      Rem  initial      M      N      M N  1 iteration  N     M N    N  M N   2 iterations M N  N  M N   M N   N  M N    lt   M N  2      So  after two iterations  the remainder is at most half of its original value  This would show that the number of iterations is at most 2logN   O logN        Note that  the algorithm computes Gcd M N   assuming M    N  If N   M  the first iteration of the loop swaps them

User · Answer

The suitable way to analyze an algorithm is by determining its worst case scenarios  Euclidean GCD s worst case occurs when Fibonacci Pairs are involved  void EGCD fib i   fib i - 1    where i   0   For instance  let s opt for the case where the dividend is 55  and the divisor is 34  recall that we are still dealing with fibonacci numbers      As you may notice  this operation costed 8 iterations  or recursive calls    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

User · Answer

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

User · Answer

One trick for analyzing the time complexity of Euclid s algorithm is to follow what happens over two iterations   a   b     a   b  b    a   b    Now a and b will both decrease  instead of only one  which makes the analysis easier  You can divide it into cases    Tiny A  2a  lt   b Tiny B  2b  lt   a Small A  2a  gt  b but a  lt  b Small B  2b  gt  a but b  lt  a Equal  a    b   Now we ll show that every single case decreases the total a b by at least a quarter    Tiny A  b    a   b   lt  a and 2a  lt   b  so b is decreased by at least half  so a b decreased by at least 25  Tiny B  a   b  lt  b and 2b  lt   a  so a is decreased by at least half  so a b decreased by at least 25  Small A  b will become b-a  which is less than b 2  decreasing a b by at least 25   Small B  a will become a-b  which is less than a 2  decreasing a b by at least 25   Equal  a b drops to 0  which is obviously decreasing a b by at least 25     Therefore  by case analysis  every double-step decreases a b by at least 25   There s a maximum number of times this can happen before a b is forced to drop below 1  The total number of steps  S  until we hit 0 must satisfy  4 3  S  lt   A B  Now just work it    4 3  S  lt   A B S  lt   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    So the number of iterations is linear in the number of input digits  For numbers that fit into cpu registers  it s reasonable to model the iterations as taking constant time and pretend that the total running time of the gcd is linear   Of course  if you re dealing with big integers  you must account for the fact that the modulus operations within each iteration don t have a constant cost  Roughly speaking  the total asymptotic runtime is going to be n 2 times a polylogarithmic factor  Something like n 2 lg n  2 O log  n   The polylogarithmic factor can be avoided by instead using a binary gcd

User · Answer

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 lt  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  by  1  and  2  we have  ki 1 lt  ki for i 0 1     m-2 m-1 and ki 2 lt   ki -1 for i 0 1     m-2  and by  3  the total cost of the m divisons is bounded by  SUM   ki-1 -  ki -1    ki for i 0 1 2    m  rearranging this  SUM   ki-1 -  ki -1    ki lt  4 k0 2  So the bitwise complexity of Euclid s Algorithm is O loga  2

User · Answer

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  T logn

User · Answer

At every step  there are two cases  b    a   2  then a  b   b  a   b will make b at most half of its previous value  b  lt  a   2  then a  b   b  a   b will make a at most half of its previous value  since b is less than a   2  So at every step  the algorithm will reduce at least one number to at least half less   In at most O log a  O log b  step  this will be reduced to the simple cases  Which yield an O log n  algorithm  where n is the upper limit of a and b   I have found it here

User · Answer

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  gt   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

User · Answer

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

User · Answer

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

[algorithm] Time complexity of Euclid's Algorithm

Examples related to algorithm

Examples related to big-o

Examples related to time-complexity

Examples related to iteration