Infinite precision arithmetic
Full implementations of Common Lisp include arbitrary-precision integer arithmetic, so you can add, subtract, multiply, and divide integers as large as you like. The arithmetic in uLisp is limited to 16 bits, giving a range of 32767 to -32768, but this example shows how you can implement infinite-precision integer arithmetic in uLisp with a few simple functions.
These routines require too much memory for an Arduino Uno or ATmega328, but will run happily on most other 8/16-bit platforms or 32-bit platforms.
For an extension to uLisp that provides a full arbitrary precision arithmetic library see Arbitrary-precision arithmetic extension.
Representing big numbers
Each big number is represented as a list of small numbers in the range 0 to 99, with the least-significant digits at the start of the list, so the number 7654321 would be represented as the list:
(21 43 65 7)
The function big converts a uLisp integer into big number notation:
(defun big (n)
(cond
((< n 100) (list n))
(t (cons
(mod n 100)
(big (truncate n 100))))))
Here's an example:
> (big 32767) (67 27 3)
On 32-bit platforms it would be more efficient to use a list of numbers from 0 to 9999; this is left as an exercise for the reader.
Printing big numbers
The function pri uses format to print each pair of digits in the list representing a number in big notation:
(defun pri (n)
(let ((rn (reverse n)))
(format t "~d~{~2,'0d~}" (car rn) (cdr rn))))
The first pair of digits is printed with any leading zero suppressed.
Adding big numbers
The function add adds together two numbers in big notation:
(defun add (a b)
(cond
((null a) b)
((null b) a)
(t (put
(+ (car a) (car b))
(add (cdr a) (cdr b))))))
It uses the following function, put, which adds an integer n to a big number c with carry:
(defun put (n c)
(cond
((< n 100) (cons n c))
(t (cons
(mod n 100)
(add (list (truncate n 100)) c)))))
Here's the calculation of 654321 + 987654 = 1641975:
> (add '(21 43 65) '(54 76 98)) (75 19 64 1)
Multiplying big numbers
To multiply two big numbers we use the fact that:
(a + 100b) * (c + 100d) = ac + 100 * (bc + ad) + 10000 * bd.
To multiply a big number b by 100 we simply need to do:
(cons 0 b)
Here's the full definition of mul which multiplies two numbers in big notation:
(defun mul (a b)
(cond
((null a) nil)
((null b) nil)
(t (add
(list (* (car a) (car b)))
(cons 0
(add
(add
(mul (list (car a)) (cdr b))
(mul (cdr a) (list (car b))))
(let ((c (mul (cdr a) (cdr b))))
(when c (cons 0 c)))))))))
Here's the calculation of 654321 * 987654 = 646242752934:
> (mul '(21 43 65) '(54 76 98)) (34 29 75 42 62 64)
Calculating factorials
As an example of using the infinite precision package, here's a routine to calculate the factorial of a number n:
(defun fac (n)
(let ((f (big 1)))
(dotimes (x n)
(setq f (mul f (big (1+ x)))))
(pri f)
(print nothing)))
To calculate factorial 24:
> (fac 24) 620448401733239439360000
Integer exponents
Here's a second example, which will find the value of x^y for integer x and y. It uses binary exponentiation, which drastically reduces the number of multiplications needed:
(defun iex (x y)
(let ((e (big 1))
(f (big x)))
(loop
(when (zerop y) (return))
(when (oddp y) (setq e (mul e f)))
(setq f (mul f f) y (ash y -1)))
(pri e)
(print nothing)))
For example:
> (iex 2 64) 18446744073709551616
Here's the whole infinite precision package: Infinite precision package.
This will work on both the integer versions of uLisp, and the 32-bit versions of uLisp, which include floating-point support.