[fpc-devel] Proposal for 2 new compiler functions

Wolf wv99999 at gmail.com
Wed Jun 13 02:56:22 CEST 2018

On 13/06/2018 11:07, J. Gareth Moreton wrote:
> Well, I would argue that when computing log(x) of any base, as x tends 
> to 0 from a positive number, log(x) becomes a progressively more 
> negative number to the point that, yes, it's undefined, but that's 
> only going by the definition of limits.
> The issue here is that my proposed logarithm functions work not on 
> floating-point numbers, but integers, primarily for the sake of speed 
> and application.  There is no way to store a NaN or plus or minus 
> infinity in an integral type, which means the only other option is to 
> raise an exception.
That's why I am willing to withdraw my objections, as stated, the moment 
you remove log from the function name. What you want to use is a 
function of your own design, with value mappings different from what a 
logarithm does. My objection is not about your optimization work, it is 
about potential mis-use of your work, and mis-understandings by any 
future maintainer of your work.
> For truly mathematical functions with a continuous domain, then yes, 
> it should return proper values.  I suppose what I'm proposing is not 
> the true base-2 logarithm, but two functions that do the following:
> FLog2(x), x element of N (natural numbers), including zero
> 0, x = 0
> floor(log2(x)); x ≠ 0
> CLog2(x), x element of N, including zero
> 0, x = 0
> ceil(log2(x)); x ≠ 0
> (Not easy to describe when you can't use proper mathematical notation 
> in an e-mail!)
> In this instance, it's less about mathematical correctness and more 
> for the sake of convenience, because only a single input (zero) would 
> be undefined, and for the sake of bit lengths and loop iterations, 0 
> is a more convenient value than throwing an exception or returning 
> something undefined or potentially hazardous like $FFFFFFFF, which if 
> passed blindly into a for-loop, will cause 4.29 billion iterations..
I understand that, and if you want to use a Bit Scan Reverse 
instruction, use it. But do not call it a logarithm, because that has 
implications . . .  Take a look at the *[fpc-pascal] round(2.5)=2* 
thread. Why is nobody there suggesting to look for Intel to sort out his 
/her rounding issues? That thread displays the kind of blindness I am 
concerned about. The answers are available, but hidden in massive 
documentation, as you yourself noticed so recently.
> Gareth
> On Wed 13/06/18 00:45 , Wolf wv99999 at gmail.com sent:
>     Hi
>     I object to one component of Gareth's proposal - to make
>     log2(0)=0. The problem lies not with what Gareth wants to do with
>     it, but what other people will use it for once it becomes
>     available.  log2(0) is undefined (and undefinable, as it is not a
>     computable number), the appropriate choice for log2(0) is to make
>     it Not-A-Number (NaN).
>     FLog2(0) = NaN = CLog2.
>     Such a choice would avoid the mess Gustavson got himself into when
>     he mapped <www.johngustafson.net/pdfs/BeatingFloatingPoint.pdf> 0
>     and 1/0 onto the same number - a mapping that has many advantages
>     for computing, but eventually destroys computability
>     <https://arxiv.org/pdf/1701.00722>. To a lesser degree, this mess
>     is already present in the IEEE 754 standard for floating-point
>     arithmetic, and thus led to, to put it mildly, computing
>     difficulties <www.itu.dk/%7Esestoft/bachelor/IEEE754_article.pdf>,
>     difficulties that many programmers gloss over - or simply ignore.
>     I will have to say more about this when I am ready to file a bug
>     report on floating point exceptions, since Gareth's proposal has
>     deep links to how floating point numbers are defined - and why
>     they were defined such.
>     Wolf
>     On 13/06/2018 00:42, J. Gareth Moreton wrote:
>>     Hi everyone,
>>     Sorry to flood the mailing list again with more ideas and
>>     experiments.
>>     I would like to propose introducing a new pair of in-built
>>     functions for the compiler.
>>     function FLog2(X: Cardinal): Cardinal;
>>     function CLog2(X: Cardinal): Cardinal;
>>     FLog2 returns the base-2 logarithm of X, rounded down, while
>>     CLog2 returns the base-2 logarithm of X, rounded up.
>>     To give examples where these functions could be useful, FLog2(X)
>>     + 1 indicates the minimum number of bits required to store X as
>>     an unsigned integer, while CLog2(X) is equal to the maximum
>>     number of iterations required for a binary search of an X-sized list.
>     Given the stated purpose, I could withdraw my objection if any
>     reference to logarithm was removed from the function and its name.
>     Then Gareth would be free to create his function any way he likes
>     and assign to it the properties he chooses. The only requirement
>     left then would be to state in the comments around the function
>     what it is supposed to achieve, as a deterrence to mis-use and
>     guidance to future maintainers, who may not think the same as
>     Gareth does.
>>     Why should they be in-built though? With the binary search
>>     example, the size of the list is sometimes known at compile time,
>>     hence is a constant - therefore, its logarithm is also a
>>     constant.  By pre-calculating the logarithm using the in-built
>>     function, it can be used to aid optimization such as loop
>>     unrolling.  It also makes them easier to inline, where FLog2(X)
>>     on x86_64-win64 translates to a single line of assembly language:
>>     BSR EAX, ECX (unless X is zero, in which case ZF is set and EAX
>>     is undefined).
>>     If there had to be a slight nuance though, it's what happens if X
>>     = 0, since log(0) = -oo
>     This statement is false. log(0) is not infinity. To obtain a
>     numerical value for log(0) by e.g. Taylor series expansion, at one
>     stage you have to divide by zero since the differential
>     (d ln x )/ d x = 1/x.
>      And since 1/0 is not an element of the set of computable numbers,
>     log(0) is not either. The only valid assignment can be
>     log(0):=NaN, for any base.
>>     , which cannot be stored as an integer and may cause problems
>>     with the compiler.  I would propose it return 0 as a special
>>     case, as this will fix most problems when it comes to loops and
>>     storage, and also ensure that FLog2 and CLog2 are "entire
>>     functions".  To give an optimised example of FLog(2) in x86-64
>>     assembly language:
>>     XOR EDX, EDX
>>     BSR EAX, ECX // ZF is set if ECX is zero
>>     CMOVZ EAX, EDX // Zero (EDX) written to result if ZF is set.
>>     Some kind of deep optimization could be used if the input is
>>     known to be non-zero and remove the instructions either side of BSR.
>>     (Alternative names: FILog2 and CILog2, to indicate they work on
>>     integers and to distinguish them from versions that work with
>>     floating-point numbers)
>>     Gareth
>>     _______________________________________________
>>     fpc-devel maillist -fpc-devel at lists.freepascal.org  
>>     http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel  
>     _______________________________________________
>     fpc-devel maillist - fpc-devel at lists.freepascal.org
>     <mailto:fpc-devel at lists.freepascal.org>
>     http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
>     <%3Ca%20href=>">http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
> _______________________________________________
> fpc-devel maillist  -  fpc-devel at lists.freepascal.org
> http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.freepascal.org/pipermail/fpc-devel/attachments/20180613/eeb60103/attachment.html>

More information about the fpc-devel mailing list