Updated arithmetic, part 1
As a further step in separating storage details from algorithms, I’ve created two procedures, %number->list and %list->number, to convert between the actual “hard” format, and a “soft” format we can use for experimenting.
The “soft” format is a list. The first item is the sign in character form, and the rest of the list are the digits in little-endian order.
With the new procedures, I revisited the add and subtract code, and altered it to put conversion to and from the internal format at the same application (i.e., call or invoke) level.
I also added two procedures, %digit-sum and %digit-complement, to highlight the fact that the radix used for “hard” encoding does not affect the general algorithm at all. Although I am using decimal now, the radix could be (decimal) 4 294 967 296, which is what would be expected from a 32-bit implementation.
The add-digit procedure %digit-sum began as a two argument function. With digits as operands and a list as output, adding three numbers (to include the carry) was a bit ugly. The solution was to redefine %digit-sum as a three argument function.
The %digit-sum procedure replaces a Scheme conditional tree. The internal routine eliminates a lot of argument list cons-ing. The only cons-ing needed is for producing the return value. Arithmetic is used to create the sum, speeding it up even more. As a result, I am expecting the new arithmetic to be competitive with the floating-point arithmetic of some old versions of Basic running on their original (slow) microprocessors. The up side: big-num capability. The down-side: fractions are not yet implemented.
The %digit-complement is the (radix – 1) complement. In my decimal radix system, that would be the nine’s complement. If I had used a binary radix, it would have been the one’s complement.
That leaves three items that were not implemented in assembly language: digit0, digit1, and max-digit (replacement for digit9). The updated algorithm is derived from using digit0 and digit1 as the carry digits, and digit0 and max-digit as the “sign extension” digits. Only digit0 needs to be implemented, with the others derived from digit0.