### Thread: Euclid's Method for finding a common factor

1. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Nov 2004
Posts
9
Rep Power
0

#### Euclid's Method for finding a common factor

Okay,

This one has me stumped! I have no clue what Euclid's Method is....haven't had a Math class in several years.

This is my assignment:

Write a function that implements Euclid's method for finding a common factor of two numbers. It works like this:

You have two numbers, a and b, where a is larger than b
You repeat the following until b becomes zero:
a is changed to the value of b
b is changed to the remainder when a (before the change) is divided by b (before the change)
You then return the last value of a
Hints:

Use a and b as parameters to the function
Simply assume that a is greater than b
The remainder when x is divided by z is calculated by the expression x % z
Two variables can be assigned to simultaneously like this: x, y = y, y+1. Here x is given the value of y (that is, the value y had before the assignment) and y is incremented by one

I have no idea why x,y,and z are in this if I have to find the last value of A? Can someone help me out with this bad boy?

Munk
2. Originally Posted by PA_Munk
Okay,

This one has me stumped! I have no clue what Euclid's Method is....haven't had a Math class in several years.

This is my assignment:

Write a function that implements Euclid's method for finding a common factor of two numbers. It works like this:

You have two numbers, a and b, where a is larger than b
You repeat the following until b becomes zero:
a is changed to the value of b
b is changed to the remainder when a (before the change) is divided by b (before the change)
You then return the last value of a
Hints:

Use a and b as parameters to the function
Simply assume that a is greater than b
The remainder when x is divided by z is calculated by the expression x % z
Two variables can be assigned to simultaneously like this: x, y = y, y+1. Here x is given the value of y (that is, the value y had before the assignment) and y is incremented by one

I have no idea why x,y,and z are in this if I have to find the last value of A? Can someone help me out with this bad boy?
The desrciption is fairly straightforward, but not very well worded. The salient points of the explanation are:
• The z, y and z were just used to give examples of how to get a remainder, and of how to use multiple assignment. They aren't part of the function itself.
• the key part of the algorithm is in the part with 'repeat the following until...' . This wording implies a loop or recursion of some kind. In this case:

Code:
`while (0 != b):`
• The body of the loop consists of two assignments.

a = b, and
b = the old value of a % b

You may need a temp variable for the second assignment; however, you can avoid that if you use the multiple-assignment technique the teacher describes at the end:

Code:
`      a, b = b, a % b;`
• If the loop is constructed correctly, then when b == 0, then the value of a is the desired result.

finally, I could add that there is a very simple tail-recursive version, as well, which would go like this:
Code:
```define a function GCD (a, b):
if b is equal or less than zero, then return a;
else return the value of the GCD (b, a % b).```
however, the description given seems to favor the iterative form of the algorithm.
3. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Nov 2004
Posts
9
Rep Power
0
Thank you!!

So it would look like this:

def euclid(a,b):

while b:

a,b = b,a % b

return a
4. That's exactly right - though it would help if you used the [ code ] and [ /code ] tags around your code, which preserves the indentation and makes it easier to read.
Code:
```def euclid(a,b):

while b:
a,b = b,a % b

return a```
You can select the code in question and use the '#' button in the editor to add the tags automatically.

If you use the [ php ] tag, it will even highlight it - it assumes PHP code, and so won't highlight Python code quite correctly, but as you can see here it is close enough to be acceptable:
PHP Code:
``` def euclid(a,b):     while b:         a,b = b,a % b     return a  ```