famous algorithm

[nonevent99]

Let's see how good your cerebral hash functions are...

What's the name of that famous math algorithm where you take two numbers x and y, mod one by the other to get z, and then discard max(x,y) so now you're left with x' = min(x,y) and z.

Repeat process with x' and z until one of the numbers in your hand is 1. The other is X.

What number X do you end up with? What is the running time?

[Laks]

The GCD - Euclids Algo......... :-)

Running time... hmmm....
ceil(max(a,b)/min(a,b)) ?????

Cheers'
Laks

[AlbaLed]

[/size]Originally posted by nonevent99

Let's see how good your cerebral hash functions are...

What's the name of that famous math algorithm where you take two numbers x and y, mod one by the other to get z, and then discard max(x,y) so now you're left with x' = min(x,y) and z.

Should this be you take the big mod small ? Because if you do small mod big = small and then discard big you're left with (small, small)
Repeat process with x' and z until one of the numbers in your hand is 1. The other is X.

Should this be stop at 0?
Assuming you have to do big mod small
Consider (18, 4)
z = 18 mod 4 = 2
then we have (2, 4)
z = 4 mod 2 = 0
so now we have (0, 2)
if we keep doing there is going to be some error since 2 mod 0 is is undefined since 2/0 is undefined


What number X do you end up with? What is the running time?
[/size]

[nonevent99]

Let's see, AlbaLed. I think I did have a typo, but here's a link that should clear it up:

http://www.cut-the-knot.org/blue/binary.shtml

The algorithm is called Euclid's algorithm, andt can be used to find the GCD of two positive integers. It is a "classic numerical algorithm" in the sense of CS AGRE IV.B.2.

The examples below demonstrate the algorithm:

Find the gcd of 10 and 8. Well, 10 % 8 (per Alba's correction, not 8 % 10) is 2. So now you have 8 and 2. 8 % 2 is 2. So now you have 2 and 2. And 2 % 2 = 1. And 2 % 1 = 0. 2 must be the GCD.

Find the gcd of 144 and 282. Well, 282 % 144 = 138. 144 % 138 = 6. 138 % 6 = 0. So the GCD must be 6.

[As an aside, the product of 144 and 282 is 40608, which is 6768. Since gcd(a,b) * lcd(a,b) = a*b, the lcd(144,282) must be 6768. SO Euclid's algorithm indirectly gives you a handy way of computing LCDs, also.]

As for the run-time of the algorithm, the key is to notice that if you iterate the algorithm twice, then the larger of the two numbers must have been cut by half. For example, if one is 100 and the other is 75, then 100%75 gives you 25; now you have 75 % 25, which is smaller than half of 100.

The smaller number is bounded above by the larger number, and we stop when the smaller number hits 0/1. If you know that the larger of the two numbers is N and it goes down by a factor of two every other iteration, then you know that the number of iterations must be logarithmic in N.

SO the runtime is O(lg N).

[nonevent99]

BTW, somebody asked me to post more code snippet problems. SO let me augment this topic with the following:

int gcd( int num1, int num2 )
{
int remainder = num2 % num1;

if ( remainder != 0 )
return gcd( remainder,num1 );

return num1;
}


Suppose that when gcd(M,N) is called (M < N), the resulting execution results in the worst possible runtime. The resulting sequence of num1 values is a famous sequence. What is its name?

(ie: what sequence of numbers is "traversed" in the worst case?)

[AlbaLed]

Find the gcd of 10 and 8. Well, 10 % 8 (per Alba's correction, not 8 % 10) is 2. So now you have 8 and 2. 8 % 2 is 2. So now you have 2 and 2. And 2 % 2 = 1. And 2 % 1 = 0. 2 must be the GCD.

Nonevent, anything wrong there (the red part)?

[nonevent99]

Originally posted by AlbaLed

Find the gcd of 10 and 8. Well, 10 % 8 (per Alba's correction, not 8 % 10) is 2. So now you have 8 and 2. 8 % 2 is 2. So now you have 2 and 2. And 2 % 2 = 1. And 2 % 1 = 0. 2 must be the GCD.

Nonevent, anything wrong there (the red part)?

:drunk: I think I was getting ahead of myself a bit. Thanks, Alba.

Do you know what sequence numbers happens in the worst case?

[AlbaLed]

Nonevent, I have no clue, but I know that the running time is O(log(b)), where b is the bigger number

[nonevent99]

Originally posted by AlbaLed

Nonevent, I have no clue, but I know that the running time is O(log(b)), where b is the bigger number

I have read that the worst case sequence traces out the Fibanacci numbers. For example, if you are given 21 and 34, then you get 13 and 21, then 13 and 8, then 8 and 5, then 5 and 3, then 3 and 2, then 2 and 1, then 1 and 0.

It's a sequence where the larger number just doesn't seem to want to die. But still, every other iteration, you still have to lose at least half of what you've got, so the big-O constraint still holds.

[AlbaLed]

Now I remember I think I've seen the fibbi sequence related to euclids algo.

I think fibbonaci was analyzing euclids algo when he came up with his sequence, not sure tho