|  Inertial-Mass | May 10, 2004 12:54pm | Euclid's algorithm for the greatest common factor of two positive integers is one of my favourites:
unsigned
gcf( unsigned u, unsigned v ) {
while( u > 0 ) {
if( u < v ) {
unsigned t = u; // temporary storage for swap
u = v;
v = t;
}
u = u - v;
}
return v;
}
The algorithm works because if u > v, then the greatest common factor of u and v is also the greatest common factor of v and u-v. |
|
|  |  113172 | May 12, 2004 6:48am | \ Euklid in a different language: Forth
: gcd ( u1 u2 -- u ) \ greatest common denominator
begin
tuck mod
?dup 0=
until ; |
|
|
| | Inertial-Mass | May 12, 2004 6:50am | | I couldn't figure out a nice way to format my source snippet with HTML here in the forum. |
|
| 
Sponsor |  pjd | May 23, 2004 8:38am | In Python:
def gcd(a, b):
while b:
a, b = b, a%b
return a
|
|
|
| | Inertial-Mass | May 23, 2004 7:54pm | 4: Sweet. What's your HTML source for formatting that last message?
I am familiar with neither Forth nor Python, and so I am probably missing something. My algorithm (shown in C) has an explicit step to compare the two inputs because it does not assume any particular ordering of them. Is it really the same algorithm expressed in Forth and Python? |
|
| 
Sponsor | | artist | May 24, 2004 1:06pm | #!/usr/bin/ruby
def gcd2(int)
a = self.abs
b = int.abs
a, b = b, a if a < b
while b != 0
void, a = a.divmod(b)
a, b = b, a
end
return a
end |
|
| | | 113172 | May 24, 2004 1:22pm | | 4: the algorithm works regardless of argument order. if order is "wrong", an extra iteration is performed. |
|
|
| | Inertial-Mass | May 24, 2004 2:07pm | | 7: Help me understand the implementation: Are "u1" and "u2" the inputs and "u" the output? I know that Forth is a stack language. I presume that u1 and u2 are pushed on entry into the function. I'm thinking that "mod" pops two numbers off of the stack and pushes back their remainder. What does "tuck" do? |
|
| | | 113172 | May 24, 2004 6:16pm | text between brackets are comments, optional. knowing the stack effect of a word is important, therefore it is depicted as stack diagram. left of "--" is what the word expects on the stack, right of "--" what the word leaves as result of its operation. the stack diagram ( u1 u2 -- u ) indicates "word expects two unsigned numbers, removes them, and leaves one result".
you are right about mod. Forth words usually remove their arguments, like Pascal, and unlike C (where it is the responsability of the caller, not the called word).
: foo ( -- ) begin 0 until ; \ would be an infinite loop.
but in gcd, we test whether the remainder (result of mod) is zero, and exit the loop if that's the case.
tuck has effect ( x1 x2 -- x2 x1 x2 ), i.e. places a copy of top stack element below the second stack element. i use "x" here, for "no matter what number, signed or unsigned" . it could be defined like this (but many Forth implementations define it as "primitive" - a machine code "atomic" function, rather than as high-level word, for performance reasons):
: tuck ( x1 x2 -- x2 x1 x2 ) swap over ;
?dup only duplicates the top stack element if it is not zero.
0= leaves true if top is zero, false otherwise.
you would place arguments on stack, call gcd, and output the result like this (the dot is "output top stack element as number"):
12 15 gcd .
arguments can of course be produced by other forth words, rather than giving numbers. |
|
|
Sponsor | | pjd | May 25, 2004 6:18am | Inertial-Mass: Yep, it's all the same.
As easterbunny said, the argument order doesn't really matter: if they're the wrong way around, the first iteration implicitly swaps them--try it.
The only other difference is that the Forth/Python/Ruby versions use the modulus/remainder operator directly, instead of getting the remainder via repeated subtraction. This can save a (potentially huge) number of unnecessary iterations.
As for the formatting, you can just look at the HTML source from your browser. (in Firefox, this is as simple as choosing "view selection source" from the context menu). |
|
| Simple but Beautiful | 11>| | | |
Algorithms → Discussion