Calculating with fractions
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.
The function that performs the conversion to a rational result is called rational . For example, to evaluate:
1 + 1 + 1
> (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)
> (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
(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:
|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.
- ^ If you're trying this on a full implementation of Common Lisp you'll need to call it something like rat to avoid a conflict with the built-in rational function.