Comparing Integers with a shift
Barukh Ziv
barukh.ziv at gmail.com
Sun Jan 10 08:56:21 CET 2010
Dear all,
Consider the following scenario: given a constant integer a, and a variable
integer b, that may be represented as b = d*2^n, where d is odd.
My question is: what is the most efficient way to compare a and d, if you
are given a and b?
Working at C++ level, one possible way would be:
(b >> mpz_scan1(b. get_mpz_t(), 0)) == a
but this requires copying and allocation, which may be expensive in case a,
b occupy many limbs.
Another approach is to compare mpz_sizeinbase(a, 2) (which is constant!) to
mpz_sizeinbase(b, 2) - mpz_scan1(b, 0). If these are not equal, the outcome
is clear; only in case they are equal, the aforementioned full comparison is
performed.
Is this more efficient? Any other ideas are welcomed.
Regards,
Barukh.
More information about the gmp-discuss
mailing list