[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.
Wolf
>
> 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.
Wolf
>
> 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