udiv_qr_3by2 vs divappr

[Niels Möller]

tg at gmplib.org (Torbjörn Granlund) writes:

> A quick comment: I'd suggest that you test this with 32-bit limbs, as
> the corner cases tend to be a fixed number irrespective of limb length,
> meaning that the likelyhood of hitting a corner decreases with limb
> size.  (You could even use asl.h, perhaps.)

Good idea. Is there an easy way to use asl.h?

> As you mentioned, it's been a while since we last looked into these
> things.  I cannot recall what exact operations we use today.  What
> performance improvements do you envision?

Main use is schoolbook division, where the quadratic term is unchanged.
So we can't expect any huge improvements.

Using divappr_2 instead of udiv_qr_3by2 might give a small improvement
of the linear term, this is still unclear. Quotient approximation gets
slightly easier, and the update of the high limbs of the partial remainder
will be done by submul_1 instead of explicit subtractions and carry
logic in the C code.

I think main benefit is that it will make unnormalized schoolbook
division, without upfront normalization, easier to implement.
Eliminating the bignum normalization shifts should give a good speedup
for divisions u/d, where u and d are large, but the quotient is just one
or a few limbs. And reduce need for temporary allocation as well.

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.
Internet email is subject to wholesale government surveillance.