It's time to implement our schoolboy division routine. I prefer the name
divrem_classical, in line with the multiplication routines.
This function will take a dividend a, divisor d, carry-in ci and returns
a quotient q and remainder r. We'll also need to pass in a precomputed
inverse to speed up the dword_t by word_t divisions that need to occur.
We are going to implement the first algorithm spoken of in the previous
post, namely the one which uses a single "normalised" word of the divisor.
We need to be careful not to just shift the top word of the divisor so
that it is normalised, but if it has more than one word, shift any high
bits of the second word as well. We want the top WORD_BITS bits of the
divisor, starting with the first nonzero bit.
We can use our macro for doing a dword_t by word_t division to get each
new word of the quotient. We start with the carry-in and the most
significant word of a. The macro will automatically shift these by the
same amount as we shifted the leading words of the divisor.
As per the divrem1 function, we require that the carry-in be such that
the quotient won't overflow. In other words, we assume that if the
divisor d is m words, then the top m words of the dividend including the
carry-in, are reduced mod d.
First we need to check that we are not in the special case where truncating
the dividend and divisor to two and one words respectively would cause
an overflow of the quotient word to be computed. This only happens
when the top word of the dividend equals the top word of the divisor, as
explained in the previous post.
If the truncation would cause an overflow in the quotient, we collect a
quotient word of ~0, as discussed in the previous post. If not, we compute
the quotient using our macro.
After this point, the remainder is computed. We allow the function to
destroy the input a for this purpose. We leave it up to the caller to make
a copy of a and pass it to the function, if this is not desired
behaviour.
We do our adjustment so that the quotient is correct. We need a while loop
for this, as mentioned in the previous article.
Finally we write out the quotient word and read in the next word of the
dividend that remains.
In the test code we use our mul_classical and muladd_classical functions to
check that divrem_classical is indeed the inverse of these functions, with
zero remainder and nonzero remainder respectively.
The code for today's post is here: v0.14
Previous article: divrem discussion
Next article: v0.15 - divapprox_classical
No comments:
Post a Comment