BSDNT - v0.4 add1, sub1, neg, not

Today we introduce some more convenience functions, neg and not, and we
also add the functions add1 and sub1.

All of these functions operate slightly differently to the ones we have
introduced so far.

The functions add1 and sub1 simply add a single word to a multiprecision
integer, propagating any carries/borrows all the way along.

The main loops of add1 and sub1 need to stop if the carry becomes zero. This
is for efficiency reasons. In most cases when adding a constant limb to a
multiprecision integer, only the first limb or two are affected. One doesn't
want to loop over the whole input and output if that is the case.

However, we must be careful, as in the case where the input and output are
not aliased (at the same location), we still need to copy the remaining
limbs of the input to the output location.

We add tests that (a + c1) + c2 = (a + c2) + c1 and do the same thing for
subtraction.

We also check that chaining of add1's and chaining of sub1's works. Until
we can generate more interesting random test integers this test doesn't
give our functions much of a workout. We eventually want to be able to
generate "sparse" integers, i.e. integers with only a few binary 1's or a
few binary 0's in their binary representation. The latter case would be
interesting here as it would test the propagation of carries in our add1
and sub1 functions. We'd also eventually like to explicitly test corner
cases such as multiprecision 0, ~0, 1, etc.

A final test of add1/sub1 that we add is a + c1 - c1 = a.

The not function is logical not. It complements each limb of the input. It
is a simple for loop.

The neg function is twos complement negation, i.e. negation modulo B^m. In
fact, twos complement negation is the same as taking the logical not of the
integer, then adding 1 to the whole thing. The implementation is similar to
add1, except that we complement each limb after reading it, but before adding
the carry.

One difference is that we still need to complement the remaining limbs after
the carry becomes zero, regardless of whether the input and output are
aliased.

The carry out from (neg a) is notionally what you would get if you were
computing 0 - a. In other words, the carry is always 1 unless a is 0. In
order to allow chaining, neg must notionally subtract the carry-in from the
total.

We test that (not (not a)) = a and that neg is the same as a combination of
not and add1 with constant 1. We can also test that adding -b to a is the
same computing as a - b. And finally we can test chaining of neg, as always.

I wonder what the most interesting program is that we could implement on top
of what we have so far. Tomorrow we add a few more convenience functions
before we start heading into the more interesting stuff.

I think I may have solved the test framework problem. More on that when we
get to v0.11 and v0.12.

There is a github branch here v0.4 for this article.

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

Next article: v0.5 - add, sub, cmp