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