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 an Arduino Mega 2560, ATmega2560, or ATmega1284.

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

To calculate factorial 36:

> (fac 36)
371993326789901217467999448150835200000000

Here's the whole infinite precision package: Infinite precision package.