Ciao David, Il Mar, 22 Febbraio 2022 10:55 pm, David Harvey ha scritto: > On Tue, 2022-02-22 at 22:39 +0100, Marco Bodrato wrote: >> > E.g, in this case we could try a top-level B^66 - 1 product, split in >> > B^33+1 and B^33-1; then the former suits your new algorithm well, but >> > the former can't be recursively split (at least not on a B boundary).
>> I fully agree. > What about > > B^33 - 1 = (B^11 - 1)(B^22 + B^11 + 1)? Actually, B is a number. And if B is a power of 4 (there is an even number of bits in a limb, as usually happens, e.g. 32, or 64) then (B^n-1) and (B^2n+B^n+1) are not coprime, because both are divisible by 3. And we can not use CRT. > 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. Maybe. One should write the code and try. Ĝis, m _______________________________________________ gmp-devel mailing list gmp-devel@gmplib.org https://gmplib.org/mailman/listinfo/gmp-devel
