Counting with Fingers

Primitive arithmetic operations +, -, *, /, ** are taken for granted in most programming languages. But a language need not necessarily support primitive arithmetic operations for it to be turing complete. Increment and decrement are the basic operations available in certain minimal turing complete languages like BF. How would you go about performing addition, multiplication, exponential in such a language with just Increment and decrement operations? It's certainly possible, but a short digression on the history of counting devices follows.

Counting was one of the primary reasons the computer was invented. There were numerous counting devices before the computer. The most primitive way was the tally marks found in egyptian cave drawings. Counting with fingers was also a common method as taught in primary schools. Chinese invented the abacus to aid in counting. Then came the mechanical and electronic calculators and computers.











How will you implement addition without +, multiplication without *, and exponentiation without ** ? Exponentiation is just repeated multiplication. Multiplication is just repeated addition and addition is just....well, repeated incrementation.

Think of the way you were taught addition in school. How did you add 2 and 3? You kept 2 fingers in one hand(left), 3 in the other (right).







You deduct one from left and add one to right.







You deduct one from left and add one to right.







Voila! You have no more fingers left in your left hand and the answer in your right hand. And all you needed to do was increment and decrement in alternate hands.

The only limitation is you have only five fingers in each hand. Even with the five fingers in each leg, it isn't much. Counting in this way isn't practical for larger number unless you have infinite fingers in each hand. But computers have a large memory (analogical fingers). And it is possible to add numbers using just increment and decrement as demonstrated previously.

An implementation of this in Scheme would look like this. [Scheme has primitive add1 and sub1 for increment and decrement]


(define (add n x)
(cond
[(zero? n) x]
[else (add1 (add (sub1 n) x))]
)
)


This is what happens if we use this function to add 5 and 8


(add 5 8)
= (1 + (add 4 8))
= (1 + (1 + (add 3 8)))
= (1 + (1 + (1 + (add 2 8))))
= (1 + (1 + (1 + (1 + (add 1 8)))))
= (1 + (1 + (1 + (1 + (1 + (add 0 8))))))
= (1 + (1 + (1 + (1 + (1 + 8)))))
= (1 + (1 + (1 + (1 + 9))))
= (1 + (1 + (1 + 10)))
= (1 + (1 + 11))
= (1 + 12)
= (13)


We have successfully used increment recursively to implement addition. Addition is a primitive recursive function. The same applies for Subtraction as well.

Now to implement multiplication without *, you can implement it recursively using + or add that we implemented just now:

(define (multiply n x)
(cond
[(zero? n) 0]
[else (add x (multiply (sub1 n) x))]
)
)

This is what happens if we use this function to multiply 4 and 5


(multiply 4 5)
= (5 + (multiply 3 5))
= (5 + (5 + (multiply 2 5)))
= (5 + (5 + (5 + (multiply 1 5))))
= (5 + (5 + (5 + (5 + (multiply 0 5)))))
= (5 + (5 + (5 + (5 + 0))))


...Before we reduce it further, we have a choice. We can abstract the addition as understood previously or delve deeper into how the addition is performed recursively.

= (5 + (5 + (5 + 5)))

= (5 + (5 + 10))

OR

(5 + (5 + (1 + (1 + (1 + (1 + (1 + 5)))))))

finally evaluating to

= 20

Now to implement exponent without **, you can implement it recursively using * or multiply that we implemented just now, which in turn is recursively implemented using + or add:


(define (exponent x n)
(cond
[(zero? n) 1]
[else (multiply x (exponent x (sub1 n)))]
)
)


This is what happens if we use this function to calculate 2**3


(exponent 2 3)
= (2 * (exponent 2 2))
= (2 * (2 * (exponent 2 1)))
= (2 * (2 * (2 * (exponent 2 0))))
= (2 * (2 * (2 * 1)))


The multiplications are evaluated recursively through addition, and the additions are evaluated recursively through increment.

Arithmetic operations can be computed recursively was a re-revelation to me on reading 'how to design programs' long after forgetting how to count with fingers.