@Shady: I really haven't studied the complexity of the binary gcd algorithm. It is well known that the complexity of Euclid's algorithm is O(log_phi(max(a,b))), where phi is the golden ratio: phi = (1 + sqrt(5)) / 2, with the worst case being two consecutive Fibonacci numbers. E.g., Euclid's algorithm applied to (55,34) gives the sequence (34,21), (21,13), (13,8), (8,5), (5,3), (3,2), (2,1), (1,0). Each of these takes a modulus (%) operation, for a total of 8. The binary gcd algorithm applied to the same numbers produces the sequence (55,17), (38,17), (19,17), (2,17), (1,17), (1,16), (1,8), (1,4), (1,2), (1,1), (1,0), for a total of 11 logical operations.
Here is a modulus algorithm, adapted from a division algorithm in a previous posting of mine (http://groups.google.com/group/algogeeks/ msg/735671f6a1e16eec): int modulus(int a, int b) / / returns a%b, a>= 0 and b > 0 is assumed. { int k=0; // shift divisor to align with dividend while( b <= a ) { b <<= 1; ++k; } // perform k steps of long division in binary, don't need the quotient for( ; k ; --k ) { b >>= 1; if( a >= b ) a -= b; } return a; } If there is no hardware division instruction, the work of one invocation of the modulus function may be about the same as the entire binary gcd algorithm. Dave On Sep 10, 11:56 am, shady <sinv...@gmail.com> wrote: > @dave no doubt division is costly, but will time complexity change in your > case ? > > On Sat, Sep 10, 2011 at 10:25 PM, Neha Singh > <neha.ndelhi.1...@gmail.com>wrote: > > > > > the time complexity of my approach : O(a*b)^2 > > and of the other approach, i guess : O(a) , where a is the larger no. > > correct me if i m wrong > > > So, complexity wise my approach does not seem to be gud > > > -- > > You received this message because you are subscribed to the Google Groups > > "Algorithm Geeks" group. > > To post to this group, send email to algogeeks@googlegroups.com. > > To unsubscribe from this group, send email to > > algogeeks+unsubscr...@googlegroups.com. > > For more options, visit this group at > >http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text - > > - Show quoted text - -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
