[Edu-sig] Re: reducing fractions

[Kirby Urner]

>>   150/210 -> (3 x 5 x 2 x 5) / (7 x 3 x 2 x 5) -> 5/7
>
>That's how my 7th grade teacher taught me to simplify fractions, and I've
>never been sorry.
>
>Steve Litt
>Webmaster, Troubleshooters.Com
>http://www.troubleshooters.com
>slitt@troubleshooters.com

Yeah, it's a good way, especially because it builds on the 
prime vs. composite distinction (composites -> prime factors, 
somewhat akin to compounds -> elements).

I have a Python routine called primes.getfactors() which 
spits out the prime factors of a composite (within a 
limited domain -- "cracking numbers" like this isn't 
easy when the numbers get huge, a fact on which cryptography
builds).

  >>> from primes import getfactors, intersection
  >>> getfactors(150)
  >>> list1 = getfactors(150)
  >>> list1
  [2, 3, 5, 5]
  >>> list2 = getfactors(210)
  >>> list2
  [2, 3, 5, 7]
  >>> incommon = intersection(list1,list2)    
  >>> incommon    # find what nos both lists have in common
  [2, 3, 5]
  >>> import operator
  >>> gcdnumb = reduce(operator.mul,incommon)  # take the product
  >>> gcdnumb     # this is the greatest common divisor (gcd)
  30

Dividing by the gcd is how to make your numerator and denominator
relatively prime.

Of course, once in gcd territory, you're in a position to discuss
a classic algorithm, dwelt on my Knuth in his famous 'The Art of
Computer Programming' (multi-volume).  This is called "Euclid's
Algorithm" though it may predate Euclid, and is easily written 
in Python as follows:

 def gcd(a,b):
    """Return greatest common divisor using Euclid's Algorithm."""
    while b:      
 	 a, b = b, a % b
    return a

 >>> gcd(150, 210)
 30

The way this works is it tries to divide a by b, and if it 
gets a remainder r, then it looks for a gcd for b and r.  In 
other words, you need a more "fine grained" number that'll 
brick-fill a line of length b, _and_ the leftover r, in which
case it'll be a divisor of the original a as well.  If dividing
r into b leaves a remainder r1, then you're looking for 
gcd(r,r1) and so on -- this thing could also be written 
recursively:

 >>> def newgcd(a,b):
       """Return greatest common divisor using Euclid's Algorithm."""
 	 if b == 0: return a
	 return newgcd(b,a%b)

 >>> newgcd(210,150)
 30

Combined with the big integer class, such algorithms can be used 
to manage fractions in such a way that numerator and denominators
remain distinct, and all computations result in (long int)/(long int)
type fractions (some languages handle this natively, but in Python
you can write the class -- as some folks have done and placed on 
the net for free download).

Kirby