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 [email protected] 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 [email protected]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
_______________________________________________
fpc-devel maillist - [email protected]
<mailto:[email protected]>
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 - [email protected]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
_______________________________________________
fpc-devel maillist - [email protected]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
