udiv_qr_3by2 vs divappr
Paul.Zimmermann at inria.fr
Thu Sep 20 10:36:22 UTC 2018
> this looks quite interesting, I'm looking forward for cycle numbers.
> (I guess you target the case where the divisor is not invariant, otherwise
> you might do some preprocessing to speed up the partial quotient
> The divisor is invariant in some sense when the quotient is more than
> one limb, right?
yes it is. But I was thinking about many divisions with the same divisor
(say 2n limbs divided by n limbs). In short we can divide preprocessing
methods in two classes:
1) those with only O(1) preprocessing time, like the precomputation of an
inverse of the 1 or 2 uppers limbs of the divisor
2) those with O(n) preprocessing time, like Svoboda division
> Are you thinking of Svoboda division here? That's another possibility
> for speeding up schoolbook division.
yes, in Svoboda division the quotient selection is for free. But you still
have to wait the end of the previous submul_1 (or submul_2) call to access
the next quotient, whereas in mpn_mul_basecase all multipliers are known in
advance. Does this makes a difference?
More information about the gmp-devel