[Haskell-cafe] Confused about logBase

MarLinn monkleyon at googlemail.com
Fri Aug 26 01:43:58 UTC 2016

On 2016-08-25 21:27, Alexey Khudyakov wrote:
>> I discovered that in base logBase, the functions representing arbitrary
>> logarithms, are defined in terms of two applications of log. log, the
>> functions representing the natural logarithm, just pass responsibility on to
>> some primitives. That is fine, mathematically speaking. But from an
>> implementation standpoint, I wonder why one would do that.
>> The logarithm that should be the fastest and the most precise one to
>> approximate by a cpu should be the one to base two. In fact if one already
>> has a floating point representation, it should be almost ridiculously easy
>> to compute from the exponent.
> Also I don't think log in base 2 would be any more performant than
> natural logarithm. Yes calculations for exponent is easy but you still
> need to calculate it for mantissa and it's not easier task. And most
> of the time natural logarithm is used.

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. For floating point values, you already know where that bit is 
because the exponent tells you (modulo some edge cases and an offset). 
And even if I'm wrong, just combine both methods, add two numbers, done.

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)

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.

Maybe if speed is an issue people just resort to external libraries. 
Still, I had hoped for some more insight into why the choices were made 
as they were. I guess I'll have to assume the original easier 
implementation was just never changed because there where bigger, more 
important targets. Not 100% satisfying but reasonable.


More information about the Haskell-Cafe mailing list