November 28th, 2004, 05:14 PM
Euclid's Method for finding a common factor
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
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?
Thanks in advance!
November 28th, 2004, 06:30 PM
The desrciption is fairly straightforward, but not very well worded. The salient points of the explanation are:
Originally Posted by PA_Munk
- 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:
- 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:
- 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:
however, the description given seems to favor the iterative form of the algorithm.
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).
November 28th, 2004, 06:35 PM
So it would look like this:
a,b = b,a % b
November 28th, 2004, 06:37 PM
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.
You can select the code in question and use the '#' button in the editor to add the tags automatically.
a,b = b,a % b
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:
a,b = b,a % b