broot vs brootinv performancs
nisse at lysator.liu.se
Tue Nov 13 20:25:53 CET 2012
Torbjorn Granlund <tg at gmplib.org> writes:
> * Which function uses submul_1? I thought neither the old nor the new
> bdiv functions used that.
You're right. I thought current sb_pi1_bdiv_qr used submul_1, but when I
look I remember that it uses addmul_1 and then it negates q on the fly.
> * I assume the gmp-bdiv repo changed all bdiv functions to use the new
> convention. Correct?
> Now you're suggesting that we reintroduce positive-quotient
> functions for 1 (and 2) limb divisors?
I'm suggesting that there are use-cases for both variants, and I think
it can can be a speedup of some 10% compared to bdiv_1 + mpn_neg. But
there's no urgent need to do that until we see an application where it
makes a significant difference for performance.
> * There is no mpn_sbpi2_bdiv_qr or mpn_sbpi2_bdiv_r, analogous to redc_2
> (except that we spec dividend and divisor size separately), but
> creating one from redc_2 should be straightforward.
If I remember this correctly, redc corresponds to bdiv_r. There are
minor difference, like naming, and where the reduced output is located
(with current redc it's stored in the low limbs, while for consistence
with bdiv_qr it should be stored in the high limbs).
And there's no bdiv_r anywhere, as far as I remember, those functions
have to be written based on current redc functions (unless we're
willing to pass a dummy q area to bdiv_qr instead).
> * Has there been any effort for replacing redc? I see
> mpn/generic/powm.c still calls redc_1, redc_2, and redc_n.
No. I think it would make sense to merge the new bdiv code first.
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.
More information about the gmp-devel