 # Calculating with fractions in uLisp

#1

Here’s a simple program to enable you to perform calculations with fractions, or rational numbers, in uLisp. You can represent rational numbers using Lisp expressions, and the result is given as a Lisp expression.

It will work on any version of uLisp with floating-point support; ie on 32-bit platforms.

## Examples

The function that performs the conversion to a rational result is called rational. For example, to evaluate:

1/3 + 1/4 + 1/12

you enter:

``````> (rational (+ (/ 1 3) (/ 1 4) (/ 1 12)))
``````

The answer is expressed as a Lisp function (so you could read it back in and eval it):

``````(/ 2 3)
``````

If the answer is greater in magnitude than 1 the result is given as a proper fraction. So, for example:

``````> (rational (+ (/ 3 4) (/ 7 8)))
(+ 1 (/ 5 8))
``````

If the argument is irrational the function will return the best rational approximation; for example:

``````> (defvar pi (* 2 (asin 1)))
pi

> (rational pi)
(+ 3 (/ 16 113))
``````

If the result is an exact integer the function just returns an integer; for example:

``````> (rational (+ (/ 3 10) (/ 4 5) (- (/ 1 10))))
1
``````

The calculations are performed using floating-point arithmetic, so the results are accurate to at least six significant digits.

## The rational function

Here’s the rational function:

``````(defun rational (x)
(let* ((s (if (minusp x) -1 1))
(x (abs x))
(i (truncate x))
(f (- x i)))
(let* ((r f) (k 1) (l 1) (m 0) (j 0) d n)
(loop
(when (< (abs (- f (/ j l))) 1e-6) (return))
(setq r (/ r))
(setq d (truncate r))
(setq r (- r d))
(setq n j) (setq j (+ (* j d) k)) (setq k n)
(setq n l) (setq l (+ (* l d) m)) (setq m n))
(cond
((zerop j) (* i s))
((zerop i) (list '/ (* j s) l))
((plusp s) (list '+ i (list '/ j l)))
(t (list '- (list '+ i (list '/ j l))))))))
``````

## How it works

The rational function works by converting its floating-point argument into a fraction by constructing a continued fraction. It does this by repeating the following two steps until close to an integer result is obtained:

• Take the reciprocal.
• Subtract the integer part

The following example illustrates this by converting 0.764706 into a continued fraction:

``````x                   = 0.764706
1/x                 = 1.30769
1/x - 1             = 0.30769
1/(1/x - 1)         = 3.25
1/(1/x - 1) - 3     = 0.25
1/(1/(1/x - 1) - 3) = 4
``````

Finally, solving the equation for x in the last line gives the exact answer that x = 13/17.