[Haskell-cafe] Confused about logBase
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