Recent

Author Topic: simple problem: count digits of number  (Read 22991 times)

Bart

  • Hero Member
  • *****
  • Posts: 4342
    • Bart en Mariska's Webstek
Re: simple problem: count digits of number
« Reply #30 on: March 03, 2018, 06:39:46 pm »
Why not:
Code: Pascal  [Select][+][-]
  1. const
  2.   digitsArr : packed array[UInt64] of byte =
  3.      (1,1,1,1,1,1,1,1,1,1
  4.       2,2,2,2,2,2,2,2,2,2,
  5.       ......
  6.      20,20,20,20,20,20,20,20,20,20);

This should account for just 18446744073709551616 bytes of static data (a mere 16777216 TB, so definitely not too much).
The resulting executable should fit on 12509998964918045 3.5" DSDD floppy disks (I still have a collection of those), if I did my calculations correctly.

Bart

ASerge

  • Hero Member
  • *****
  • Posts: 1815
Re: simple problem: count digits of number
« Reply #31 on: March 03, 2018, 08:40:13 pm »
Corrected the range check errors.
OK. The testing project is included. Result:
Code: [Select]
Test 1
  CntCaseTbl     93 ticks
      CntTbl     63 ticks
  cntBitly64     93 ticks
    cntLog10    188 ticks
Test 2
  CntCaseTbl     78 ticks
      CntTbl     78 ticks
  cntBitly64     78 ticks
    cntLog10    172 ticks
Test 3
  CntCaseTbl     94 ticks
      CntTbl     62 ticks
  cntBitly64     94 ticks
    cntLog10    172 ticks
Test 4
  CntCaseTbl     94 ticks
      CntTbl     62 ticks
  cntBitly64     94 ticks
    cntLog10    187 ticks
Test 5
  CntCaseTbl     78 ticks
      CntTbl     78 ticks
  cntBitly64     78 ticks
    cntLog10    187 ticks
Test 6
  CntCaseTbl     94 ticks
      CntTbl     62 ticks
  cntBitly64     94 ticks
    cntLog10    171 ticks
Test 7
  CntCaseTbl     94 ticks
      CntTbl     62 ticks
  cntBitly64     94 ticks
    cntLog10    187 ticks

isidroco

  • New Member
  • *
  • Posts: 12
Re: simple problem: count digits of number
« Reply #32 on: March 03, 2018, 11:21:31 pm »
Thanks for your wonderful additions, will try my last attemp in building the dumbest function:

Code: Pascal  [Select][+][-]
  1. function cntDumb(Z: int64): integer;
  2. begin
  3.   if abs(z)= 0 then cntDumb:=1;
  4.   if abs(z)= 1 then cntDumb:=1;
  5.   if abs(z)= 2 then cntDumb:=1;
  6.   if abs(z)= 3 then cntDumb:=1;
  7.   if abs(z)= 4 then cntDumb:=1;
  8.   if abs(z)= 5 then cntDumb:=1;
  9.   if abs(z)= 6 then cntDumb:=1;
  10.   if abs(z)= 7 then cntDumb:=1;
  11.   if abs(z)= 8 then cntDumb:=1;
  12.   if abs(z)= 9 then cntDumb:=1;
  13.   if abs(z)= 10 then cntDumb:=2;
  14.   ........
  15.   if abs(z)= maxInt then cntDumb:=20;
  16. end;
  17.  
Advantages: No variables are used, and will take a constant (long) time because the absence of ELSEs.
I want my prize now. :)
Isidro.
[/quote]
« Last Edit: March 08, 2018, 01:35:46 am by isidroco »

ASerge

  • Hero Member
  • *****
  • Posts: 1815
Re: simple problem: count digits of number
« Reply #33 on: March 04, 2018, 12:09:25 am »
Advantages: No variables are used, and will take a constant (long) time because the absence of ELSEs.
I want my price now. :)
;D First, provide the finished project that is being compiled, and the time the test was run.

Bart

  • Hero Member
  • *****
  • Posts: 4342
    • Bart en Mariska's Webstek
Re: simple problem: count digits of number
« Reply #34 on: March 04, 2018, 12:18:50 am »
Code: Pascal  [Select][+][-]
  1. ...
  2.   if abs(z)= maxInt then cntDumb:=20;
  3. end;
  4.  

Max(Long)Int = 2147483647, so not only will your code be slow, it will also be flawed, so: no price for you  O:-)
High(UInt64) = 18446744073709551616, which is 20 digits ....

Bart

Solecist

  • New member
  • *
  • Posts: 7
Re: simple problem: count digits of number
« Reply #35 on: June 22, 2021, 01:47:34 am »
I felt like it's appropriate to post in here, instead of making a new thread without any context.

Code: Pascal  [Select][+][-]
  1. {$asmmode intel}
  2. {$mode objfpc}
  3. Program cpu_CountDigits;
  4. Uses Math,SysUtils,Windows;
  5. Var
  6.         _DigitCount : Array[Word] of Byte;
  7.         DigitCount : Pointer;
  8.  
  9.         q,w,e : DWord;
  10.         f,c,cc : int64;
  11.  
  12.         Results : Array[Word] of Byte;
  13.  
  14. Function CountDigits(where : Pointer; n : Word) : DWord; inline; Assembler;
  15. Asm
  16.         movzx eax,byte [where+n]
  17. End;
  18.  
  19. Begin
  20.         Randomize;
  21.         QueryPerformanceFrequency(f);
  22.  
  23.         For q := 0 to 65535 do _DigitCount[q] := length(IntToStr(q));
  24.         DigitCount := @_DigitCount[0];
  25.  
  26.  
  27.  
  28. // -----------------------------------------------
  29.  
  30.  
  31.         QueryPerformanceCounter(c);
  32.  
  33.         for q := 0 to 15257 do
  34.         for w := 0 to 65535 do // one billion
  35.                 e := CountDigits(DigitCount,w);
  36.        
  37.         QueryPerformanceCounter(cc);
  38.  
  39.         writeln(FormatFloat('0.0000',(cc-c)/f)); // in Seconds.
  40.  
  41.  
  42. // -----------------------------------------------
  43.  
  44.         QueryPerformanceCounter(c);
  45.  
  46.         for q := 0 to 15257 do
  47.         for w := 0 to 65535 do // one billion
  48.                 e := _DigitCount[w];
  49.        
  50.         QueryPerformanceCounter(cc);
  51.  
  52.         writeln(FormatFloat('0.0000',(cc-c)/f)); // in Seconds.
  53.  
  54.  
  55. // -----------------------------------------------
  56.  
  57.  
  58.         FillChar(Results,sizeof(Results),0);
  59.  
  60.         QueryPerformanceCounter(c);
  61.  
  62.         Asm
  63.                 mov rax,DigitCount
  64.                 lea rdx,Results[0]
  65.                 mov rbx,65535
  66.                 mov ecx,15257
  67.                 add rdx,rbx
  68.                 add rax,rbx
  69.                 @bigLoop:
  70.                         neg ebx
  71.                         @smallLoop:
  72.                                 movzx edi,byte [RAX+ebx]
  73.                                 mov byte [RDX+ebx],edi
  74.                                 add ebx,1
  75.                         jnz @smallLoop
  76.                         mov rbx,65535
  77.                 sub ecx,1
  78.                 jnz @bigLoop
  79.         End;
  80.  
  81.         QueryPerformanceCounter(cc);
  82.  
  83.         writeln(FormatFloat('0.0000',(cc-c)/f)); // in Seconds.
  84.         // for q := 0 to 65535 do write(Results[q],' ');
  85.  
  86.  
  87. // -----------------------------------------------
  88.  
  89.  
  90.         FillChar(Results,sizeof(Results),0);
  91.  
  92.         QueryPerformanceCounter(c);
  93.  
  94.         Asm
  95.                 mov rax,DigitCount
  96.                 lea rdx,Results[0]
  97.                 mov rbx,65535
  98.                 mov ecx,7629
  99.                 add rax,rbx
  100.                 add rdx,rbx
  101.                 @bigLoop:
  102.                         neg ebx
  103.                         @smallLoop:
  104.                                 movzx edi,byte [RAX+ebx]
  105.                                 mov byte [RDX+ebx],edi
  106.                                 add ebx,1
  107.  
  108.                                 jz @breakloop
  109.  
  110.                                 movzx edi,byte [RAX+ebx]
  111.                                 mov byte [RDX+ebx],edi
  112.                                 add ebx,1
  113.                         jnz @smallLoop
  114.  
  115.                         @breakloop:
  116.                         mov rbx,65535
  117.                 sub ecx,1
  118.                 jnz @bigLoop
  119.         End;
  120.  
  121.         QueryPerformanceCounter(cc);
  122.  
  123.         writeln(FormatFloat('0.0000',(cc-c)/f)); // in Seconds.
  124.         // for q := 0 to 65535 do write(Results[q],' ');
  125.  
  126.  
  127. End.

Results on my G15 Zephyrus with R5900HS and 16gig of 3200 DDR in Dual Channel mode,
for roughly a billion lookups,
in seconds:

0.5174
1.5414
0.2522
0.1258

Roughly. Every run gives around the same result. Obviously all the data is in the cache,
but because of the easy parallelism you'd probably want to run through all your numbers at once and save the results for further usage.

I needed this and was wondering if there were clever solutions. After reading the first page I rather came up with my own solution,
so I've implemented the above instead. I don't need a lot of range, so 64k as a limit is fine. It's easily extended to 16megs range, too.

This can be further optimized and is going to be faster on Intel processors due to their lower access latency.
Please note that the function isn't being inlined. The code's probably ugly, but works.

I hope it helps someone! o/
« Last Edit: June 22, 2021, 01:55:18 am by Solecist »

Kays

  • Sr. Member
  • ****
  • Posts: 328
  • Whasup!?
    • KaiBurghardt.de
Re: simple problem: count digits of number
« Reply #36 on: June 22, 2021, 02:21:20 pm »
[…] or
Code: Pascal  [Select][+][-]
  1. uses Math;
  2.  
  3. function countZiff (inZahl : tNatZahl) : tNatZahl;
  4. begin
  5.   Result := Floor(Log10(inZahl));
  6. end;
  7.  
OMG. It’s surprising that I didn’t see that off-by-one-mistake when I read this topic back in 2018. It’s of course supposed to read like:
Code: Pascal  [Select][+][-]
  1. uses
  2.         math;
  3.  
  4. function digitWidth(n: ALUSInt): ALUSInt;
  5. begin
  6.         n := abs(n);
  7.         digitWidth := 1;
  8.         { actually `n > 9`, yet `n > 0` generates `test rdi, rdi`}
  9.         if n > 0 then
  10.         begin
  11.                 inc(digitWidth, trunc(log10(n)));
  12.         end;
  13. end;
Yours Sincerely
Kai Burghardt

BeniBela

  • Hero Member
  • *****
  • Posts: 800
    • homepage
Re: simple problem: count digits of number
« Reply #37 on: June 22, 2021, 02:36:31 pm »
Recently I came across a blog post about this:  https://lemire.me/blog/2021/06/03/computing-the-number-of-digits-of-an-integer-even-faster/

Here is also some more discussion: https://news.ycombinator.com/item?id=27394153

Does fpc have a integer log2 or count leading binary zeros function?
« Last Edit: June 22, 2021, 02:44:21 pm by BeniBela »

Bart

  • Hero Member
  • *****
  • Posts: 4342
    • Bart en Mariska's Webstek
Re: simple problem: count digits of number
« Reply #38 on: June 22, 2021, 07:17:31 pm »
I have this:

Code: Pascal  [Select][+][-]
  1. function Log2(n: uint64; RoundDown: Boolean): Integer;  overload;
  2. //implements an integer version of Log2
  3. //using floor() or ceil() on Math.Log2() gives rouding errors
  4. var
  5.   temp: uint64;
  6. begin
  7.   Result := 0;
  8.   temp := 1;
  9.   while (temp < n) do
  10.   begin
  11.     Inc(Result);
  12.     if (Result = 64) then
  13.       temp := high(uint64)
  14.     else
  15.       temp := uint64(1) shl Result;
  16.   end;
  17.   if RoundDown and ((temp > n) or (Result = 64)) then
  18.     Dec(Result);
  19. end;
  20.  
  21. function TrailingZeroBits(n: UInt64): Integer;
  22. var
  23.   Mask: Integer;
  24. begin
  25.   Result := 0;
  26.   while (Result < SizeOf(UInt64)*8) do
  27.   begin
  28.     Mask := 1 shl Result;
  29.     if (n and Mask) <> 0 then Exit;
  30.     Inc(Result);
  31.   end;
  32. end;
  33.  
  34. function TrailingZeroBits(n: Int64): Integer; inline;
  35. begin
  36.   Result := TrailingZeroBits(UInt64(n));
  37. end;
  38.  
  39. function TrailingOneBits(n: UInt64): Integer;
  40. var
  41.   Mask: Integer;
  42. begin
  43.   Result := 0;
  44.   while (Result < SizeOf(UInt64)*8) do
  45.   begin
  46.     Mask := 1 shl Result;
  47.     if (n and Mask) = 0 then Exit;
  48.     Inc(Result);
  49.   end;
  50. end;
  51.  
  52. function TrailingOneBits(n: Int64): Integer; inline;
  53. begin
  54.   Result := TrailingOneBits(UInt64(n));
  55. end;
  56.  
  57. function Parity(n: Integer): Integer;
  58. var
  59.   Mask, I, Bits: Integer;
  60. begin
  61.   Bits := 0;
  62.   for I := 0 to SizeOf(Integer)*8 - 1 do
  63.   begin
  64.     Mask := 1 shl I;
  65.     if ((n and Mask) <> 0) then Inc(Bits);
  66.   end;
  67.   Result := Ord(Odd(Bits));
  68. end;

Leading zero's/one's should be equally simple to calculate.

(The poor man's solution: use .ToBinString and the a for loop on the resulting string: accurate but rather slow...)

Bart

Bart

  • Hero Member
  • *****
  • Posts: 4342
    • Bart en Mariska's Webstek
Re: simple problem: count digits of number
« Reply #39 on: June 22, 2021, 08:08:22 pm »
I cooked up this:

Code: Pascal  [Select][+][-]
  1. function LeadingZeroBits(n: QWORD; BitSize: Integer): Integer;
  2. var
  3.   Mask: QWORD;
  4.   L: Integer;
  5. begin
  6.   Result := 0;
  7.   for L := BitSize - 1 downto 0 do
  8.   begin
  9.     Mask := QWORD(1) shl L;
  10.     if (n and Mask) <> 0 then Exit;
  11.     Inc(Result);
  12.   end;
  13. end;
  14.  
  15. function LeadingZeroBits(n: QWORD): Integer; inline;
  16. begin
  17.   Result := LeadingZeroBits(n, SizeOf(QWORD)*8);
  18. end;
  19.  
  20. function LeadingZeroBits(n: DWORD): Integer; inline;
  21. begin
  22.   Result := LeadingZeroBits(n, SizeOf(DWORD)*8);
  23. end;
  24.  
  25. function LeadingZeroBits(n: WORD): Integer; inline;
  26. begin
  27.   Result := LeadingZeroBits(n, SizeOf(WORD)*8);
  28. end;
  29.  
  30. function LeadingZeroBits(n: Byte): Integer; inline;
  31. begin
  32.   Result := LeadingZeroBits(n, SizeOf(Byte)*8);
  33. end;
  34.  
  35. function LeadingZeroBits(n: Int64): Integer; inline;
  36. begin
  37.   Result := LeadingZeroBits(QWORD(n));
  38. end;
  39.  
  40. function LeadingZeroBits(n: Int32): Integer; inline;
  41. begin
  42.   Result := LeadingZeroBits(DWORD(n));
  43. end;
  44.  
  45. function LeadingZeroBits(n: Int16): Integer; inline;
  46. begin
  47.   Result := LeadingZeroBits(Word(n));
  48. end;
  49.  
  50. function LeadingZeroBits(n: Int8): Integer; inline;
  51. begin
  52.   Result := LeadingZeroBits(Byte(n));
  53. end;
  54.  
  55.  
  56.  
  57. function LeadingOneBits(n: QWORD; BitSize: Integer): Integer;
  58. var
  59.   Mask: QWORD;
  60.   L: Integer;
  61. begin
  62.   Result := 0;
  63.   for L := BitSize - 1 downto 0 do
  64.   begin
  65.     Mask := QWORD(1) shl L;
  66.     if (n and Mask) = 0 then Exit;
  67.     Inc(Result);
  68.   end;
  69. end;
  70.  
  71. function LeadingOneBits(n: QWORD): Integer; inline;
  72. begin
  73.   Result := LeadingOneBits(n, SizeOf(QWORD)*8);
  74. end;
  75.  
  76. function LeadingOneBits(n: DWORD): Integer; inline;
  77. begin
  78.   Result := LeadingOneBits(n, SizeOf(DWORD)*8);
  79. end;
  80.  
  81. function LeadingOneBits(n: WORD): Integer; inline;
  82. begin
  83.   Result := LeadingOneBits(n, SizeOf(WORD)*8);
  84. end;
  85.  
  86. function LeadingOneBits(n: Byte): Integer; inline;
  87. begin
  88.   Result := LeadingOneBits(n, SizeOf(Byte)*8);
  89. end;
  90.  
  91. function LeadingOneBits(n: Int64): Integer; inline;
  92. begin
  93.   Result := LeadingOneBits(QWORD(n));
  94. end;
  95.  
  96. function LeadingOneBits(n: Int32): Integer; inline;
  97. begin
  98.   Result := LeadingOneBits(DWORD(n));
  99. end;
  100.  
  101. function LeadingOneBits(n: Int16): Integer; inline;
  102. begin
  103.   Result := LeadingOneBits(Word(n));
  104. end;
  105.  
  106. function LeadingOneBits(n: Int8): Integer; inline;
  107. begin
  108.   Result := LeadingOneBits(Byte(n));
  109. end;

Bart
« Last Edit: June 22, 2021, 08:11:10 pm by Bart »

MathMan

  • Full Member
  • ***
  • Posts: 227
Re: simple problem: count digits of number
« Reply #40 on: June 23, 2021, 09:47:23 am »
Hm, looking through the RTL I do see - BsrQWord, BsrDWord, BsrWord.

Looking at generated asm they do indeed produce a BSR instruction (on x86 of course) plus a check for value=0.

They unfortunately return 255 for value=0. However the last can easily be circumvented in this case by e.g. BsrQWord( value or 1 ).

The implementations shown in the linked blog-post of Daniel Lemire can more or less directly be translated to Pascal. If I remember correct then engkin related to a precursor of this approach already during the discussions in 2018. ;-)

Cheers,
MathMan

Bart

  • Hero Member
  • *****
  • Posts: 4342
    • Bart en Mariska's Webstek
Re: simple problem: count digits of number
« Reply #41 on: June 23, 2021, 07:19:42 pm »
Changed it into:

Code: Pascal  [Select][+][-]
  1. function LeadingZeroBits(n: QWORD; BitSize: Integer): Integer;
  2. begin
  3.   if (n = 0) then
  4.     Exit(BitSize);
  5.   Result := BitSize - 1 {%H-}- BsrQWORD(n);
  6. end;/code]
  7.  
  8. Bart

 

TinyPortal © 2005-2018