[fpc-devel] Proposal for 2 new compiler functions

[J. Gareth Moreton]

 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.
 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..
 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 [1] 0 and 1/0 onto the same number - a mapping that has many
advantages for computing, but eventually destroys computability [2]. 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 [3], 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
  

Links:
------
[1]
http://secureweb.fast.net.uk/www.johngustafson.net/pdfs/BeatingFloatingPoint.pdf
[2] https://arxiv.org/pdf/1701.00722
[3]
http://secureweb.fast.net.uk/www.itu.dk/%7Esestoft/bachelor/IEEE754_article.pdf
[4] mailto:fpc-devel at lists.freepascal.org
[5] 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/a57949be/attachment.html>