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

On 13/06/2018 11:07, 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. 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

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

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

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

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

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

------

[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

_______________________________________________

fpc-devel maillist - fpc-***@lists.freepascal.org

http://lists.freepascal.org/cgi-bin/mailman