Ciao Niels and David,
Il 2022-02-23 09:14 ni...@lysator.liu.se ha scritto:
N^3-1 = (N^2+N+1)/3 * 3^{k+1} * (N-1)/3^k
Could be implemented as one multiply each mod 2^N+N+1 and (N-1),
followed by reduction mod (N^2+N+1)/3 and (N-1)/3^k at the end; these
reductions correspond to small quotients and should be cheap (I
suspect we have to require canonical reduction for CRT reconstruction
to
Yes, there are many details that one needs to take into account to
implement something like that...
Il 2022-02-22 22:55 David Harvey ha scritto:
What about
B^33 - 1 = (B^11 - 1)(B^22 + B^11 + 1)?
Also, I suspect that some of these tricks are worth doing even if the
factorisations cross the B boundaries. The extra shifting overhead is
only
linear.
I do not, but if someone has the time to try to implement some
extensions on the _bnm1 side (B^n-1), I'd suggest to try at first the
"cross the B boundaries" strategy.
I mean, if we have H s.t. H^2 = B, I'd try to split
B^33 - 1 = (H^33 - 1)(H^33 + 1)
One more observation.
Currently, the library may require a product eg. mod B^72-1. The current
_bnm1 code splits the computation into
B^72-1 = (B^36+1)(B^18+1)(B^9+1)(B^9-1)
I'd expect that more than half the time is spent computing mod B^36+1.
Less than 1/4 the time is spent mod B^18+1.
Less than 1/8 the time is spent for each of the two last factors B^9+1,
and B^9-1.
... then maybe I was wrong when I wrote that we should not trade a
factor 3 with a factor 2...
Ĝis,
m
_______________________________________________
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel
