Recent

Author Topic: Odd way of calculating the Logarithm  (Read 2898 times)

Salazar

  • New Member
  • *
  • Posts: 11
Odd way of calculating the Logarithm
« on: April 20, 2021, 09:25:58 pm »
Hi all,

recently I discovered that Lazarus/FreePascal calculates
Code: Pascal  [Select][+][-]
  1. Trunc(Log2(8))
as 2. Whereas it should be 3, because
Code: Pascal  [Select][+][-]
  1. Log2(8) = 3
and Trunc(3) is 3. I suppose that internally it is calculated as some floatingpointnumber 2.99999... and then truncated to 2.

I use this calculation to determin the position (level) of a number in a binary tree for visualizing it. And this calculation worked correctly earlier. Then - maybe because of a new Lazarusversion - the calculation went wrong.

Does anyone know how this could happen and whether it is a bug in Lazarus/FPC, that should be corrected?

Sorry for the bad formatting, but if I don't quote the text as code, silly smileys are put in  :(.

By the way: I use Lazarus-Version 2.0.12 and FPC-Version 3.2.0.

Thank You for any answer!

« Last Edit: April 20, 2021, 09:55:28 pm by Salazar »

howardpc

  • Hero Member
  • *****
  • Posts: 4144
Re: Odd way of calculating the Logarithm
« Reply #1 on: April 20, 2021, 09:30:46 pm »
Trunc does exactly that: it truncates any fractional part of a number, no matter how small (.000000000000001) or large (.99999999999999999).

You are probably looking for the Round() function which returns the nearest integral value to a floating point number (and I believe does "banker's rounding" for values of x.5).

Salazar

  • New Member
  • *
  • Posts: 11
Re: Odd way of calculating the Logarithm
« Reply #2 on: April 20, 2021, 09:38:00 pm »
The Problem is, that "Round" calculates the levels wrong in principal. So what I would need is a trunc-function that works in the way that I see as mathematically correct.
« Last Edit: April 20, 2021, 11:37:22 pm by Salazar »

winni

  • Hero Member
  • *****
  • Posts: 3197
Re: Odd way of calculating the Logarithm
« Reply #3 on: April 20, 2021, 09:48:46 pm »
Hi!

Write your own round:

Code: Pascal  [Select][+][-]
  1. function RoundCorrect (s: single) : Integer;
  2. var minus : Boolean;
  3. begin
  4. minus := s < 0;
  5. result := trunc (abs(s) +0.5);
  6. if minus then result := -result;
  7. end;

Winni

Salazar

  • New Member
  • *
  • Posts: 11
Re: Odd way of calculating the Logarithm
« Reply #4 on: April 20, 2021, 10:05:11 pm »
Thank you Winni for the answer, but no "version" of rounding will do the job. The 8th number has to go to the 3rd level as all numbers up to 15. The 16th number up to the 31. goes to level 4. This could (and should) be calculated by the trunc-function (trunc(log2(number)) respectively). My question is, why it doesn't. Is this a bug in FPC?
« Last Edit: April 20, 2021, 10:13:59 pm by Salazar »

MarkMLl

  • Hero Member
  • *****
  • Posts: 6676
Re: Odd way of calculating the Logarithm
« Reply #5 on: April 20, 2021, 10:16:19 pm »
Thank you Winni for the answer, but no "version" of rounding will do the job. The 8th number has to go to the 3rd level as all numbers up to 15. The 16th number up to the 31. goes to level 4. This could (and should) be calculated by the trunc-function (trunc(log2(number)) respectively). My question is, why it doesn't. Is this a bug in FPC?

I suggest that you give us examples. If you are convinced that you have a bug then submit it via Mantis, but you'll find the bar quite high.

https://bugs.freepascal.org/bug_report_page.php

MarkMLl
MT+86 & Turbo Pascal v1 on CCP/M-86, multitasking with LAN & graphics in 128Kb.
Pet hate: people who boast about the size and sophistication of their computer.
GitHub repositories: https://github.com/MarkMLl?tab=repositories

balazsszekely

  • Guest
Re: Odd way of calculating the Logarithm
« Reply #6 on: April 20, 2021, 10:19:48 pm »
@Salazar
With Lazarus Trunk/FPC 3.2.0 works fine for me(see attached screenshot). Or perhaps I misunderstood your question?
« Last Edit: April 20, 2021, 10:23:06 pm by GetMem »

Warfley

  • Hero Member
  • *****
  • Posts: 1499
Re: Odd way of calculating the Logarithm
« Reply #7 on: April 20, 2021, 10:38:51 pm »
I use always an interger based log function for this sort of thing:
Code: Pascal  [Select][+][-]
  1. function ilog2(value: integer): Integer;
  2. begin
  3.   Result := 0;
  4.   While value shr Result > 0 do
  5.     Inc(result);
  6. end;
Untested, but something like that should do the job.

Salazar

  • New Member
  • *
  • Posts: 11
Re: Odd way of calculating the Logarithm
« Reply #8 on: April 20, 2021, 10:51:07 pm »
@GetMem

Hello GetMem,

you understood wright. Now I am completely bewildered because on my computer it does not calculate like your snippet shows. See the attachment. The executable  shows 2 instead of 3.

Maybe I did something in the context wrong?

As an example I chose:

Code: Pascal  [Select][+][-]
  1. { TfrmExampleMain }
  2.  
  3. procedure TfrmExampleMain.btnCalculateClick(Sender: TObject);
  4. begin
  5.   pnlResult.Caption := IntToStr(Trunc(Log2(8));
  6. end;

It is the same behaviour with "FloatToStr" instead of "IntToStr". I added the Math-Unit to the Uses-Clause.

Unfortunately I could not add the executable in the attachement because it exceeds the limit of 500 kb.

I don't know whether it compiles differently with other Lazarus-/FPC-Versions.
« Last Edit: April 20, 2021, 11:00:21 pm by Salazar »

Salazar

  • New Member
  • *
  • Posts: 11
Re: Odd way of calculating the Logarithm
« Reply #9 on: April 20, 2021, 10:57:29 pm »
I use always an interger based log function for this sort of thing:
Code: Pascal  [Select][+][-]
  1. function ilog2(value: integer): Integer;
  2. begin
  3.   Result := 0;
  4.   While value shr Result > 0 do
  5.     Inc(result);
  6. end;
Untested, but something like that should do the job.

That sounds like a solution to the problem, Warfley. I will try it, thank you!

Nevertheless I'd like to know, why my mentioned code does not work as expected.
« Last Edit: April 20, 2021, 11:23:11 pm by Salazar »

Bart

  • Hero Member
  • *****
  • Posts: 5275
    • Bart en Mariska's Webstek
Re: Odd way of calculating the Logarithm
« Reply #10 on: April 20, 2021, 11:01:09 pm »
Depending on your OS and CPU (bitness?) the code used to calculate log2 may differ and so might the result type.
On win32 the result type will be extended, on win64 it will be double.
Since on all systems the calculation involves floating point operations there will in most cases not be a mathematically correct return value, since most numbers cannot be represented exactly in a floating point.
So, while mathematically the result of Log2(8) equals 3 exactly, the actual result returned by the CPU might either be 2.99999999999999999999999 or 3.000000000000000000000001 or similar.

Compiled for win32 (i386 procesor) Log2(8) returns: 3.00000000000000000000E+0000, the return value being of type exyended,
Compiled for win64 (x86_64 processor) Log2(8) returns: 2.9999999999999996E+000, the return value of being type double.

i386 has dedicated asm function for Log2, x86_64 does not (in fpc 3.2.0), it calculates it as log2:=ln(x)*1.4426950408889634079;    { 1/ln(2) }

Trunc() then returns the expected result: 2 in case of 2.999999999999999, 3 in case of 3.000000000000000001.

Bart

Salazar

  • New Member
  • *
  • Posts: 11
Re: Odd way of calculating the Logarithm
« Reply #11 on: April 20, 2021, 11:14:12 pm »
@Bart

Thank you Bart, for this great detailed answer!

So the reason, why my code broke at some point must have been, when I changed from Lazarus Version 32bit to 64bit. I could not imagine this consequence  :o.

May I ask you what "dedicated function" means. As I understand from your answer it must be some "better version" of calculating log2 in a unique way for each number. Am I wright? Why isn't this implemented in 64bit?
« Last Edit: April 20, 2021, 11:21:37 pm by Salazar »

Bart

  • Hero Member
  • *****
  • Posts: 5275
    • Bart en Mariska's Webstek
Re: Odd way of calculating the Logarithm
« Reply #12 on: April 20, 2021, 11:28:12 pm »
On i386 Log2(x) is calculated like this:

Code: Pascal  [Select][+][-]
  1. function log2(x : float) : float;assembler;
  2.   asm
  3.     fld1
  4.     fldt x
  5.     fyl2x
  6.     fwait
  7.   end;

Bart

jamie

  • Hero Member
  • *****
  • Posts: 6090
Re: Odd way of calculating the Logarithm
« Reply #13 on: April 21, 2021, 12:49:06 am »
Code: Pascal  [Select][+][-]
  1. Function ILog2(x:Integer):Integer; nostackframe Assembler;
  2. Asm
  3.  bsr x,%eAx;
  4. End;
  5.  
  6. procedure TForm1.Button1Click(Sender: TObject);
  7. begin
  8.   Caption := Ilog2(8).Tostring;
  9. end;                                      
  10.  

Does that work for you?
That should work in both 32 and 64 bit of intel that is.

Not sure about the results but I am guessing that will generate the results you are looking for.

The 8 tested value results in 3 here.

The only true wisdom is knowing you know nothing

engkin

  • Hero Member
  • *****
  • Posts: 3112
Re: Odd way of calculating the Logarithm
« Reply #14 on: April 21, 2021, 01:13:36 am »
Jamie, FPC has BsrByte, BsrWord, BsrDWord, and BsrQWord.

 

TinyPortal © 2005-2018