Thursday, 9 September 2010

BSDNT - v0.3 copy, zero, normalise, mul1

In this section we add a few more trivial convenience functions, nn_copy,
nn_zero and nn_normalise.

The first two are simple for loops which we implement in nn.h.

A pair {c, m} will be considered normalised if either m is zero
(representing the bignum 0) or the limb c[m-1] is nonzero. In other words,
the most significant word of {c, m} will be non-zero.

The only tricky thing to do with nn_normalise is to make sure nothing goes
wrong if all the limbs are zero.

We add numerous tests of these new functions. We zero an integer and check
that it normalises to zero limbs. We copy an integer and make sure it
copies correctly. We also copy an integer, then modify a random limb and
then check that it is no longer equal. This provides a further check that
the nn_equal function is working correctly.

Finally, we do a more thorough test of nn_normalise by zeroing the top few
limbs of an integer then normalising it. We then copy just this many limbs
into a location which has been zeroed and check that the new integer is
still equal to the original *unnormalised* integer. This checks that
nn_normalise hasn't thrown away any nonzero limbs.

Next we add a mul_1 function. As for all of the linear functions we have
been adding, this will be very slow in C. This time we need to retrieve
the top limb of a word-by-word multiply. Again, ANSI C doesn't provide this
functionality, so we use the gcc extensions that allow us to upcast to a
double word before doing the multiply. Again the compiler is supposed to
"do the right thing" with this combination.

We add a test to check that a * (c1 + c2) = a * c1 + a * c2. We also add
a test for chaining of mul1's together, passing the carry-out of one to
the carry-in of the next.

The github branch for this post is here: v0.3

No comments:

Post a Comment