[Edu-sig] Long Integer Fractions

[Kirby Urner]

>Yep, I was reinventing a wheel.  Not surprised.
>
>yarn.py looks good.  gcd() is especially fine:
>
>def gcd(a, b):
>	"""Return GCD of two numbers.  Duh!
>	"""
>	while b:
>		a, b = b, a % b
>	return a
>
>(That's Lanny's duh, not mine).
>
>Kirby

The above algorithm isn't original with Lanny however.
Euclid wrote it up in Book 7, Propositions 1 and 2 of
Elements, but Knuth thinks it goes even further back.

Maybe Lanny wrote "Duh!" because this is one of the 
oldest algorithms on record, and would be recognized 
by just about anyone with training in computer science
and numerical methods.  Ergo, every K-12er should know
it too, as per my evolving math-through-programming
approach to CP4E (numeracy + computer literacy).

Today was my birthday, and as a present to myself, I
finally bought a copy of 'The Art of Computer Programming'
by Donald E. Knuth, 3rd Edition, 1998, Addison Wesley
-- a classic work in the field.  I couldn't afford all 
3 volumes though, just got volume 2.  The gcd() stuff 
is in section 4.5.2.

Kirby