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)
   ((< 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)
   ((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)
   ((< 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)
   ((null a) nil)
   ((null b) nil)
   (t (add
       (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)

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)))
     (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)

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.