mpz_mod inside loop

[Hans L]

The "+ 2" looks quite wrong to me.

I think the correct way to align a value in such a way would be:
mpz_mul_2exp (align, n, 63 - ( ( mpz_sizeinbase ( n, 2 ) - 1 ) % 64) );

Think about the edge case where n is a single limb with all 64 bits set
(aka 2^64-1, or ~(0UL) in C ).
If i understand your goal correctly, its already as aligned as can be.  So
the operation should end up shifting by 0 (multiplying by 2^0=1)
mpz_sizeinbase will return 64, so we subtract one from that.  (without this
subtraction, 64 % 64 would give 0, then shifting by 64-0 will cause
unnecessary shift up an entire limb).
After the "% 64" we can add 1 back to result, (I've simplified this into
taking 1 away from the left side of the subtraction operation 64-1 = 63),
giving us our expected 0 shift.

Try considering other edge or nearby cases(like n=1, or
mpz_sizeinbase(n,2)==63) to convince yourself this is correct. I'm fairly
confident that it is.

Anyways, not sure about any efficiency benefits, or even what use mpz_mod
is after you've shifted.  Are you also shifting the r variable by the same
amount(*not* independently aligning r), then unshifting/dividing at the end
of the loop?

- Hans Loeblich


On Fri, May 17, 2019 at 1:50 AM Paul Underwood <paulunderwood at mindless.com>
wrote:

> I have noticed some efficiency when doing repeated mpz_mod (r, r, n) by
> replacing it with with mpz_mod (r, r, align) where align is n shifted left
> to the 64 bit boundary of the most significant quadword with the following
> (possibly incorrect) precomputed function:
>
> mpz_mul_2exp (align, n, 64 - ( ( mpz_sizeinbase ( n, 2 ) + 2 ) % 64 ));
>
> Is this correct expression for alignment of n?
>
> Paul
> _______________________________________________
> gmp-discuss mailing list
> gmp-discuss at gmplib.org
> https://gmplib.org/mailman/listinfo/gmp-discuss
>