[fpc-devel] Proposal for 2 new compiler functions
J. Gareth Moreton
gareth at moreton-family.com
Wed Jun 13 02:13:27 CEST 2018
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
>
More information about the fpc-devel
mailing list