How about adding rational fraction to Python?

[Lie]

On Feb 25, 1:21 am, Mark Dickinson <dicki... at gmail.com> wrote:
> On Feb 24, 1:09 pm, Lie <Lie.1... at gmail.com> wrote:
>
> > And this limit is much lower than n!. I think it's sum(primes(n)), but
> > I've got no proof for this one yet.
>
> It's the least common multiple of the integers 1 through n, or
> equivalently the product over all primes p <= n of the highest power
> of p not exceeding n.  So for n = 100, it's:
>
> 64 * 81 * 25 * 49 * 11 * 13 * 17 * ... rest of primes up to 100.
>
> For general n, this number is of roughly the same order of magnitude
> as e**n.

Ah, yes, I meant product(primes(n)), please forgive my honest mistake
which is partially caused by me not supposed to still be awake at this
time of the day. And thanks for Mark for noticing the mistake, and
here is the code I used:

import fraction
import random

frac = fraction.frac
ops = (frac.__add__, frac.__sub__)

a = frac(random.randrange(1, 10), random.randrange(1, 10))
b = frac(random.randrange(1, 10), random.randrange(1, 10))

while True:
    o = ops[random.randrange(0, 2)]
    a = o(a, b)
    b = frac(random.randrange(1, 10), random.randrange(1, 10))
    print a

I decided to keep the num/den limit low (10) because higher values
might obscure the fact that it do have limits. And through further
observations, I think it is sufficient if the limit is imposed in the
denominator only (numerator can have any values it wanted to,
denominator growth is determined only by the limit of denominator
growth).

I think I'll also post the code for the fraction class I used, if you
have other fraction class that can automatically simplify, you could
use that instead as this class suffers from a naive GCD
implementation:

==== fraction.py ====
from __future__ import division


def GCD(a, b):
    if b == 0: return a
    return GCD(b, a % b)


class frac:

    ''' Fraction Class



        A fraction class.



        Attributes:

        num  -> the numerator of a fraction

        den  -> the denominator of a fraction



        Methods:

        add(a, b)       -> add fraction a to fraction b and return a
new fraction

        sub(a, b)       -> subtract fraction b from fraction a and
return a new fraction

        mul(a, b)       -> multiply fraction a with fraction b and
return a new fraction

        div(a, b)       -> divides fraction b from fraction a and
return a new fraction

        invert(a)       -> invert the fraction (switch the numerator
and denominator)

        neg(a)          -> negates the fraction (negates numerator)

        powr(a, b)      -> raise fraction a to the power of b

        simplify(a, b)  -> simplify fraction to its canonical
representation



        __init__(a, b)  -> creates a new fraction

        __str__(a, b)   -> returns a string representation. Mixed
fraction if possible

        __repr__(a, b)  -> returns a string representation. Always
return vulgar fraction



        Operators:

        Conversion to fractions will be done automatically whenever
possible, in-place

        operation is fully supported. Both regular and reflected
operation is supported.

        a + b  -> Calls frac.add(a, b)

        a - b  -> Calls frac.sub(a, b)

        a * b  -> Calls frac.mul(a, b)

        a / b  -> Calls frac.div(a, b)

        a // b -> Floors the resulting fraction from frac.div(a, b)

        -a     -> Negates a fraction

        +a     -> Returns a copy of the fraction

        ~a     -> Return the reciprocal of a



        Comparisons:

        Implemented through __cmp__(a, b), no rich comparison.

        a == b  -> a equals b

        a != b  -> a not equal b

        a > b   -> a greater than b

        a < b   -> a less than b

        a >= b  -> a greater than or equal to b

        a <= b  -> a less than or equal to b



        Casting:

        __complex__ -> Converts the fraction to floats and return the
result as complex number

        __int__     -> Returns the whole part of the fraction in
Integer

        __long__    -> Returns the whole part of the fraction in Long

        __float__   -> Returns the value of the fractino in Float



        Exceptions:

        ZeroDenominatorError

        -> A fraction cannot have zero as its denominator



        Bugs:

        - At the meantime, the fraction class doesn't mix well if used

          together with floating type numbers. Inline operators and

          initializers implicitly assumed that numbers are either
integers or

          fraction. So if there are operations involving floating
point or

          you initialized a fraction with a floating point number, the
result

          would be something like a "floating point fraction".

    '''



    def __init__(self, a = 0, b = 1):

        dev = GCD(a, b)

        if b > 0:

            self.num = a // dev

        elif b < 0:

            self.num = -a // dev

        else:

            raise frac.ZeroDenominatorError



        self.den = abs(b) // dev



    def simplify(self):

        dev = GCD(self.num, self.den)

        self.num //= dev

        self.den //= dev

        return self



    def add(a, b):

        return frac(a.num * b.den + b.num * a.den, a.den * b.den)

    def sub(a, b):

        return frac(a.num * b.den - b.num * a.den, a.den * b.den)

    def mul(a, b):

        return frac(a.num * b.num, a.den * b.den)

    def div(a, b):

        return frac(a.num * b.den, a.den * b.num)

    def invert(a):

        return frac(a.den, a.num)

    def neg(a):

        return frac(-a.num, a.den)

    def powr(x, y):

        return frac(x.num ** y, x.den ** y)



    def __add__(self, other):

        return self.add(other)

    def __radd__(self, other):

        return other.add(self)



    def __sub__(self, other):

        return self.sub(other)

    def __rsub__(self, other):

        return other.sub(self)



    def __mul__(self, other):

        return self.mul(other)

    def __rmul__(self, other):

        return other.mul(self)



    def __div__(self, other):

        return self.div(other)

    def __rdiv__(self, other):

        return other.div(self)



    def __truediv__(self, other):

        return self.div(other)

    def __rtruediv__(self, other):

        return other.div(self)



    def __floordiv__(self, other):

        ret = self.div(other)

        return ret.num // ret.den

    def __rfloordiv__(self, other):

        ret = other.div(self)

        return ret.num // ret.den



    def __iadd__(a, b):

        a.num, a.den = a.num * b.den + b.num * a.den, a.den * b.den

        return a.simplify()

    def __isub__(a, b):

        a.num, a.den = a.num * b.den - b.num * a.den, a.den * b.den

        return a.simplify()

    def __imul__(a, b):

        a.num, a.den = a.num * b.num, a.den * b.den

        return a.simplify()

    def __idiv__(a, b):

        a.num, a.den = a.num * b.den, a.den * b.num

        return a.simplify()

    def __itruediv__(a, b):

        a.num, a.den = a.num * b.den, a.den * b.num

        return a.simplify()

    def __ifloordiv__(self, other):

        self /= other

        return self.num // self.den



    def __str__(self):
        ''' String Function

            Convert the function to its human-friendly representation.
Tries
            to convert smartly.
        '''

        ret = ''

        if self.num < 0: ret = '-'

        w, n, d = abs(self.num // self.den), abs(self.num) % self.den,
self.den

        if w != 0:

            if n != 0 and d != 1:

                ret += '%s %s/%s' % (w, n, d)

            else:

                ret += str(w)

        else:

            if n != 0 and d != 1:

                ret += '%s/%s' % (n, d)

            else:

                ret = '0'

        return ret



    def __repr__(self):

        return str(self.num) + '/' + str(self.den)



    def __complex__(self):

        return complex(float(self))

    def __int__(self):

        return int(self.num / self.den)

    def __long__(self):

        return long(self.num / self.den)

    def __float__(self):

        return self.num / self.den



    def __neg__(self):

        return frac.neg(self)

    def __pos__(self):

        return frac(self.num, self.den)

    def __abs__(self):

        return frac(abs(self.num), self.den)

    def __invert__(self):

        return frac.invert(self)

    def __pow__(x, y):

        return powr(x, y)



    def __coerce__(self, other):

        try:

            self.num, self.den

        except AttributeError:

            self = frac(self)

        try:

            other.num, other.den

        except AttributeError:

            other = frac(other)

        return self, other



    def __cmp__(self, other):

        a = self.num * other.den

        b = other.num * self.den

        return cmp(a, b)



    class ZeroDenominatorError(Exception):

        ''' Exception for having a zero as the denominator in a
Fraction Class

        '''

        def __init__(self):

            pass

        def __str__(self):

            return "A fraction cannot have zero as denominator
(frac.den != 0)"