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.
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)
Printing big numbers
The function pri prints a number in big notation:
(defun pri (n) (cond ((null n) nil) (t (pri (cdr n)) (princ (truncate (car n) 10)) (princ (mod (car n) 10)) nil)))
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)
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
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.