Comparing Integers with a shift

Barukh Ziv barukh.ziv at
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

Is this more efficient? Any other ideas are welcomed.


More information about the gmp-discuss mailing list