[fpc-devel] Proposal for 2 new compiler functions

[J. Gareth Moreton]

I can see where you're coming from here. 
If not a logarithm, what would you call 
these functions that concisely and 
compactly describes their behaviour and 
purpose? While "bit scan reverse" is 
effectively a truncated log2, with a flag 
set if the input was zero, it's not a name 
that jumps out at the user as "aah, that's 
what I need" or "ah, I know what that's 
for", and there's no equivalent to what 
I'm calling CLog2 yet.

Would "ILog2" and "CILog2" differentiate 
them enough from the mathematical 
functions?

Gareth

On Wed 13/06/18 01:56 , Wolf 
wv99999 at gmail.com sent:
> 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 [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.johngusta
fson.net/pdfs/BeatingFloatingPoin
> t.pdf[2] 
https://arxiv.org/pdf/1701.00722
> [3]
> 
http://secureweb.fast.net.uk/www.itu.dk/%7
Esestoft/bachelor/IEEE754_article
> .pdf[4] http://secureweb.fast.net.uk/ 
http:=
> [5] http://lists.freepascal.org/cgi-
bin/mailman/listinfo/fpc-devel
> [6]
> http://secureweb.fast.net.uk/parse.php?
redirect=http://lists.freepascal.org
> /cgi-bin/mailman/listinfo/fpc-devel
>