### Bookstore

 Computer Math and Games in Pascal (preview) Lazarus Handbook

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

#### Bart

• Hero Member
• Posts: 4415
##### 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: 1845
##### 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 ticksTest 2  CntCaseTbl     78 ticks      CntTbl     78 ticks  cntBitly64     78 ticks    cntLog10    172 ticksTest 3  CntCaseTbl     94 ticks      CntTbl     62 ticks  cntBitly64     94 ticks    cntLog10    172 ticksTest 4  CntCaseTbl     94 ticks      CntTbl     62 ticks  cntBitly64     94 ticks    cntLog10    187 ticksTest 5  CntCaseTbl     78 ticks      CntTbl     78 ticks  cntBitly64     78 ticks    cntLog10    187 ticksTest 6  CntCaseTbl     94 ticks      CntTbl     62 ticks  cntBitly64     94 ticks    cntLog10    171 ticksTest 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: 1845
##### 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.
First, provide the finished project that is being compiled, and the time the test was run.

#### Bart

• Hero Member
• Posts: 4415
##### 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
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
69.                 @bigLoop:
70.                         neg ebx
71.                         @smallLoop:
72.                                 movzx edi,byte [RAX+ebx]
73.                                 mov byte [RDX+ebx],edi
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
101.                 @bigLoop:
102.                         neg ebx
103.                         @smallLoop:
104.                                 movzx edi,byte [RAX+ebx]
105.                                 mov byte [RDX+ebx],edi
107.
108.                                 jz @breakloop
109.
110.                                 movzx edi,byte [RAX+ebx]
111.                                 mov byte [RDX+ebx],edi
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: 357
• Whasup!?
##### 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: 817
##### 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: 4415
##### 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
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
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: 4415
##### 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
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
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: 236
##### 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: 4415
##### 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