udiv_qr_3by2 vs divappr
Torbjörn Granlund
tg at gmplib.org
Mon Apr 30 09:00:50 UTC 2018
nisse at lysator.liu.se (Niels Möller) writes:
Good idea. Is there an easy way to use asl.h?
I cannot recall what it takes, I never finished simple integration of
it. (The idea is to have some --enable-asl=4 configure switch.)
I think using ABI=32 for now is yoor best option.
Main use is schoolbook division, where the quadratic term is unchanged.
So we can't expect any huge improvements.
Except when the linear term dominates, e.g., when the divisor is small...
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.
So the submul_1 size agument will increase slightly?
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.
That'd be very good!
--
Torbjörn
Please encrypt, key id 0xC8601622
More information about the gmp-devel
mailing list