## 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.

```(defun add (a b)
(cond
((null a) b)
((null b) a)
(t (put
(+ (car a) (car 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)
(list (* (car a) (car b)))
(cons 0
(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:

```(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.