I’m working on an implementation of arbitrary-precision signed integers (bignums) in Dialog, and this article seems like exactly what I need: a didactic explanation of how to implement bignums in Scheme, which uses lists the same way as Dialog (LISP-style).
Unfortunately, I find the attached Scheme code generally incomprehensible. So when it explains the “optimized subtraction” algorithm…
Let’s look at an example in human readable (as opposed to our internal) form. In the case of 1000000 - 1 we would be wanting to convert ‘(1 0 0 0 0 0 0) to (0 9 9 9 9 9 10). But if you think about it, a borrow from the minuend is the same as a carry added to the subtrahend. So, the conversion from ‘(1 0 0 0 0 0 0) to ‘(0 9 9 9 9 9 9 10) can be simulated, with the same effect, by converting the minuend to this instead: ‘(1 0 0 0 0 0 10) as long as we convert the subtrahend from ‘(1) to ‘(1 1)! However, after the first digit subtraction, we have to borrow again. No problem, we just repeat the process every time we need to borrow. The advantage to doing the borrow in this way is that it fits the LISP style of car and cdr, and it allows us to get everything done in one trip through the list with no look aheads whatsoever. Furthermore, it’s much simpler-not much more difficult than the carry was for the add algorithm. In fact, not only is it easier for LISP-it’s also easier for humans! Not only do you not have to look ahead more than one digit for a borrow, but you’re never borrowing anything other than 10. (In the customary method, when borrowing, you are sometimes borrowing 10, and sometimes 9). These schemes are mathematically equivalent. In the below, consider c to be the minuend digit from which a borrow was taken, and d to be the subtrahend digit.
(c - 1) - d (Given. i.e., how most people do it.) c + (-1 - d) (Associative Law.) c + (-d - 1) (Commutative Law.) c - (d + 1) (Distributive Law.)I was introduced to this trick by a CU professor [Haddon, 1982] who presented it as a trick for humans doing subtraction, especially in other bases such as 16, 8, and 2).
…I don’t really understand what’s going on, and I don’t know where to look for a better explanation. (The Haddon 1982 citation is to a university class that doesn’t seem to have any slides or notes available.)
What’s actually going on here? It sounds like it’s adding 10 (the base) to both the minuend and the subtrahend, but putting it into the least significant digit of the minuend and the second-least of the subtrahend?
This is the relevant bit of the source, which may make things clearer to people who know Scheme:
(define big-sub
(lambda (minuend subtrahend . base)
(let ((base (base-10?? base)))
(letrec
((recur
(lambda (minuend subtrahend borrow)
(if (no-digits? minuend)
(if (no-digits? subtrahend)
(if (=? borrow 1)
(error
"needed to borrow more than I had")
())
(error
"(>? subtrahend minuend) => #t"
minuend
subtrahend))
(if (no-digits? subtrahend)
(if (zero? borrow)
minuend
(recur minuend
(bigify-digits borrow)
0))
(let ((dig1 (first-digit minuend))
(dig2 (+ (first-digit
subtrahend)
borrow)))
(if (<? dig1 dig2)
(push-digit
(+ (- base dig2)
dig1)
(recur (rest-digits minuend)
(rest-digits
subtrahend)
1))
(push-digit
(- dig1 dig2)
(recur (rest-digits minuend)
(rest-digits
subtrahend)
0)))))))))
(remove-leading-zeros
(recur minuend subtrahend 0))))))