[Haskell-cafe] Confused about logBase

[Richard A. O'Keefe]

On 26/08/16 1:43 PM, MarLinn via Haskell-Cafe wrote:
>
> Calculating the binary logarithm of an integer is a search for the least
> significant bit. For integers, that's either a build-in or a binary
> search.

The binary log of an integer is close to the location of
the MOST significant bit.  (Common Lisp, see HAULONG.
Smalltalk, see #highBit.)  Some machines have hardware
for "Count Leading Zeros" that can be used to get this.
BUT that's still not the binary logarithm.
4 and 5 have their most significant bit in the same place,
but do not have the same base-2 logarithm.

log2(4) = 2.0000000000000000
log2(5) = 2.3219280948873622

Realistically, the hard part happens *after* you find the
most significant bit.

For floating point values, you already know where that bit is
> because the exponent tells you (modulo some edge cases and an offset).

That's not the hard part.

In the open source libm, log() is 104 SLOC of C,
while log2() is 119 SLOC of C.  In both of them,
extracting the exponent from the floating point
number is indeed just a couple of lines.  It's everything
ELSE that's hard.  Getting below 0.90 ULP of error is not easy.

It's worth noting that these days the standard C library
has log1p() and log() -- both base e -- and also log2 and log10.
But that's recent; the C library used to include just log().


> That should still be faster than even the division operation alone that
> you otherwise need to combine the two values. Divisions are expensive, too.
> (interesting fact: Java uses a seven-fingered merge sort with
> bit-shift-trickery to approximate a division by seven because the
> division is so damn expensive)

Java was designed by a company that left integer division
entirely out of the hardware of their machine (SPARC V7).
While this was fixed in SPARC V8, some experiences leave scars.

For what it's worth, gcc and other C compilers have been
optimising integer divisions by known constants into shifts and
adds/subtracts for a long time.  The bit-shift trickery may well
be an idea whose time has gone.

What this has to do with FLOATING-POINT divisions is not clear.
Looking at all the work that log() -- or log2() -- has to do
makes me think that a Haskell program that could NOTICE an
extra floating-point division would be a very unusual Haskell
program indeed.

> So sorry, I don't believe that claim of yours. I'm not sure about your
> second claim either. Maybe natural logarithms are used more often, maybe
> not. I don't have any numbers either way and I don't read enough papers
> to have a feeling what the scientific community uses.

Natural logarithms have some rather pleasant mathematical
properties.  log10 is nice for human beings, but that's a user
interface issue more than actual calculation.  log2 is useful
if you are calculating "information", but even then, for most
purposes other than user output measuring information in nats
is just as good as measuring in bits.