Comparing Integers with a shift
Paul Zimmermann
Paul.Zimmermann at loria.fr
Sun Jan 10 11:20:01 CET 2010
Dear Barukh,
> Date: Sun, 10 Jan 2010 09:56:21 +0200
> From: Barukh Ziv <barukh.ziv at gmail.com>
>
> 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.
the most efficient method seems to be the following:
* if a is even, always return "inequal" :-)
* if a is odd, first compare the most significant bits of a and b
(this might require shifting bits of a or b if they are not bit-aligned,
alternatively you might precompute 64 copies of a which are shifted by 0
to 63 bits)
* if the most significant bits (i.e., d) agree, then check the low bits of
b are zero (here no shift is required)
Paul Zimmermann
More information about the gmp-discuss
mailing list