## 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;
}