Wednesday, 8 September 2010

BSDNT - v0.2 subtraction, shifting

In today's revision we add a subtraction function and left and right
shift functions.

Subtraction is almost trivial after addition. We copy what we did for
addition. The main change is that carry-ins become borrows. we have to
negate our borrows at each step, so that we are always dealing with
positive quantities. The returned borrow is zero or positive.

In the test code for subtraction, we can add a test which checks that
a + b - b = a. This is a further test of the addition function as well.

Left shift is straightforward. Again we make use of the dword_t type
which is twice as wide as a word_t. This allows us to do a single shift
(which the compiler has the option of converting to two shifts if required).

We shift each limb by the specified bits, then hang onto the bits that were
shifted out the top, to be added back in at the next iteration.

For right shift we only have three functions instead of four. It doesn't make
sense to write out the "carry-out" at the bottom of a right shift. Instead
we do a "read-in" nn_r_rsh version which is the exact opposite of nn_s_lsh. It
reads the "carry-in" from an (m + 1)-th limb (which it shifts appropriately).

The nn_r_rsh function, also returns the bits that are shifted out the bottom end.

We can provide an extra test for addition now, by checking that a + a = a << 1
We also check that (a << sh1) >> sh1 gets us back to a.

Finally, we test that we can chain our carry-in carry-out functions together. For
example, I should be able to shift the first few limbs of an integer, feed the
carry-out as a carry-in in to the next shift, which will then shift the rest of
the integer. This should give me the same result as if I had shifted the whole
integer in one go.

We also do similar carry-in/carry-out chaining with the addition and subtraction
functions.

We are going to need to set up a proper test framework at some point, but for
now, whilst we are still working on implementing "linear" functions, I'm simply
going to keep duplicating the test functions over and over and making the
minor modifications required to test the new functions we are adding.

Here is v0.2 on github for this post.