Notes on Multiplication
This is another subject that required quite a lot of thought. I believe
I've found a way to make it all work, but there are a number of
subtleties involved that I'll try to explain here.
The basic algorithm I'll be using is simple: for each bit of
the first operand, multiply the second operand by it, shifted by an
appropriate number of places, and add up the results. This is
particularly easy to do in
binary, since multiplying by a single bit can be accomplished with an
AND gate.
In what follows, I'm going to call the first operand the multiplicand and the second operand the multiplier, because the second operand (the one that gets added to the product) will be the one held in the Multiplier Register.
Scaling
EDSAC numbers are meant to be interpreted as fractions in the
range -1 to 1, and the multiplication algorithm needs to produce results consistent with this interpretation. Given two signed n bit operands with an assumed point between bits n-1 and n-2, we want a 2n-1 bit result with an assumed point between bits 2n-2 and 2n-3.
Here's an example with n = 5:
0.75 * 0.6875 = 0.515625
0.1 1 0 0
0.1 0 1 1
-----------------
0 0 0 0 0
0 0 0 0 0
0 1 0 1 1
0 1 0 1 1
0 0 0 0 0
-----------------
0.1 0 0 0 0 1 0 0
From this we can see that to get a correctly aligned result, the most
significant bit of the multiplier (i.e. its sign bit) needs to be
aligned with the bit from the multiplicand that we are multiplying it
by.
Negative numbers
We need to make sure we get the right results with negative operands.
As long as the multiplicand is positive, we don't need to do anything
special -- the multiplier can be of either sign, and as long as we
sign-extend it when shifting, two's-complement arithmetic will produce the correct result. For example,
0.75 * -0.3125 = -0.234375
0.1 1 0 0
1.1 0 1 1
-----------------
0 0 0 0 0
0 0 0 0 0
1 1 1 1 0 1 1
1 1 1 0 1 1
0 0 0 0 0
-----------------
1.1 1 0 0 0 1 0 0
The bits resulting from sign extension are shown in red.
But, we need to be careful when the multiplicand is negative -- naively
treating the sign bit of the multiplicand the same way as its other
bits will not give the right result.
To see what needs to be done, consider that a number in the range -1 <= x < 0 can be written as -1 + y, where y
is what results from taking the bits after the point and interpreting
them as a positive number. In other words, we can take the bits after
the point as having positive binary weights for both positive and
negative numbers, as long as we give the sign bit a weight of -1.
What this means is that we can
carry out the multiplication algorithm as usual for the bits of the
multiplicand after the point, ignoring its sign; then, if the
multiplicand is negative, subtract the multplier from the product. Example:
-0.25 * 0.6875 = -0.171875
1.1 1 0 0
0.1 0 1 1
-----------------
0 0 0 0 0
0 0 0 0 0
0 1 0 1 1
0 1 0 1 1
1 0 1 0 1
-----------------
1.1 1 0 1 0 1 0 0
Here, the bits shown in red result from taking the two's complement of the multiplicand.
Shifting strategy
The above examples are presented as though the multiplier is being
shifted to the right by varying amounts, but I'm actually going to do
it slightly differently: at each step, shift the product one place right and then add the multiplier to the most significant bits of the product.
This avoids having to shift the multiplier, leaving the contents of the
Multiplier Register undisturbed. It also allows me to process the
multiplicand bits in order from least significant to most significant,
so that I can keep the multiplicand in the S-register and make use of its right-shift capability.
What's more, it turns out that, with a slight
modification to the circuitry I already have, I can perform the
shifting and adding together in one pass.
Where to put the unused bit?
For simplicity, BREDSAC is based on 18-bit cycles. But a short word has
only 17 bits, and a long word 35 bits, meaning there is one unused bit
in each short or long word. Early on, I chose to put this bit at the
most significant end, and extend the sign bit into it. However, while
thinking about multiplication, I realised it would be more convenient
to put the unused bit at the least significant end.
To see why, consider the 5-bit example from before, extended on the left with an unused 6th bit, shown here in red:
0 0.1 1 0 0
0 0.1 0 1 1
---------------------
0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 0 1 1
0 0 1 0 1 1
0 0 0 0 0 0
0 0 0 0 0 0
---------------------
0 0.0 1 0 0 0 0 1 0 0
Notice that the product is out by a factor of 0.5. Each of the unused
bits adds one extra bit to the product, resulting in it having two
extra bits on the left, whereas we only want one. Getting a correctly
scaled result would require an extra shifting step at the end.
On the other hand, if we put the unused bit on the right, things look like this:
0.1 1 0 0 0
0.1 0 1 1 0
---------------------
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 1 0 1 1 0
0 1 0 1 1 0
0 0 0 0 0 0
---------------------
0.1 0 0 0 0 1 0 0 0 0
There are still two extra bits in the product, but they're on the
right, where they don't make any difference to the value interpreted as
a fraction.
For this reason, I've decided to revise the design so that the unused
bit is at the least significant end. In the next instalment, I'll
detail the changes required to make this happen.