There is the C function mpz_sizeinbase. If you do it in base 2 it will
extremely efficiently tell you the bit length. Your algorithm will
actually be O(n^2) time, whereas mpz_sizeinbase for base a power of 2
is O(1).
On 9 March 2011 17:46, Steve <sjh_goo...@shic.co.uk> wrote:
> I need to calculate the 'bit length' of some (very large) arbitrary
> precision natural numbers. Without any regard for efficiency, I have
> this prototype:
>
> --
> unsigned count_bits(mpz_class number)
> {
> BOOST_ASSERT(number<0);
> unsigned count=0;
> while (number!=0)
> {
> number>>=1;
> count++;
> }
> return count;
> }
> --
>
> While this approach is obviously very inefficient, it serves as a
> specification? What would be the most efficient way to implement this
> function? I note that this question relates to logarithms - about which
> I found various questions, but no satisfactory answers, on the web.
>
> --
> You received this message because you are subscribed to the Google Groups
> "mpir-devel" group.
> To post to this group, send email to mpir-devel@googlegroups.com.
> To unsubscribe from this group, send email to
> mpir-devel+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/mpir-devel?hl=en.
>
>
--
You received this message because you are subscribed to the Google Groups
"mpir-devel" group.
To post to this group, send email to mpir-devel@googlegroups.com.
To unsubscribe from this group, send email to
mpir-devel+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/mpir-devel?hl=en.
