Computing A mod d (for small odd d without division and multiplication)

[marco.bodrato at tutanota.com]

Ciao,

8 mar 2026, 21:17 da tg at gmplib.org:

> marco.bodrato at tutanota.com writes:
>
> I mean, mp_limbs_t rems [d-GMP_NUMB_BITS%2 >> 1-GMP_NUMB_BITS%2];
> should be large enough.
>
> I am not sure how to interpret that expression.
>

You declared rems[] of size d.
If GMP_NUMB_BITS is odd, then the maximal order is d-1, i.e. d-GMP_NUMB_BITS%2.
If GMP_NUMB_BITS is even, then the maximal order is d/2, i.e.d >> 1-GMP_NUMB_BITS%2.
We can declare a smaller rems[].


> ? #divisors(2^(64*3)-1)
> 49152
>
> Huh?
>
gp-pari says that there are 49152 divisors of 2^(64*3)-1.
But I didn't check if they are larger or smaller than 2^64...
Only 12289 of them fit in a 64-bits limb, and only 12289 are new (not divisors of 2^64-1).

Ĝis,
m