http://t3x.org/lisp64k/numbers.html

# LISPy things you can do in 64K bytes of core

## Arithmetics on Natural Numbers

Even purely symbolic LISP is a Turing-complete language, so natural numbers and their basic operations can be implemented in it, although not very efficiently. The term 12 × 34 + 567, for instance, would be calculated as follows:

```* (load 'src//nmath)
t

* (plus (times '(1 2) '(3 4)) '(5 6 7))
(9 7 5)

* _
```

The implementation works rather well and even implements unbounded integers ("bignums"). It is not even that slow on modern hardware: on the author's 750MHz notebook computer, calculating `(expt #2 #100)` takes 1.2 seconds and truthfully spits out

```(1 2 6 7 6 5 0 6 0 0 2 2 8 2 2 9 4 0 1 4 9 6 7 0 3 2 0 5 3 7 6)
```

Kilo LISP offers a nicer notation for writing lists consisting of single-character symbols exclusively. For instance, `#12345` equals `'(1 2 3 4 5)`. This notation is particularly practical for numbers. In the previous chapter it was used for base-1 numbers, so both `#iiiii` and `#12345` would represent the number 5. In this chapter, `#12345` represents the decimal integer 12345 and `#iiiii` denotes the base-1 number 5.

So how do arithmetics work in a language where the only relationship between two objects is the identity operation, a.k.a. `eq`? The following snippets will illustrate how numbers are represented and how addition is performed using only symbols.

As shown above, a number is a list of symbols that represent decimal digits. The digits themselves have no values, but can be tested for identity, e.g.:

```* (eq '5 '5)
t

* (eq '5 '7)
nil
```

This observation alone is enough to assign base-1 values to the digits and implement the successor (SUCC, N+1) and predecessor (PRED, N-1) functions as well as the test for the zero digit, DZEROP.

```* (setq value
(lambda (x)
(cond ((eq x '0) nil)
((eq x '1) #i)
((eq x '2) #ii)
((eq x '3) #iii)
((eq x '4) #iiii)
((eq x '5) #iiiii)
((eq x '6) #iiiiii)
((eq x '7) #iiiiiii)
((eq x '8) #iiiiiiii)
((eq x '9) #iiiiiiiii)
(else (error 'not/ a/ digit x)))))
value

* (setq pred cdr)
pred

* (value '5)
(i i i i i)

* (pred (value '5))
(i i i i)
```

The SUCC, PRED, and DZEROP functions assign values to the digit symbols `0`...`9`. This was the hard part! The rest is elementary school-level arithmetic.

When adding two numbers on a sheet of paper, what is basically done is to slide a decimal full adder over the operands:

```  <-------
+-+
2 3 |4|
+ 7 8 |9|+0
-------|-|--
|3|+1
+-+
```

A full adder adds two digits and a carry digit and yields a result digit and a new carry digit that will be fed to next full adder operation. In the above example, it maps the input (4,9,0) to (3,1), meaning 4+9+0=3, carrying 1 to the next operation.

There is one problem, though: adding digits requires the "add" operation, but the purpose of the entire exercise is to implement addition in the first place. The classic bootstrapping problem. However, since the domain of the full adder function is small (0..9 × 0..9), it can be implemented using table lookup. The result of 4+9 can be looked up in the following table by moving to the 4th row and then to the 9th column (rows and columns start at 0):

```(setq sums
'(((0.0) (1.0) (2.0) (3.0) (4.0) (5.0) (6.0) (7.0) (8.0) (9.0) (0.1))
((1.0) (2.0) (3.0) (4.0) (5.0) (6.0) (7.0) (8.0) (9.0) (0.1) (1.1))
((2.0) (3.0) (4.0) (5.0) (6.0) (7.0) (8.0) (9.0) (0.1) (1.1) (2.1))
((3.0) (4.0) (5.0) (6.0) (7.0) (8.0) (9.0) (0.1) (1.1) (2.1) (3.1))
((4.0) (5.0) (6.0) (7.0) (8.0) (9.0) (0.1) (1.1) (2.1) (3.1) (4.1))
((5.0) (6.0) (7.0) (8.0) (9.0) (0.1) (1.1) (2.1) (3.1) (4.1) (5.1))
((6.0) (7.0) (8.0) (9.0) (0.1) (1.1) (2.1) (3.1) (4.1) (5.1) (6.1))
((7.0) (8.0) (9.0) (0.1) (1.1) (2.1) (3.1) (4.1) (5.1) (6.1) (7.1))
((8.0) (9.0) (0.1) (1.1) (2.1) (3.1) (4.1) (5.1) (6.1) (7.1) (8.1))
((9.0) (0.1) (1.1) (2.1) (3.1) (4.1) (5.1) (6.1) (7.1) (8.1) (9.1))))
```

In case the carry digit is 1, the result can be found in the entry to the right or in the same column in the row below.

The DTH function finds the Dth element of a list, where D is a base-1 number, as described above.

```(setq dth
(lambda (d lst)
(if (dzerop d)
(car lst)
(dth (pred d) (cdr lst)))))
```

The DPLUS function uses DTH to implement the full adder via table lookup, where A and B are the operands and C is the carry digit:

```(setq dplus
(lambda (a b c)
(let ((row (dth (value b) sums)))
(if (eq c '1)
(dth (value a) (cdr row))
(dth (value a) row)))))
```

The PLUS function, which is a bit more complex, "slides" the full adder over two operands, adding their digits and propagating the carry digit. It distinguishes four cases:

• if the end of operand A is reached and the end of operand B is reached, it attaches the carry digit to the result R and returns it
• if the end of operand A is reached, but the end of operand B is not reached, it fills A with leading zeros
• if the end of operand B is reached, but the end of operand A is not reached, it fills B with leading zeros
• otherwise, it looks up the result digit and the new carry digit in the table, adds the result digit to the result R, and moves to the next pair of digits

Theoretically, the PLUS function adds two decimal numbers of any size. The actual size of the numbers is only limited by available node space and time allocated to the computation.

```* (plus #234 #789)
(1 0 2 3)

* _
```

The DIFF ("difference") function is implemented in basically the same way as PLUS, but it uses a different table for lookup. Also, its result has to be normalized by removing leading zeros, so that it does not return 0001 for 1000-999.

```* (diff #1023 #789)
(2 3 4)

* (diff #0 #1)
negative

* _
```

Because the NMATH package implements natural numbers, the DIFF function returns the symbol NEGATIVE when its result would be negative. This fact can be used to implement the numeric comparison predicates LESS, GRTR, etc:

```(setq less
(lambda (a b)
(eq 'negative (diff a b))))

(setq grtr (lambda (a b) (less b a)))

(setq lteq (lambda (a b) (not (less b a))))

(setq gteq (lambda (a b) (not (less a b))))
```

There is no "equal" predicate, because the EQUAL function of LISP can be used to test lists of digits for equality.

The TIMES and DIVIDE functions implement multiplication and floored division:

```* (times #123 #456)
(5 6 0 8 8)

* (divide #56000 #456)
((1 2 2) 3 6 8)

* _
```

DIVIDE returns a pair consisting of the floored quotient in the car field and the division remainder in the cdr field. In the above example it indicates that 56000 = 122 × 456 + 368.

In principle, this implementation can be extended to cover integers, rational numbers, real number, complex numbers, etc. However, it would make more sense to implement some native numeric data types first.

But then, not every interesting problem that can be solved with LISP requires numbers!