broot vs brootinv performancs

[Niels Möller]

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?

Right.

>   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.

Regards,
/Niels 

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