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