Is there a standard bitwise log2 implementation, akin to logb() in C?

[Eric Barnhill]

I'm working on the Complex() class over at apache commons-numbers, currently conforming multiplication and division methods to comply to C99 standards (G.5.1 to be specific).

Some C-specific methods are called for and I am searching for the best equivalent in Java; for example, the complex multiplication standard calls for scalbn() and Java has the equivalent in Math.scalb().

The complex division standard calls for  logb() which is an efficient way of taking the 2-log by shifting bits, that avoids under- and overflows that can occur from a simpler formulation such as Math.log(x) / Math.log(2) .

I cannot find a similar method in the Math API, but maybe I don't have the right name. Has anyone come across a standardized logb() or similar bit-shifting method of taking log2 in Java?

This thread elsewhere has some methods for integers, but I need to handle doubles.

[Campbell Ritchie]

Never seen one. I presume you have already been through the Math and StrictMath classes and the API index (L) already.
What is the actual risk of an overflow or underflow error? If you divide a logarithm by log2, won't underflow only occur when your argument is close to 1.0?
What does logb() return? Is it an int?
Remind yourself of the structure of a double. Its bit₀…bit₅₁ contain the right 52 bits of a 53‑bit mantissa whose leftmost part is equivalent to 1.… The next bits to the left (52…62) represent an exponent biased by −0x03ff (I think: check that), and the remaining bit (No 63) is a sign bit. Now, we know that non‑positive numbers don't have a real logarithm in the first place, so avoid anything ≤ 0.0.
Suggestion:-

1: Convert your double to a long; you can only use bitwise operators on integer primitives. There is a method called something like longToDoubleBits in the Double class.

2: Mask it with & 0x7ff0_0000_0000_0000L. You now have the exponent without the bias.

3: Shift that with >>> 0x34 (=52 decimal).

4: Subtract 0x3ff for your bias. If you get −0x03ff or (+)0x0400, you were in the realms of 0 or subnormal numbers or NaN or ∞ and your result is wrong.

5: The 1.… bit at the left of the mantissa may require you add 1 to your result

6: Check carefully that my numbers are correct.

[Tim Holloway]

Strictly speaking, I think that the C logb function merely returns the exponent bits by ripping them bodily from the argument floating-point number. This is a trivial operation in C, which is allowed to be only semi-portable, and can be done for Java by using a native function, but a true write-once/run-anywhere Java-only solution is more problematic.

It gets even more complicated when you realize that the results of logb (as I understand it) would vary depending on whether the underlying binary floating-point number has been normalized or not. As far as I can recall, Java doesn't have anyway of knowing whether a number has been normalized or not, much less on when and how to coerce it into normalization.

On top of that, the only way you can even begin to consider such a function in Java is courtesy of the standard that Java floating-point numbers in their default form are IEEE-format and thus consistent across computing platforms. The old IBM floating-point exponents were powers of 16, not powers of 2, if I'm not mistaken. And you can tap into them in Java, you just have to indicate their use with the appropriate keyword (which I don't remember offhand, but it may be "native").

Functions like logb are useful in C, where you can directly access the bits of almost anything, for better or for worse. Java, however, operates on a more abstract level and all you can do is fake it and realize that often the results will vary from reality - especially if the system starts normalizing on what you are working with while you are working with it.

As far as faking it, I suppose you could take the decimal logarithm of it, truncate it to an integer which gives the decimal exponent, and make an ad hoc judgement from there - if the exponent is 1, that's roughly equivalent to 3 as a normalized binary equivalent. An exponent of 2 would be about 8, and so forth with greater "precision" available from examining the range of the original number.

But Java really isn't geared for this kind of thing. Bit primitives aren't a part of the language. The closest thing you'll find is boolean, which is abstractly different, or byte, which is a collection of 8 binary values treated as a unit. Further, the common C practice of using unions and bitfield definitions is not supported in Java. Java can only operate on physical memory when using native methods.

[Eric Barnhill]

Many, many thanks for these terrific responses. I will give all this a re-think.

[Campbell Ritchie]

That's a pleasure

I searched for logb and found this which says

On most platforms, FLT_RADIX is 2, and thus this function is equivalent to log2 for positive values.

Since such radices would be the same for all JVMs, what is wrong with Math.log(x) / Math.log(2.0)?

[Tim Holloway]

Campbell Ritchie wrote:That's a pleasure

I searched for logb and found this which says

On most platforms, FLT_RADIX is 2, and thus this function is equivalent to log2 for positive values.

Since such radices would be the same for all JVMs, what is wrong with Math.log(x) / Math.log(2.0)?

It's a kludge.

I'm not really sure what purpose logb serves in pure mathematics. By everything I can see, it's a view into the low-level hardware which presumably can be used to optimize calculations rather than actually being part of a calculation directly.

The thing is, when you attempt this sort of thing using an abstract machine, it's not (and must not) seeing the low-level hardware. Newer IBM mainframes have 2 hardware floating-point co-processors, one for traditional IBM FP and one for IEEE. Older machines would only have the older one (indeed, it wasn't even standard equipment on the oldest of them). I'm not sure if IEEE was the native FP format for Sun's RISC machines, for that matter. And that's presuming that we're not even going to try and support things like Univac, Burroughs, Siemens, Cray or the first-generation MPU systems - since they're mainly extinct and mostly not powerful enough to run Java even without floating-point.

So A) we would be violating the spirit of the method by equivalencing the VM with the underlying hardware and B) as I said earlier, thanks to floating-point auto-normalization, we cannot be 100% sure that the number presented to the method call is indeed the number in RAM as far as its exponent value goes.