Saturday 11 September 2010

BSDNT - v0.5 add, sub, cmp

It's time we added a full add and sub routine. These perform addition and
subtraction with possibly different length operands. For simplicity, we
assume the first operand is at least as long as the second. This saves us
a comparison and a swap or function call.

Add is simply an add_m followed by an add1 to propagate any carries right
through to the end of the longest operand. A similar thing holds for sub.

We'd like to code these as macros, however we'd also like to get the return
value. Thus, we use a static inline function, which the compiler has the
option of inlining if it wants, saving the function call overhead.

We add tests for (a + b) + c = (a + c) + b where b and c are at most the same
length as a. We also check that chaining an add with equal length operands,
followed by one with non-equal operands, works as expected. We add similar
tests for subtraction too.

The next function we add is comparison. It should return a positive value
if its first operand is greater than its second, a negative value if it is
the other way, and zero if the operands are equal.

As for equal_m and equal, we introduce different versions of the function
for equal length operands and possibly distinct operands.

The laziest way to do comparison is to subtract one value from the other
and see what sign the result is. However, this is extremely inefficient
in the case that the two operands are different. It's very likely that
they already differ in the most significant limb, so we start by checking
limb by limb, from the top, until we find a difference.

Various tests are added. We test that equal things are equal, that operands
with different *lengths* compare in the right order, and operands with
different *values* but the same length compare in the right order.

We also take the opportunity to do a copy-and-paste job from our cmp test
code and quickly generate some test code for the nn_equal function, which
didn't have test code up to this point.

From the next section onwards, we will only deal with one or two functions
at a time. All the really simple functions are now done, and we can move on
to more interesting (and useful) things.

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

Previous article: 0.4 - add1, sub1, neg, not
Next article: v0.6 addmul1, submul1

No comments:

Post a Comment