Fourth in a series on colorForth and GreenArrays hardware. This time, how the multiply-step instruction works on the F18.
Here's a bit-twiddly interview question for you: Design an algorithm to multiply fixnum integers in O(log n) time using only addition. This may come in handy given that the F18 doesn't have a plain multiply instruction!
Starting with the primary school algorithm, but in binary:
110001 × 111101 110001 0000000 11000100 110001000 1100010000+ 11000100000 101110101101 <- 'bad' in hex :)
Summing the product of each digit of the multiplier (right to left) and the multiplicand; shifting (padding with zeros) as we go. Of course, single binary digit multiplication is super-easy; being just zero or the multiplicand itself.
Another way to formulate this is:
1 × 110001 << 0 = 110001 0 × 110001 << 1 = 0000000 1 × 110001 << 2 = 11000100 1 × 110001 << 3 = 110001000 1 × 110001 << 4 = 1100010000+ 1 × 110001 << 5 = 11000100000
Or we can begin with the multiplicand shifted to the left and shift right after each step:
1 × 11000100000 >> 5 = 110001 0 × 11000100000 >> 4 = 0000000 1 × 11000100000 >> 3 = 11000100 1 × 11000100000 >> 2 = 110001000 1 × 11000100000 >> 1 = 1100010000+ 1 × 11000100000 >> 0 = 11000100000
This leads to realizing that In fact we can do it in place. We can begin with the multiplier in the right-most bits, processing one bit at a time, shifting right after conditionally adding the left-shifted multiplicand. Pretty slick!
This code works with a pair of 8-bit values; first preparing by shifting the multiplicand 8 bits to the left, then performing 8 'step' operations. Each 'step' adds the multiplier if the low bit is set, then (always) shifts everything right. There you have it; multiplication in terms of only addition and shifting!
Add multiplicand (left - 110001).Then shift right.
Add multiplicand.Shift right.
This is essentially how the F18 works. There is a multiply-step (+*) instruction that carries out one step of this process; applied n-times (usually in a micronext loop) to perform an n-bit multiply. You can read the details in the doc. The multiplier is placed in A, the multiplicand in S and an initial zero in T. Together, T and A are treated as a single shift register (like the left/right in our example above). Then a series of multiply-step (+*) instructions are executed; leaving the result (in A). Here's Greg Bailey's excellent description from the GreenArrays arrayForth Institute course:
As he says, there are other purposes for the +* instruction. We'll get into them later.
Here's an example (note that the sim we're using is 32- rather than 18-bit, thus the 1f loop count)
It may be more efficient to unroll the loop:
Or a good balance might be to do sets of three +* in a micronext loop:
Try it out with some silly hex words: