Friday 1 October 2010

BSDNT - v0.13 muladd1, muladd

We noted in the last article that multiplication need not take a carry-in
and that it doesn't seem related to the linear functions we have been
implementing.

Instead, we think of multiplication in a different way, as an inverse of
division. We'll soon implement division with remainder, i.e. given a and
d, find q and r such that a = d*q + r, where 0 <= r < d
If d and q are of lengths m and n respectively, then r is of length at most
m and a is either of length m + n or m + n - 1.

Multiplication corresponds to the case where r = 0.

As we will certainly not wish to have to zero pad our division out to
m + n limbs if a is in fact only m + n - 1 limbs, it makes sense that our
division will take a carry-in. For this reason, it made sense for our
multiplication to yield a carry-out, i.e. it will write m + n - 1 limbs
and return an m + n - th limb, which may or may not be 0.

When r is not zero in our division, the inverse operation would take a
value r of n limbs and add d*q to it, returning the result as a value a of
m + n - 1 limbs (and a carry which may or may not be zero). We call this
routine muladd. In the case where r and a happen to be aliased, the result
will be written out, overwriting a.

We first implement nn_muladd1 which is identical to addmul1 except that
muladd1 writes its result out to a location not necessarily coincident with
any of the inputs. In other words, nn_addmul1 is an in-place operation
whereas nn_muladd1 is not.

Next we implement nn_muladd_classical. It takes an argument a of length m
to which it adds the product of b of length m and c of length n. The result
may or may not alias with a.

We also implement a version of the linear and quadratic muladds which writes
out the carry, naming the functions with the nn_s_ prefix, as per the
convention initiated in our nn_linear module.

As for multiplication, we don't allow zero lengths. This dramatically
simplifies the code.

An important application of the muladd function will be in chaining full
multiplication. We'll discuss this when we get to dealing with multiplication
routines with better than quadratic complexity.

Our test code simply checks that muladd is the same as a multiplication and
and an addition.

The github repo for this post is here: v0.13

Previous article: configure and assembly
Next article: divrem discussion

No comments:

Post a Comment