finding MSB ?? Best way or is there a function?

[Ernst Berg]

I have been looking for a way to find the MSB of mpz_t
in GMP.
I am new to GMP.
Below are the only texts I can find on the subject.
  Do you know of any new or better ways to Find MSB in
mpz_t. 
 Do you know of a standard function in/for GMP that
finds MSB of mpz_t ?

---------------------------------------------
Previous posts on the subject  :  Your comments are
welcome as to the validity of these suggestions.
 My post continues after these quotes.
--------------------------------------------
Start--- "

Hello,

Is there an efficient way to compute the position of
the most
significant bit in a multiprecision integer?
Basically, like
mpz_scan1(), but instead of scanning from LSB to MSB,
the other way around.

mpz_sizeinbase(op, 2) would do it, but I don't know if
there is a more
efficent way to accomplish this.

Regards,
George Coulouris

----------------------------------------------------------------------------
George Coulouris <coulouri at ncbi.nlm.nih.gov> writes:

  mpz_sizeinbase(op, 2) would do it, but I don't know
if there is a more
  efficent way to accomplish this.

mpz_sizeinbase(op,2) should need just a few cycles.
Is that not efficient enough?  ;-)

--
Torbjörn

----------------------------------------------------------------------------

----------------------------------------------------------------------------

I assume one knows from the data structure of an
arbitrary integer where the
limb containing the most significant bit is.

Then the problem reduces to the problem of finding the
most significant
within a limb (a machine word).

I would tend to hardcode and bsearch it, i.e.

if (word & 0x0000FFFF)
   {
   if (word & 0x000000FF)
      {
      }
   else
      {
      }
   }
else
   {
   if (word & 0x00FF0000)
      {
      }
   else
      {
      }
   }

You could just roll and test, but I'm not sure how
that would compare
against a hardcoded BSEARCH.

Dave.
-----------------------------------------------------------------------------
-----------------------------------------------------------------------------

> -----Original Message-----
> From: gmp-discuss-admin at swox.com
[mailto:gmp-discuss-admin at swox.com]On
> Behalf Of Torbjorn Granlund
> Sent: Tuesday, November 26, 2002 1:04 PM
> To: George Coulouris
> Cc: gmp-discuss at swox.com
> Subject: Re: find position of most significant bit ?
>
>
> George Coulouris <coulouri at ncbi.nlm.nih.gov> writes:
>
>   mpz_sizeinbase(op, 2) would do it, but I don't
know if there is a more
>   efficent way to accomplish this.
>
> mpz_sizeinbase(op,2) should need just a few cycles.
> Is that not efficient enough?  ;-)
>
> --
> Torbjörn
> _______________________________________________

-----------------------------------------------------------------------------

> gmp-discuss mailing list
> gmp-discuss at swox.com
> https://gmplib.org/mailman/listinfo/gmp-discuss
On 2002-11-26 16:25:18 -0500, David T. Ashley wrote:
>
> I assume one knows from the data structure of an
arbitrary integer
> where the limb containing the most significant bit
is.

Yes. If A is an mpz_t, then A->_mp_d[ABS(A->_mp_size)
- 1] is the most
significant limb, since ABS(A->_mp_size) is the number
of limbs and
the most significant limb is always nonzero. I'm not
exactly sure what
happens when A is zero, but I think that
ABS(A->_mp_size) is zero
then, so there are no limbs. (Someone correct me if
I'm wrong!)

> Then the problem reduces to the problem of finding
the most
> significant within a limb (a machine word).

In longlong.h there is a macro called
count_leading_zeros that does
this.

--
Kalle Hasselström, kha at treskal.com
      www.treskal.com/kalle


-----------------------------------------------------------------------------
 "---End



This is great news for me that these fine folks offer
aid in their posts; however, if there is already a
function for this so much the better.
 I didn't see any that I could tell was a MSB function
so I guess I would need to write one.

 Please if you know of a MSB function ready made let
me know.

Ernst_Berg at sbcglobal.net