[Edu-sig] Long Integer Fractions

[Kirby Urner]

On Fri, 12 May 2000 23:58:05 -0700 I wrote:
>Anyway, I wrote a Fraction class that sort of does 
>this (computes with fractions) -- maybe I'm reinventing 
>a wheel or two here.

Here's the code.  Sorta rough.  

Also, depends on primes.py, which is zipped inside of 
python101.zip and linked from my math-thru-programming 
essay at:

  http://www.inetarena.com/~pdx4d/ocn/numeracy2.html

I'll probably just end up sticking the Fraction class
inside of primes.py eventually, as one more example 
application of its methods (gcd and lcm, which depend
on getfactor which depends on isprime).  

The class has its limitations i.e. even though it deals 
with long integers, my getfactor method relies on prime
factorizations, and this gets impractical using the brute 
force "trial by division" algorithm I'm using (I feature 
some other prime tests, such as Euler's and Fermat's,
but they all have loop holes).

Could be this Fraction idea is already in some module,
but I haven't seen it yet, nor in the books I've looked
at.  As I recall, SmallTalk has native integer fractions.
Scheme too?

Given my "math through programming" focus, having the 
capability to do basic ops with long integer fractions 
might come in handy.

Part of the idea is kids are learning Python as part of 
their basic math instruction.  So they'll be able to 
see/read/comprehend the technique for dividing one 
fraction by another as:

    def __div__(self,n):
        # divide self by another fraction
        f = self.mkfract(n)
        recip = Fraction(f.denom,f.numer)
        return self.__mul__(recip)

In other words, whereas a pre-Python conventional text might 
say "multiply by the reciprocal", here we see the __mul__ 
method being invoked, after creating Fraction recip with 
denom and numer reversed.

One of the things traditionalists scream about when reading
reformist math texts is that "dividing fractions" seems 
to be given short shrift.  So these folks should be happy
to see that I'm bringing it back -- albiet in a different
notation (self-executing).

========================= roots.py =================

import primes

class Fraction:
    numerator   = 1L
    denominator = 1L

    def mkfract(self,n):
        # this method is to allow ops that mix Fractions
        # with non-decimal numbers e.g. 25 * (3/7)
        if type(n).__name__ in ['int','float','long int']:
            return Fraction(n)
        else: return n

    def __init__(self,num=1L,den=1L):
        self.numer = long(num)
        self.denom = long(den)
        self.simplify()

    def __mul__(self,n):
        f = self.mkfract(n)
        return Fraction(self.numer*f.numer,
                        self.denom*f.denom)
    
    def __div__(self,n):
        # divide self by another fraction
        f = self.mkfract(n)
        recip = Fraction(f.denom,f.numer)
        return self.__mul__(recip)
    
    def simplify(self):
        # reduce numerator/denominator to lowest terms
        divisor = primes.gcd(abs(self.numer),abs(self.denom))
        if divisor > 1:
            self.numer = self.numer/divisor
            self.denom = self.denom/divisor
            
    def __add__(self,n):
        # add self to another fraction
        f = self.mkfract(n)
        common = primes.lcm(self.denom,f.denom)
        sum = self.numer * common/self.denom
        sum = sum + f.numer * common/f.denom
        return Fraction(sum,common)

    def __sub__(self,n):
        # subtract another fraction from self
        return self.__add__(-n)

    def __neg__(self):
        # negate self
        return Fraction(-self.numer,self.denom)
    
    __rmul__ = __mul__

    def str(self):
        return str(self.numer)+"/"+str(self.denom)
    
    def list(self):
        return [self.numer,self.denom]
    
    def float(self):
        return (self.numer*1.0)/(self.denom*1.0)

Fraction in action (this version auto-simplifies):

 Python 1.5.2 (#0, Apr 13 1999, 10:51:12) [MSC 32 bit (Intel)] on win32
 Copyright 1991-1995 Stichting Mathematisch Centrum, Amsterdam
 IDLE 0.5 -- press F1 for help
 >>> from roots import Fraction
 >>> a = Fraction(2,3)
 >>> b = Fraction(3,2)
 >>> c = a+b
 >>> c.str()   # str() is for seeing as string, nnn/ddd format
 '13L/6L'
 >>> c.float() # ...or you can output the decimal equivalent with float()
 2.16666666667
 >>> c=a-b
 >>> c.str()
 '-5L/6L'
 >>> a = Fraction(300,10)
 >>> a.str()  # note autosimplification, i.e. 300/10 is now 30/1
 '30L/1L'
 >>> (a*b).str()  
 '45L/1L'
 >>> d=25*b       # integer x Fraction OK
 >>> d.str()
 '75L/2L'

Kirby

PS:  thanks to Stan Heckman for catching this typo:

Fri May 12 22:28:33 2000

>>> halley(1000,4)  # 4th root of 1000 (duh)
10.0

Shoulda been 

>>> halley(10000,4)  # 4th root of 1000 (duh)
10.0

(double duh)