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

## No comments:

## Post a Comment