Confused about logBase
Hi, 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. I suppose it's probably a good idea to use primitive functions for the harder cases to get some speed-up. What I don't see is why the choice seems to have been an /xor/ instead of an /and/. I am by absolutely no means an expert on these things, so I am probably missing something here. Is there actually a good reason for this choice? For example will ghc optimize such logarithms anyway? Cheers, MarLinn
On 25 August 2016 at 00:51, MarLinn via Haskell-Cafe
Hi,
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.
Speaking of precision. log in any base is a transcendental function so best we can do is to ensure that approximation differs from true answer no more that 0.5 ULPs. 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.
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. MarLinn
On Thu, Aug 25, 2016 at 9:43 PM, MarLinn via Haskell-Cafe < haskell-cafe@haskell.org> wrote:
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 logs almost exclusively... because their occurrence all through the physical sciences and biology, etc. is what got them the name "natural". Which is why CPUs have natural log as a built-in FP operation. -- brandon s allbery kf8nh sine nomine associates allbery.b@gmail.com ballbery@sinenomine.net unix, openafs, kerberos, infrastructure, xmonad http://sinenomine.net
On Thu, 25 Aug 2016 21:56:01 -0400, you wrote:
Which is why CPUs have natural log as a built-in FP operation.
That's not quite true, as far as I know. The FPU log instructions (FYL2X and FYL2XP1) use base 2, but the FPU also provides FLDLN2 and FLDLG2 constant-loading instructions to allow for easy conversion to natural and base-10 logs, respectively. -Steve Schafer -- This message has been scanned for viruses and dangerous content by MailScanner, and is believed to be clean.
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.
And /that's/ why non-experts like me should not be let near the actual implementation. Thank you very much for all the detailed information and for purging some of the falsehoods in my worldview. I knew that I misunderstood a lot of stuff but now I have a better picture of were the errors actually are. So again, thanks! MarLinn
If you decide to research specialized algorithms for calculating logs with a variety of bases, it may make sense to start trying to add one to the numeric-functions package [*] before going for base. Aleksey Khudyakov has been doing a lot of work on that package of late, and would likely be able to help you work out potential issues. [*] https://hackage.haskell.org/package/math-functions On Aug 26, 2016 3:10 AM, "MarLinn via Haskell-Cafe" < haskell-cafe@haskell.org> wrote:
And *that's* why non-experts like me should not be let near the actual implementation.
Thank you very much for all the detailed information and for purging some of the falsehoods in my worldview. I knew that I misunderstood a lot of stuff but now I have a better picture of were the errors actually are. So again, thanks! MarLinn
_______________________________________________ Haskell-Cafe mailing list To (un)subscribe, modify options or view archives go to: http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe Only members subscribed via the mailman list are allowed to post.
2016-08-26 3:43 GMT+02:00 MarLinn via Haskell-Cafe : [...] Divisions are expensive, too. Yes, considered in isolation they are, but things are totally different if
you consider modern CPU architectures and the program as a whole: With
highly pipelined architectures, out-of-order execution, register renaming
etc. it is not uncommon that the high cost of the division itself is hidden
because e.g. its result is not immediately needed. And the other
observation is: The cunning bit-fiddling algorithms of the past often have
very high hidden costs because they need more registers, have strong value
dependencies (leading to pipeline stalls), interact badly with branch
prediction etc. As a result, it is not uncommon that the most
straightforward code is the fastest. In the end you have to measure... (on
various platforms) (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) [...] This is a perfect example for a bad algorithm on current CPUs: An integer
division by a constant can and should be replaced by an integer
multiplication plus some tiny correction by a shift/add, see e.g. section
"8.1 Replacing division with multiplication" in AMD's optimization guide (
http://support.amd.com/TechDocs/25112.PDF) or "Computing Magic Numbers" in
Hacker's Delight (http://www.hackersdelight.org/). Looking at e.g. the
Skylake table in http://www.agner.org/optimize/instruction_tables.pdf (the
CPU performance "bible" ;-), you can see how blazingly fast that is.
In a nutshell: We don't program on our grandpa's CPUs anymore, :-D at least
not on the desktop/server, so a lot of traditional advice from the past is
misleading nowadays.
participants (7)
-
Alexey Khudyakov -
Brandon Allbery -
David Feuer -
MarLinn -
Richard A. O'Keefe -
Steve Schafer -
Sven Panne