Rational Numbers

January 25, 2011

Scheme provides rational numbers natively, but we will make our own version to show the implementation. We will represent a rational number as a pair with the numerator in the car and denominator in the cdr; our convention will be that the denominator is always positive and the numerator and denominator will have no common factors. We begin with a function frac that creates a fraction in the appropriate representation:

(define (frac n d)
  (if (zero? d) (error 'frac "can't have zero denominator")
    (if (negative? d) (frac (- n) (- d))
      (let ((g (gcd n d)))
        (if (= g 1) (cons n d)
          (cons (/ n g) (/ d g)))))))

Then the other functions are from grade-school arithmetic; note that divide doesn’t check for division by zero because frac will report any error:

(define (plus x y)
  (let ((a (car x)) (b (cdr x)) (c (car y)) (d (cdr y)))
    (frac (+ (* a d) (* b c)) (* b d))))

(define (minus x y)
  (let ((a (car x)) (b (cdr x)) (c (car y)) (d (cdr y)))
    (frac (- (* a d) (* b c)) (* b d))))

(define (times x y)
  (let ((a (car x)) (b (cdr x)) (c (car y)) (d (cdr y)))
    (frac (* a c) (* b d))))

(define (divide x y)
  (let ((a (car x)) (b (cdr x)) (c (car y)) (d (cdr y)))
    (frac (* a d) (* b c))))

When my daughter was in fifth grade, she had trouble understanding the method they taught for comparing two fractions, which required the student to multiply each fraction by the denominator of the other fraction, then simplify by removing common factors, and finally to compare numerators. I had trouble understanding the need to simplify the fractions, so I showed her how to compare two fractions by cross-multiplying, and she understood immediately; the next day, when the students had a quiz on comparing fractions, she finished long before any of the other students. At the next parent-teacher conference, the teacher berated me for undermining his teaching, and ordered me not to do so again. Harrumph! Here’s the cross-multiplication method:

(define (less-than? x y)
  (let ((a (car x)) (b (cdr x)) (c (car y)) (d (cdr y)))
    (< (* a d) (* b c))))

Here are some examples:

> (plus (frac 1 3) (frac -1 7))
(4 . 21)
> (minus (frac 1 3) (frac -1 7))
(10 . 21)
> (times (frac 1 3) (frac -1 7))
(-1 . 21)
> (divide (frac 1 3) (frac -1 7))
(-7 . 3)
> (less-than? (frac 1 3) (frac -1 7))
#f

You can run the program at http://programmingpraxis.codepad.org/EnDFmHgs.

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 621 other followers

%d bloggers like this: