[Edu-sig] Long Integer Fractions

[Dennis E. Hamilton]

The Euclidian GCD algorithm is also the very first algorithm introduced
in Volume 1.  It is used for the initial discussion of what constitutes
an algorithm, the conditions that an algorithm satisfies, and so on. (In
the 3d edition of volume 1, Fermat's last theorem is indeed downgraded
from difficulty [M50].  I can't remember if that leaves any [M50]
problems in the book!)

At some point, I would recommend section 1 of Volume 1 because it also
establishes the mathematical concepts needed for the series of books,
including basic number theory and other topics that are applied to great
advantage in volume 2 and beyond.  This might fit your interests
perfectly.

There is also a book on concrete mathematics that Knuth and a couple of
his buddies put together, but the material in Volume 1 strikes me (no
mathematician) as pretty challenging and interesting already.

Meanwhile, happy birthday!  For a long time, ACP vol.2 was one of the
most dog-eared and referenced books in my personal library.

-- Dennis

-----Original Message-----
From: edu-sig-admin@python.org [mailto:edu-sig-admin@python.org]On
Behalf Of Kirby Urner
Sent: Wednesday, 17 May 2000 18:26
To: edu-sig@python.org
Subject: Re: [Edu-sig] Long Integer Fractions



>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


_______________________________________________
Edu-sig mailing list
Edu-sig@python.org
http://www.python.org/mailman/listinfo/edu-sig