udiv_qr_3by2 vs divappr

paul zimmermann 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
>   approximation.)
> 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 mailing list