nisse at lysator.liu.se
Tue Dec 15 15:45:49 CET 2009
nisse at lysator.liu.se (Niels Möller) writes:
> I'm tempted to remove the inv21 member of the gmp_pi1_t type. It's used
> in exactly one place, and there it's most likely better to use 3/2
> division and inv32 anyway.
Here's a patch to dcpi1_div_qr.c, replacing the use of inv21 by inv32.
Some comments and questions:
* I require dn >= 2, I guess that requirement is part of the interface
for the new division functions? Then I'd like to add an ASSERT to that
effect at the top of the functions.
* The use of inv21 was in the case that the first block should generate
a single quotient limb. I replaced the old code (based on
udiv_qrnnd_preinv) by basically one iteration of the code in
sbpi1_div_wr, which took me some time to get right due to the
different pointer offsets used.
* I had do a separate update and adjustment step as well, using
mpn_submul_1, since the general update code was for (2 qn) / qn
division, while for qn = 1 I do a 3/2 division. The patch uses a goto
for that, but I think one could get rid of that (didn't do that now,
since I don't want to bloat the patch with indentation changes).
* Also in the general case, I think it would make sense to do (2qn+1) /
(qn+1) divisions, to reduce the probability of expensive adjustments.
Feedback appreciated. I'd like to check this in in a day or two.
And after that, one can delete the inv21 member.
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.
More information about the gmp-devel