Rational Numbers

January 25, 2011

A rational number, or fraction, is the ratio of two integers; for instance, 4/7 is the ratio of 4 (the numerator) divided by 7 (the denominator). No rational number may have a denominator of zero. Rational numbers respond to all the same operations as integers, including addition, subtraction, multiplication and division, and they may also be compared by the less-than operator.

Your task is to write functions that perform arithmetic on rational numbers. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

About these ads

Pages: 1 2

10 Responses to “Rational Numbers”

  1. [...] today’s Programming Praxis exercise, our goal is to implement common operations on rational numbers. [...]

  2. I believe your multiplication function is wrong. 1/3 * -1/7 should produce -1/21, not -3/7, shouldn’t it?

    My Haskell solution (see http://bonsaicode.wordpress.com/2011/01/25/programming-praxis-rational-numbers/ for a version with comments):

    ratio :: Integral a => a -> a -> (a, a)
    ratio _ 0 = error "Division by zero"
    ratio n d = (signum d * div n g, abs $ div d g) where g = gcd n d
    
    plus :: Integral a => (a, a) -> (a, a) -> (a, a)
    plus (nx, dx) (ny, dy) = ratio (nx * dy + dx * ny) (dx * dy)
    
    minus :: Integral a => (a, a) -> (a, a) -> (a, a)
    minus x (ny, dy) = plus x (-ny, dy)
    
    times :: Integral a => (a, a) -> (a, a) -> (a, a)
    times (nx, dx) (ny, dy) = ratio (nx * ny) (dx * dy)
    
    divide :: Integral a => (a, a) -> (a, a) -> (a, a)
    divide x (ny, dy) = times x (dy, ny)
    
    lessThan :: Integral a => (a, a) -> (a, a) -> Bool
    lessThan (nx, dx) (ny, dy) = nx * dy < dx * ny
    
  3. programmingpraxis said

    Fixed. I must have been asleep when I did that.

  4. Gambiteer said

    Knuth, volume 3, Seminumerical Algorithms, has some simple algorithms for rational arithmetic that computes GCDs on the smallest possible numbers. It complicates matters a bit, but it makes a big difference in some problems; you can find the code in _num.scm in the Gambit source code. (Search for (define-prim (##ratnum.= x y) …)

    For example, with your code using Gambit’s bignum operations I get for

    (define one (cons 1 1))

    (define number-of-loops 1000)

    (time
    (do ((i 0 (+ i 1))
    (r one (plus one (divide one r))))
    ((= i 1000) (display r)(newline))))

    (time
    (do ((i 0 (+ i 1))
    (r 1 (+ 1 (/ 1 r))))
    ((= i 1000) (display r)(newline))))

    gsi rational
    (113796925398360272257523782552224175572745930353730513145086634176691092536145985470146129334641866902783673042322088625863396052888690096969577173696370562180400527049497109023054114771394568040040412172632376 . 70330367711422815821835254877183549770181269836358732742604905087154537118196933579742249494562611733487750449241765991088186363265450223647106012053374121273867339111198139373125598767690091902245245323403501)
    (time (do ((i 0 (+ i 1)) (r one (plus one (divide one r)))) ((= i 1000) (display r) (newline))))
    217 ms real time
    210 ms cpu time (210 user, 0 system)
    390 collections accounting for 58 ms real time (50 user, 0 system)
    108458544 bytes allocated
    61 minor faults
    no major faults
    113796925398360272257523782552224175572745930353730513145086634176691092536145985470146129334641866902783673042322088625863396052888690096969577173696370562180400527049497109023054114771394568040040412172632376/70330367711422815821835254877183549770181269836358732742604905087154537118196933579742249494562611733487750449241765991088186363265450223647106012053374121273867339111198139373125598767690091902245245323403501
    (time (do ((i 0 (+ i 1)) (r 1 (+ 1 (/ 1 r)))) ((= i 1000) (display r) (newline))))
    1 ms real time
    10 ms cpu time (0 user, 10 system)
    1 collection accounting for 0 ms real time (0 user, 0 system)
    411264 bytes allocated
    1 minor fault
    no major faults

  5. Graham said

    Seems reminiscent of SICP :-)
    Since I implemented fractions as pairs, I included two procedures to get the
    numerator and denominator. I also included pretty printing of fractions. My
    Python solution:

    #!/usr/bin/env python
    
    def gcd(a, b):
        while b:
            a, b = b, a % b
        return a
    
    def frac(n, d):
        if d == 0:
            raise ZeroDivisionError
        else:
            sign = -1 if d < 0 else 1
            g = gcd(n, d)
            return (sign * (n // g), abs(d) // g)
    
    def num(x):
        return x[0]
    
    def denom(x):
        return x[1]
    
    def plus(x, y):
        return frac(num(x) * denom(y) + denom(x) * num(y), denom(x) * denom(y))
    
    def minus(x, y):
        return plus(x, frac(-num(y), denom(y)))
    
    def times(x, y):
        return frac(num(x) * num(y), denom(x) * denom(y))
    
    def divide(x, y):
        return times(x, frac(denom(y), num(y)))
    
    def is_less_than(x, y):
        return num(x) * denom(y) < denom(x) * num(y)
    
    def frac_print(x):
        print str(num(x)) + "/" + str(denom(x))
        return
    
    if __name__ == "__main__":
        frac_print(plus(frac(1, 3), frac(-1, 7)))
        frac_print(minus(frac(1, 3), frac(-1, 7)))
        frac_print(times(frac(1, 3), frac(-1, 7)))
        frac_print(divide(frac(1, 3), frac(-1, 7)))
        print(is_less_than(frac(1, 3), frac(-1, 7)))
    
  6. Graham said

    Oops! That was an earlier version. The constructor should be:

    def frac(n, d):
        if d == 0:
            raise ZeroDivisionError
        else:
            sign = -1 if d < 0 else 1
            ad = abs(d)
            g = gcd(n, ad)
            return (sign * (n // g), ad // g)
    
  7. Kai said

    A Ruby example
    Thanks for the refresher in how to find the GCD, it’s been a long time since I had to do that….

    class RationalNumber
      include Comparable
      public
      attr_reader :denominator, :numerator
    
      def initialize(numerator, denominator = 1)
        raise "Division by zero" unless denominator != 0
        if (denominator < 0)
          numerator   = -numerator
          denominator = -denominator
        end
        @numerator   = numerator.to_i
        @denominator = denominator.to_i
        reduce!
      end
    
      def -@
        RationalNumber.new(-@numerator, @denominator)
      end
    
      def * other
        RationalNumber.new(@numerator * other.numerator, @denominator * other.denominator)
      end
    
      def / other
        self * other.invert
      end
    
      def + other
        RationalNumber.new(@numerator * other.denominator + other.numerator * @denominator, @denominator * other.denominator)
      end
    
      def - other
        self + (-other)
      end
    
      def <=> other
        @numerator * @denominator <=> other.numerator * other.denominator
      end
    
      protected
      def invert
        RationalNumber.new(@denominator, @numerator)
      end
    
      def reduce!
        gdc = gdc(@numerator, @denominator)
        @denominator /= gdc
        @numerator /= gdc
      end
    
      def gdc(a, b)
        a, b = b, a % b while b > 0
        a
      end
    end
    
    
    
  8. Alan said

    In J, rational numbers are built-in, so this is really a demonstration of J’s extended integer and rational number arithmetic.
    In J, a rational number is written as ‘NrD’, where ‘N’ and ‘D’ are integers.
    If D is one, the ‘r1′ will be omitted. If D is zero, infinity is represented as “_”.
    Negative numbers are indicated with a ‘_’ prefix, eg: ‘_2′ is negative 2.

    NB. Rational literal numbers
    NB. generate a vector of 11 numbers
       i.11
    0 1 2 3 4 5 6 7 8 9 10
    NB. start the vector at -5
       _5 + i.11
    _5 _4 _3 _2 _1 0 1 2 3 4 5
    NB. produce the reciprocal of each number
       %_5 + i.11    NB. these are NOT rational
    _0.2 _0.25 _0.333333 _0.5 _1 _ 1 0.5 0.333333 0.25 0.2
    NB. produce the rational reciprocal of each number
       x:%_5 + i.11  NB. x: converts floating to rational
    _1r5 _1r4 _1r3 _1r2 _1 _ 1 1r2 1r3 1r4 1r5
    NB. produce the reciprocal of each rational number
       %_5x + i.11   NB. the 'x' suffix on any number makes it rational
    _1r5 _1r4 _1r3 _1r2 _1 _ 1 1r2 1r3 1r4 1r5
    

    Now that we now how to read and make rational numbers, let’s do some rational arithmetic in J (a very common thing to do in carpentry).

    NB. add rationals: add 1/2 + 1/3
       1r2 + 1r3
    5r6
    
    NB. what's 5/6 + 1/6?
       5r6 + 1r6
    1
    
    NB. what is 3/4 - 1/8?
       3r4 - 1r8
    5r8
    
    NB. now multiply some rationals: 1/2 times the vector 2,3,4?
       1r2 * 2 3 4
    1 3r2 2
    
    NB. 1/3 * -1/7?
       1r3 * _1r7
    _1r21
    
    NB. rational division: 1/2 divided by 1/4?
       1r2 % 1r4
    2
    
    NB. and 1/4 divided by 2?
       1r4 % 2
    1r8
    
    NB. apply <, =, and > (comparisons) between 1/2 and 1, 1/2 and 1/3
       |: 1r2    (<`=`>`:0) 1r1 1r2 1r3
    1 0 0
    0 1 0
    0 0 1
    
    NB. simplify:
       1r2 < 1r1 1r2 1r3
    1 0 0
       1r2 = 1r1 1r2 1r3
    0 1 0
       1r2 > 1r1 1r2 1r3
    0 0 1
    
    NB. Finally, GCD is built-in also as the '+.' operator
       12 +. 20
    4
       16 +. 28
    4
       18 +. 28
    2
       18 +. 27
    9
    
  9. Rainer said
    
    do forever
       say 'Bitte Rechnung eingeben, z.B. 1/2 * 1/3'
       parse pull f1 op f2
       if strip(f1) == '' & strip(op) == '' & strip(f2) == '' then leave
       say f1||' '||op||' '||f2||' = 'rat_rech(op,f1,f2)
    end
     
    exit
     
    rat_rech:
       parse arg op,f1,f2
       parse value f1 with z1'/'n1
       parse value f2 with z2'/'n2
       if n1 == '' then n1 = 1
       if n2 == '' then n2 = 1
       select
           when op == '+' | op == '-' then do
                   n = n1 * n2
                   interpret 'z = (z1 * n2) 'op' (z2 * n1)'
               end
           when op == '*' then do
                   n = n1 * n2
                   z = z1 * z2
               end
           when op == '/' then do
                   n = n1 * z2
                   z = z1 * n2
               end
       end
       return kuerzen(n,z)
     
    kuerzen:
       /* Zaehler und Teiler durch GGT teilen */
       parse arg y,x
       z = 0
       ggt = euklid(x,y)
       x = x / ggt
       y = y / ggt
       if x > y then do
           z = x % y
           x = x // y
       end
       /* Ganzzahlen separat */
       if z > 0 then
           return strip(z||' '||x||'/'||y)
       if y == 1 then
           return strip(x)
       return strip(x||'/'||y)
     
    euklid:
       /* gcd */
       parse arg a,b
       if a == 0 then return b
       do while b \= 0
           if a > b then
               a = a - b
           else
               b = b - a
       end
       return a
    
    
  10. cryptische said

    #include
    typedef struct rational
    {
    int n;
    int d;
    } rational;

    rational normalize(rational r)
    {
    int a = gcd(r.n, r.d);
    r.n/=a;
    r.d/=a;
    return r;
    }

    rational add(rational r1, rational r2)
    {
    rational sum;
    sum.d=(r1.d)*(r2.d);
    sum.n=(r1.n)*(r2.d)+(r2.n)*(r1.d);
    return normalize(sum);
    }

    rational subtract(rational r1, rational r2)
    {
    rational sum;
    sum.d=(r1.d)*(r2.d);
    sum.n=(r1.n)*(r2.d)-(r2.n)*(r1.d);
    return normalize(sum);
    }

    rational multiply(rational r1, rational r2)
    {
    rational sum;
    sum.d=(r1.d)*(r2.d);
    sum.n=(r1.n)*(r2.n);
    return normalize(sum);
    }

    rational divide(rational r1, rational r2)
    {
    rational sum;
    sum.d=(r1.d)*(r2.n);
    sum.n=(r1.n)*(r2.d);
    return normalize(sum);
    }

    int l_t(rational r1, rational r2)
    {
    int lcm=(r1.*r2.d)/gcd(r1.d*r2.d);
    if(r1.n*(lcm/r1.d)b){
    a=a+b;
    b=a-b;
    a=a-b;
    }
    if(a==0) return b;

    return gcd(b%a, a);
    }

    void print_rational(rational r)
    {
    printf(“%d/%d”, r.n, r.d);
    }

    void read_rational(rational *r)
    {
    scanf(“%d/%d”, &r->n, &r->d);
    }

    int main()
    {
    rational r1, r2;

    read_rational(&r1);
    read_rational(&r2);

    print_rational(divide(r1, r2));

    return 0;
    }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 616 other followers

%d bloggers like this: