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.

Previous article: v0.1 - basic types and addition

Next article: v0.3 - copy, zero, normalise, mul1