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