int gcd(int a, int b) { return (b==0 ? a : gcd(b,a%b)); }
http://en.wikipedia.org/wiki/Euclidean_algorithm
On 8/17/07, Muntasir Azam Khan <[EMAIL PROTECTED]> wrote:
>
>
> On Aug 17, 6:53 pm, anshu <[EMAIL PROTECTED]> wrote:
> > Do you think sorting would help here?
> > I mean, arranging the numbers in descending order and then computing
> > progressively.
> >
> > Why I am suggesting sorting is that considering an array like the
> > following
> > 2, 80, 36, 70, 150, 300
> > It would be pretty expensive to do the euclidean algo first with
> > gcd(2, 80 ) = 2 --- O(40)
> > gcd(2, 36 )= 2 -- O(18)
> > gcd(2 , 70) =
> > gcd(2, 150)
> >
> > vs
> > gcd(150, 300) = 150
> > gcd(70,150) = 10
> > etc..
>
> I don't know, but this is easily found by running tests on sorted vs
> unsorted input.
> I don't think this really matters much, unless you are using really
> big numbers, and even then I am not sure.
>
> Muntasir
>
>
>
> >
>
--~--~---------~--~----~------------~-------~--~----~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
