0

I am looking for a fast way to approximate the logarithm base 2 of a BigInteger. Speed and support for large numbers are more important than exact results. My current suggestion is:

return BigInteger.valueOf(n.bitLength());

I highly assume that this gives a correct approximation for numbers up to 2^(2^31-1). But can it be done faster? I am not sure how efficient bitLength() is?

All comments and suggestions are highly appreciated. Thanks in advance.

Update: This is not a duplicate, because I was looking for the fastest way to perform the operation where accuracy is not that much of an issue. In the end, I decided to use double approximations.

aka
  • 2,723
  • 1
  • 14
  • 10
  • How Accurate does it have to be? IMHO getting the bit length is really inaccurate. Also, how big do you think your numbers will be? – Carlos Bribiescas Nov 04 '14 at 20:31
  • 1
    Possible [duplicate](http://stackoverflow.com/q/6827516/230513). – trashgod Nov 04 '14 at 20:36
  • @CarlosBribiescas: The numbers will be 80 to 100 bit integers. If there are more accurate and possibly faster ways, I'd be more than happy to get to know them. Thanks. – aka Nov 04 '14 at 20:59

0 Answers0