Standart function for length of decimal number

[avk]

...
If I replace the trunc(log2(i)) with this:
...

Maybe it's better to replace it with BsrDWord()?
And random number generation isn't free, it can significantly distort the results.

[Warfley]

And random number generation isn't free, it can significantly distort the results.

Yes of course it's not free, but I use the exact same random number generator for each test, and the number of iterations is so high that the expected error is vanishingly small. As the differences are in order of magnitude, there is no reason to believe that suddenly the rng iterations 300000000 to 399999999 take significantly more time than the rng iterations 400000000 to 499999999.

But in my tests I also varied the order in which I performed the tests to rule that out, I simply did not post it here, because I don't do a full statistical analysis for a simple benchmark. But there is no statistical or technical reason why the same RNG that is used hundred of millions of times in this code suddenly would behave completely differently just for one of those measures

[avk]

All I meant was that the time spent generating random numbers obscures the real performance ratio of the different versions of the function.

Code: Pascal  [Select][+][-]

1. program Project1;
2.  
3. {$mode objfpc}{$H+}
4.  
5. uses sysutils,Math;
6.  
7. function DecLength(i: DWord): SizeUInt;inline;
8. const
9.   CTable: array [0..31] of QWord = (
10.     4294967296,  8589934582,  8589934582,  8589934582,
11.     12884901788, 12884901788, 12884901788, 17179868184,
12.     17179868184, 17179868184, 21474826480, 21474826480,
13.     21474826480, 21474826480, 25769703776, 25769703776,
14.     25769703776, 30063771072, 30063771072, 30063771072,
15.     34349738368, 34349738368, 34349738368, 34349738368,
16.     38554705664, 38554705664, 38554705664, 41949672960,
17.     41949672960, 41949672960, 42949672960, 42949672960
18.   );
19. begin
20.   if i = 0 then
21.     Result:= 1
22.   else
23.     //Result:= (i + CTable[Trunc(Log2(i))]) shr 32;
24.     Result := (i + CTable[BsrDWord(i)]) shr 32;
25. end;
26.  
27. function IntLog10(v: DWord): SizeUInt; inline;
28. begin
29.   Result:=0;
30.   While v>=10 do
31.   begin
32.     Inc(Result);
33.     v := v div 10;
34.   end;
35. end;
36.  
37. function TruncLog10(v: DWord): SizeUInt; inline;
38. begin
39.   if v=0 then
40.     Result:=0
41.   else
42.     Result:=trunc(log10(v));
43. end;
44.  
45. function StrLen(v: DWord): SizeUInt; inline;
46. begin
47.   Result:=Length(IntToStr(v));
48. end;
49.  
50. function LookUp(v: DWord): SizeInt; inline;
51. const
52.   LATable: array [2..10] of QWord = (10,  100,  1000,  10000, 100000, 1000000, 10000000, 100000000, 1000000000);
53. begin
54.   for Result:=High(LATable) downto Low(LATable) do
55.     if v >= LATable[Result] then
56.       Exit;
57.   Result:=1;
58. end;
59.  
60. function Hardcode(v: DWord): SizeInt; inline;
61. begin
62.   case v of
63.   0..9: Result:=1;
64.   10..99: Result:= 2;
65.   100..999: Result:=3;
66.   1000..9999: Result:=4;
67.   10000..99999: Result:=5;
68.   100000..999999: Result:=6;
69.   1000000..9999999: Result:=7;
70.   10000000..99999999: Result:=8;
71.   100000000..999999999: Result:=9;
72.   otherwise Result:=10;
73.   end;
74. end;
75.  
76. const
77.   laps=100000000;
78. var
79.   s: QWord;
80.   x, i: Integer;
81.   a: array of DWord = nil;
82. begin
83.   SetLength(a, laps);
84.   for i := 0 to High(a) do
85.     a[i] := Random(MaxInt);
86.  
87.   x:=0;
88.   s:=GetTickCount64;
89.   for i := 0 to High(a) do
90.     x:=x+DecLength(a[i]);
91.   WriteLn('DecLength: ', GetTickCount64-s);
92.  
93.   s:=GetTickCount64;
94.   for i := 0 to High(a) do
95.     x:=x+IntLog10(a[i]) + 1;
96.   WriteLn('IntLog10: ', GetTickCount64-s);
97.  
98.   s:=GetTickCount64;
99.   for i := 0 to High(a) do
100.     x:=x+TruncLog10(a[i]) + 1;
101.   WriteLn('TruncLog10: ', GetTickCount64-s);
102.  
103.   s:=GetTickCount64;
104.   for i := 0 to High(a) do
105.     x:=x+StrLen(a[i]);
106.   WriteLn('StrLen: ', GetTickCount64-s);
107.  
108.   s:=GetTickCount64;
109.   for i := 0 to High(a) do
110.     x:=x+LookUp(a[i]);
111.   WriteLn('LookUp: ', GetTickCount64-s);
112.  
113.   s:=GetTickCount64;
114.   for i := 0 to High(a) do
115.     x:=x+Hardcode(a[i]);
116.   WriteLn('Hardcode: ', GetTickCount64-s);
117. end.
118.  

On my machine it prints

Code: [Select]

DecLength: 156
IntLog10: 1185
TruncLog10: 3681
StrLen: 4088
LookUp: 546
Hardcode: 826


[MathMan]

...
If I replace the trunc(log2(i)) with this:
...

Maybe it's better to replace it with BsrDWord()?
And random number generation isn't free, it can significantly distort the results.

Sorry, I should have followed up earlier - BsrDWord of course is the correct approach to Log2(i).

So thanks avk for stepping in.

[Thaddy]

Well, I just wanted to show the power of LUT and that wasn' t far off, although it was a hexagonal wheel...

[LemonParty]

Does anybody know how to find magical numbers for 64 bit version of DecLength?

[MathMan]

Is there a standart function that return number of decimal digits in signed/unsigned integer?

Fortunately that has been researched already. I suggest looking at https://lemire.me/blog/2021/06/03/computing-the-number-of-digits-of-an-integer-even-faster/

The solution presented is extremely fast for UInt32 and - once you understood the algorithm - extendable to UInt64.

Regards,
MathMan

I translated code into Pascal. But I don't know how to implemet it for 64 bit.

Code: Pascal  [Select][+][-]

1. uses Math;
2.  
3. function DecLength(i: DWord): SizeUInt;inline;
4. const
5.   CTable: array [0..31] of QWord = (
6.     4294967296,  8589934582,  8589934582,  8589934582,
7.     12884901788, 12884901788, 12884901788, 17179868184,
8.     17179868184, 17179868184, 21474826480, 21474826480,
9.     21474826480, 21474826480, 25769703776, 25769703776,
10.     25769703776, 30063771072, 30063771072, 30063771072,
11.     34349738368, 34349738368, 34349738368, 34349738368,
12.     38554705664, 38554705664, 38554705664, 41949672960,
13.     41949672960, 41949672960, 42949672960, 42949672960
14.   );
15. begin
16.   if i = 0 then
17.     Result:= 1
18.   else
19.     Result:= (i + CTable[Trunc(Log2(i))]) shr 32;
20. end;
21.  
22. function DecLength(i: LongInt): SizeUInt;inline;
23. begin
24.   if i < 0 then
25.     Result:= 1 + DecLength(DWord(-i))
26.   else
27.     Result:= DecLength(DWord(i));
28. end;
29.  

Hello LemonParty,

On a second look maybe I was a bit hasty with my statement "it can be extended to UInt64". I think it can be extended, but this might become non-trivial - t.i. can not simply be derived from the UInt32 approach. I'll have a look and come back around tomorrow / Sunday latest.

Cheers,
MathMan

[Thaddy]

This one is surprisingly fast and does not need math unit nor table:

Code: Pascal  [Select][+][-]

1. //    CTable[k] = ceil( (2^k) * (log2(10) - 1) ) * 2^(64 - k)   [maybe?]
2. {$mode objfpc}
3. function DecLength(i: QWord): SizeUInt; inline;overload;
4. begin
5.   case i of
6.   0..9:result := 1;
7.   10..99: result := 2;
8.   100..999:result := 3;
9.   1000..9999:result := 4;
10.   10000..99999:result := 5;
11.   100000..999999:result := 6;
12.   1000000..9999999:result := 7;
13.   10000000..99999999:result := 8;
14.   100000000..999999999:result := 9;
15.   1000000000..9999999999:result := 10;
16.   10000000000..99999999999:result := 11;
17.   100000000000..999999999999:result := 12;
18.   1000000000000..9999999999999:result := 13;
19.   10000000000000..99999999999999:result := 14;
20.   100000000000000..999999999999999:result := 15;
21.   1000000000000000..9999999999999999:result := 16;
22.   10000000000000000..99999999999999999:result := 17;
23.   100000000000000000..999999999999999999:result := 18;
24.   1000000000000000000..9999999999999999999:result := 19
25.   else result := 20;
26.   end;
27. end;
28. // bonus for int64
29. function DecLength(i: Int64): SizeUInt; inline;overload;
30. begin
31.   if i < 0 then
32.     Result := 1 + DecLength(QWord(-i))// calls above, this is not recursion
33.   else
34.     Result := DecLength(QWord(i));// calls above, this is not recursion
35. end;
36. begin
37. end.

A lookup table might still be faster, though. Although this is just cmp/jmp/load as a ladder.

[d2010]

This one is surprisingly fast and does not need math unit nor table:

Code: Java  [Select][+][-]

1. //    CTable[k] = ceil( (2^k) * (log2(10) - 1) ) * 2^(64 - k)   [maybe?]
2. {$mode objfpc}
3. function DecLength(i: QWord): SizeUInt; inline;overload;
4. begin
5.   case i of
6.   0..9:result := 1;
7.   10..99: result := 2;
8.   100..999:result := 3;
9.   1000..9999:result := 4;
10.   10000..99999:result := 5;
11.   100000..999999:result := 6;
12.   1000000..9999999:result := 7;
13.   10000000..99999999:result := 8;
14.   100000000..999999999:result := 9;
15.   1000000000..9999999999:result := 10;
16.   10000000000..99999999999:result := 11;
17.   100000000000..999999999999:result := 12;
18.   1000000000000..9999999999999:result := 13;
19.   10000000000000..99999999999999:result := 14;
20.   100000000000000..999999999999999:result := 15;
21.   1000000000000000..9999999999999999:result := 16;
22.   10000000000000000..99999999999999999:result := 17;
23.   100000000000000000..999999999999999999:result := 18;
24.   1000000000000000000..9999999999999999999:result := 19
25.   else result := 20;
26.   end;
27. end;
28. // bonus for int64
29. function DecLength(i: Int64): SizeUInt; inline;overload;
30. begin
31.   if i < 0 then
32.     Result := 1 + DecLength(QWord(-i))// calls above, this is not recursion
33.   else
34.     Result := DecLength(QWord(i));// calls above, this is not recursion
35. end;
36. begin
37. end.

A lookup table will likely still be faster, though. Although this is just cmp/jmp/load as a ladder.

You code is great funnym great funny (my e.g.  from You
  10000000000000..99999999999999:result := 14;
)_
Please, You use this trick, You rewrite for your-needs,at means You convert
to Qword the "IntToStr_AZ_Pas_1_a"

Code: Pascal  [Select][+][-]

1. Function IntToStr_AZ_Pas_1_a(V: Integer): word;
2. Begin
3.   if v >= 1000000000 then result := 10 else
4.   if v >= 100000000  then result :=  9 else
5.   if v >= 10000000   then result :=  8 else
6.   if v >= 1000000    then result :=  7 else
7.   if v >= 100000     then result :=  6 else
8.   if v >= 10000      then result :=  5 else
9.   if v >= 1000       then result :=  4 else
10.   if v >= 100        then result :=  3 else
11.   if v >= 10         then result :=  2 else result:= 1;
12.  urlmon:='Eu multumesc Ilie lacatusu. Doamne ajuta, Doamne ajuta.';
13. End;
14.  

[Thaddy]

14 is correct: 99999999999999 = 14 decimals = length of the decimal number, as is 14 for 10000000000000
What is your problem?

[BrunoK]

No math, no division.

Code: Pascal  [Select][+][-]

1. program Project1;
2.  
3.  
4.   function DecLength(i: int64): integer;
5.   const
6.     cMaxDecInt = 1000000000000000000;
7.     cMaxDigLen = 18;
8.   var
9.     limit: int64;
10.   begin
11.     Result := 1;
12.     if i < 0 then begin            // Negative ?
13.       Inc(Result);
14.       i := -i;
15.       if i < 0 then                // Low(Int64) ?
16.         Exit(Result + cMaxDigLen);
17.     end;
18.     if i >= cMaxDecInt then        // Max digits
19.       Exit(Result + cMaxDigLen);
20.     limit := 9;
21.     while i > limit do begin       // Tight loop with only * + operators
22.       Inc(Result);
23.       limit := limit * 10 + 9;
24.     end;
25.   end;
26.  
27. var
28.   lTestInt64: int64;
29. begin
30.   lTestInt64 := 0;
31.   Writeln(lTestInt64: 20, #9, DecLength(lTestInt64): 2);
32.   lTestInt64 := -lTestInt64;
33.   Writeln(lTestInt64: 20, #9, DecLength(lTestInt64): 2);
34.  
35.   lTestInt64 := 9;
36.   Writeln(lTestInt64: 20, #9, DecLength(lTestInt64): 2);
37.   lTestInt64 := -lTestInt64;
38.   Writeln(lTestInt64: 20, #9, DecLength(lTestInt64): 2);
39.  
40.   lTestInt64 := 500;
41.   Writeln(lTestInt64: 20, #9, DecLength(lTestInt64): 2);
42.   lTestInt64 := -lTestInt64;
43.   Writeln(lTestInt64: 20, #9, DecLength(lTestInt64): 2);
44.  
45.   lTestInt64 := 9999;
46.   Writeln(lTestInt64: 20, #9, DecLength(lTestInt64): 2);
47.   lTestInt64 := -lTestInt64;
48.   Writeln(lTestInt64: 20, #9, DecLength(lTestInt64): 2);
49.  
50.   lTestInt64 := 999999999999999999;
51.   Writeln(lTestInt64: 20, #9, DecLength(lTestInt64): 2);
52.   lTestInt64 := -lTestInt64;
53.   Writeln(lTestInt64: 20, #9, DecLength(lTestInt64): 2);
54.  
55.  
56.   lTestInt64 := 1000000000000000000;
57.   Writeln(lTestInt64: 20, #9, DecLength(lTestInt64): 2);
58.   lTestInt64 := -lTestInt64;
59.   Writeln(lTestInt64: 20, #9, DecLength(lTestInt64): 2);
60.  
61.   lTestInt64 := High(int64);
62.   Writeln(lTestInt64: 20, #9, DecLength(lTestInt64): 2);
63.   lTestInt64 := Low(int64);
64.   Writeln(lTestInt64: 20, #9, DecLength(lTestInt64): 2);
65.  
66.   ReadLn;
67. end.

Results :

Code: Pascal  [Select][+][-]

1.                    0     1
2.                    0     1
3.                    9     1
4.                   -9     2
5.                  500     3
6.                 -500     4
7.                 9999     4
8.                -9999     5
9.   999999999999999999    18
10.  -999999999999999999    19
11.  1000000000000000000    19
12. -1000000000000000000    20
13.  9223372036854775807    19
14. -9223372036854775808    20

[Thaddy]

@BrunoK

Time that...it is slow. We are trying to find the fastest/faster way.

[MathMan]

Does anybody know how to find magical numbers for 64 bit version of DecLength?

Hello LemonParty,

I wasn't at my prime last time - my only excuse is that it was 2:00 am local time 

Some general comments first:

* one can get rid of the check for '0' by extending the table by one entry and using the definition of BsrDWord
* if a signed integer is to be checked the best way is to use Abs(i) instead of if ... then ... else
* the extension to UInt64 / Int64 needs a different table format or two tables <= latter is slightly faster
* there was a lot more in the articles in Daniel Lemire's blog, and the sub-sequent discussions

* speed may depend on your specific use case - if you have normal distributed randoms the following is probably best, in other cases maybe not

Code: Pascal  [Select][+][-]

1. program DecCnt;
2.  
3. {$mode objfpc}{$H+}
4.  
5. uses
6.   SysUtils, Math;
7.  
8. function DecCntu32( u: UInt32 ):NativeInt;inline;
9.  
10. const
11.   CTable: array [0..32] of UInt64 =
12.   (
13.     4294967296,
14.     4294967296,  8589934582,  8589934582,  8589934582,
15.     12884901788, 12884901788, 12884901788, 17179868184,
16.     17179868184, 17179868184, 21474826480, 21474826480,
17.     21474826480, 21474826480, 25769703776, 25769703776,
18.     25769703776, 30063771072, 30063771072, 30063771072,
19.     34349738368, 34349738368, 34349738368, 34349738368,
20.     38554705664, 38554705664, 38554705664, 41949672960,
21.     41949672960, 41949672960, 42949672960, 42949672960
22.   );
23.  
24. begin
25.   Result := ( u+CTable[ UInt8( BsrDWord( u )+1 ) ] ) shr 32;
26. end;
27.  
28. function DecCnti32( i: UInt32 ):NativeInt;inline;
29.  
30. const
31.   CTable: array [0..32] of QWord =
32.   (
33.     4294967296,
34.     4294967296,  8589934582,  8589934582,  8589934582,
35.     12884901788, 12884901788, 12884901788, 17179868184,
36.     17179868184, 17179868184, 21474826480, 21474826480,
37.     21474826480, 21474826480, 25769703776, 25769703776,
38.     25769703776, 30063771072, 30063771072, 30063771072,
39.     34349738368, 34349738368, 34349738368, 34349738368,
40.     38554705664, 38554705664, 38554705664, 41949672960,
41.     41949672960, 41949672960, 42949672960, 42949672960
42.   );
43.  
44. begin
45.   Result := ( i+CTable[ UInt8( BsrDWord( Abs( i ) )+1 ) ] ) shr 32;
46. end;
47.  
48. // the following defines are just for code beautifying purposes
49. {$push}{$macro on}
50.  
51. {$define E0  := -1}
52. {$define E1  := -10}
53. {$define E2  := -100}
54. {$define E3  := -1000}
55. {$define E4  := -10000}
56. {$define E5  := -100000}
57. {$define E6  := -1000000}
58. {$define E7  := -10000000}
59. {$define E8  := -100000000}
60. {$define E9  := -1000000000}
61. {$define E10 := -10000000000}
62. {$define E11 := -100000000000}
63. {$define E12 := -1000000000000}
64. {$define E13 := -10000000000000}
65. {$define E14 := -100000000000000}
66. {$define E15 := -1000000000000000}
67. {$define E16 := -10000000000000000}
68. {$define E17 := -100000000000000000}
69. {$define E18 := -1000000000000000000}
70. {$define E19 :=  8446744073709551616}
71.  
72. function DecCntu64( u: UInt64 ):NativeInt;inline;
73.  
74. const
75.   CTable: array [0..64,0..1] of QWord =
76.   (
77.     (  1, UInt64( E0  ) ),
78.     (  1, UInt64( E1  ) ), (  1, UInt64( E1  ) ), (  1, UInt64( E1  ) ), (  1, UInt64( E1  ) ),
79.     (  2, UInt64( E2  ) ), (  2, UInt64( E2  ) ), (  2, UInt64( E2  ) ),
80.     (  3, UInt64( E3  ) ), (  3, UInt64( E3  ) ), (  3, UInt64( E3  ) ),
81.     (  4, UInt64( E4  ) ), (  4, UInt64( E4  ) ), (  4, UInt64( E4  ) ), (  4, UInt64( E4  ) ),
82.     (  5, UInt64( E5  ) ), (  5, UInt64( E5  ) ), (  5, UInt64( E5  ) ),
83.     (  6, UInt64( E6  ) ), (  6, UInt64( E6  ) ), (  6, UInt64( E6  ) ),
84.     (  7, UInt64( E7  ) ), (  7, UInt64( E7  ) ), (  7, UInt64( E7  ) ), (  7, UInt64( E7  ) ),
85.     (  8, UInt64( E8  ) ), (  8, UInt64( E8  ) ), (  8, UInt64( E8  ) ),
86.     (  9, UInt64( E9  ) ), (  9, UInt64( E9  ) ), (  9, UInt64( E9  ) ),
87.     ( 10, UInt64( E10 ) ), ( 10, UInt64( E10 ) ), ( 10, UInt64( E10 ) ), ( 10, UInt64( E10 ) ),
88.     ( 11, UInt64( E11 ) ), ( 11, UInt64( E11 ) ), ( 11, UInt64( E11 ) ),
89.     ( 12, UInt64( E12 ) ), ( 12, UInt64( E12 ) ), ( 12, UInt64( E12 ) ),
90.     ( 13, UInt64( E13 ) ), ( 13, UInt64( E13 ) ), ( 13, UInt64( E13 ) ), ( 13, UInt64( E13 ) ),
91.     ( 14, UInt64( E14 ) ), ( 14, UInt64( E14 ) ), ( 14, UInt64( E14 ) ),
92.     ( 15, UInt64( E15 ) ), ( 15, UInt64( E15 ) ), ( 15, UInt64( E15 ) ),
93.     ( 16, UInt64( E16 ) ), ( 16, UInt64( E16 ) ), ( 16, UInt64( E16 ) ), ( 16, UInt64( E16 ) ),
94.     ( 17, UInt64( E17 ) ), ( 17, UInt64( E17 ) ), ( 17, UInt64( E17 ) ),
95.     ( 18, UInt64( E18 ) ), ( 18, UInt64( E18 ) ), ( 18, UInt64( E18 ) ),
96.     ( 19, UInt64( E19 ) ), ( 19, UInt64( E19 ) ), ( 19, UInt64( E19 ) ), ( 19, UInt64( E19 ) )
97.   );
98.  
99. var
100.   Index: UInt8;
101.  
102. begin
103.   Index := UInt8( BsrQWord( u )+1 );
104.   Result := CTable[ Index,0 ] + NativeInt( ( CTable[ Index,1 ]+u )<u );
105. end;
106.  
107. function DecCntu64v2( u: UInt64 ):NativeInt;inline;
108.  
109. const
110.   CTable1: array [0..64] of UInt8 =
111.   (
112.      1,
113.      1,  1,  1,  1,  2,  2,  2,  3,  3,  3,  4,  4,  4,  4,  5,  5,  5,  6,  6,  6,
114.      7,  7,  7,  7,  8,  8,  8,  9,  9,  9, 10, 10, 10, 10, 11, 11, 11, 12, 12, 12,
115.     13, 13, 13, 13, 14, 14, 14, 15, 15, 15, 16, 16, 16, 16, 17, 17, 17, 18, 18, 18,
116.     19, 19, 19, 19
117.   );
118.  
119.   CTable2: array [0..64] of UInt64 =
120.   (
121.     UInt64( E0  ),
122.     UInt64( E1  ), UInt64( E1  ), UInt64( E1  ), UInt64( E1  ),
123.     UInt64( E2  ), UInt64( E2  ), UInt64( E2  ),
124.     UInt64( E3  ), UInt64( E3  ), UInt64( E3  ),
125.     UInt64( E4  ), UInt64( E4  ), UInt64( E4  ), UInt64( E4  ),
126.     UInt64( E5  ), UInt64( E5  ), UInt64( E5  ),
127.     UInt64( E6  ), UInt64( E6  ), UInt64( E6  ),
128.     UInt64( E7  ), UInt64( E7  ), UInt64( E7  ), UInt64( E7  ),
129.     UInt64( E8  ), UInt64( E8  ), UInt64( E8  ),
130.     UInt64( E9  ), UInt64( E9  ), UInt64( E9  ),
131.     UInt64( E10 ), UInt64( E10 ), UInt64( E10 ), UInt64( E10 ),
132.     UInt64( E11 ), UInt64( E11 ), UInt64( E11 ),
133.     UInt64( E12 ), UInt64( E12 ), UInt64( E12 ),
134.     UInt64( E13 ), UInt64( E13 ), UInt64( E13 ), UInt64( E13 ),
135.     UInt64( E14 ), UInt64( E14 ), UInt64( E14 ),
136.     UInt64( E15 ), UInt64( E15 ), UInt64( E15 ),
137.     UInt64( E16 ), UInt64( E16 ), UInt64( E16 ), UInt64( E16 ),
138.     UInt64( E17 ), UInt64( E17 ), UInt64( E17 ),
139.     UInt64( E18 ), UInt64( E18 ), UInt64( E18 ),
140.     UInt64( E19 ), UInt64( E19 ), UInt64( E19 ), UInt64( E19 )
141.   );
142.  
143. var
144.   Index: UInt8;
145.  
146. begin
147.   Index := UInt8( BsrQWord( u )+1 );
148.   Result := CTable1[ Index ] + NativeInt( ( CTable2[ Index ]+u )<u );
149. end;
150.  
151. function DecCnti64( i: Int64 ):NativeInt;inline;
152.  
153. const
154.   CTable: array [0..64,0..1] of QWord =
155.   (
156.     (  1, UInt64( E0  ) ),
157.     (  1, UInt64( E1  ) ), (  1, UInt64( E1  ) ), (  1, UInt64( E1  ) ), (  1, UInt64( E1  ) ),
158.     (  2, UInt64( E2  ) ), (  2, UInt64( E2  ) ), (  2, UInt64( E2  ) ),
159.     (  3, UInt64( E3  ) ), (  3, UInt64( E3  ) ), (  3, UInt64( E3  ) ),
160.     (  4, UInt64( E4  ) ), (  4, UInt64( E4  ) ), (  4, UInt64( E4  ) ), (  4, UInt64( E4  ) ),
161.     (  5, UInt64( E5  ) ), (  5, UInt64( E5  ) ), (  5, UInt64( E5  ) ),
162.     (  6, UInt64( E6  ) ), (  6, UInt64( E6  ) ), (  6, UInt64( E6  ) ),
163.     (  7, UInt64( E7  ) ), (  7, UInt64( E7  ) ), (  7, UInt64( E7  ) ), (  7, UInt64( E7  ) ),
164.     (  8, UInt64( E8  ) ), (  8, UInt64( E8  ) ), (  8, UInt64( E8  ) ),
165.     (  9, UInt64( E9  ) ), (  9, UInt64( E9  ) ), (  9, UInt64( E9  ) ),
166.     ( 10, UInt64( E10 ) ), ( 10, UInt64( E10 ) ), ( 10, UInt64( E10 ) ), ( 10, UInt64( E10 ) ),
167.     ( 11, UInt64( E11 ) ), ( 11, UInt64( E11 ) ), ( 11, UInt64( E11 ) ),
168.     ( 12, UInt64( E12 ) ), ( 12, UInt64( E12 ) ), ( 12, UInt64( E12 ) ),
169.     ( 13, UInt64( E13 ) ), ( 13, UInt64( E13 ) ), ( 13, UInt64( E13 ) ), ( 13, UInt64( E13 ) ),
170.     ( 14, UInt64( E14 ) ), ( 14, UInt64( E14 ) ), ( 14, UInt64( E14 ) ),
171.     ( 15, UInt64( E15 ) ), ( 15, UInt64( E15 ) ), ( 15, UInt64( E15 ) ),
172.     ( 16, UInt64( E16 ) ), ( 16, UInt64( E16 ) ), ( 16, UInt64( E16 ) ), ( 16, UInt64( E16 ) ),
173.     ( 17, UInt64( E17 ) ), ( 17, UInt64( E17 ) ), ( 17, UInt64( E17 ) ),
174.     ( 18, UInt64( E18 ) ), ( 18, UInt64( E18 ) ), ( 18, UInt64( E18 ) ),
175.     ( 19, UInt64( E19 ) ), ( 19, UInt64( E19 ) ), ( 19, UInt64( E19 ) ), ( 19, UInt64( E19 ) )
176.   );
177.  
178. var
179.   Index: UInt8;
180.   Absi: UInt64;
181.  
182. begin
183.   Absi := Abs( i );
184.   Index := UInt8( BsrQWord( Absi )+1 );
185.   Result := CTable[ Index,0 ] + NativeInt( ( CTable[ Index,1 ]+Absi )<Absi );
186. end;
187.  
188. {$undef E19}
189. {$undef E18}
190. {$undef E17}
191. {$undef E16}
192. {$undef E15}
193. {$undef E14}
194. {$undef E13}
195. {$undef E12}
196. {$undef E11}
197. {$undef E10}
198. {$undef E9}
199. {$undef E8}
200. {$undef E7}
201. {$undef E6}
202. {$undef E5}
203. {$undef E4}
204. {$undef E3}
205. {$undef E2}
206. {$undef E1}
207. {$undef E0}
208.  
209. {$pop}
210.  
211. const
212.   laps=100000000;
213.  
214.   TestValu32Tab: array[ 0..20 ] of UInt32 =
215.   (
216.     0, 1, 9, 10, 99, 100, 999, 1000, 9999, 10000, 99999, 100000, 999999,
217.     1000000, 9999999, 10000000, 99999999, 100000000, 999999999, 1000000000,
218.     4294967295
219.   );
220.  
221.   TestCntu32Tab: array[ 0..20 ] of UInt8 =
222.   (
223.     1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10
224.   );
225.  
226.   TestValu64Tab: array[ 0..40 ] of UInt64 =
227.   (
228.     0, 1, 9, 10, 99, 100, 999, 1000, 9999, 10000, 99999, 100000, 999999,
229.     1000000, 9999999, 10000000, 99999999, 100000000, 999999999, 1000000000,
230.     9999999999, 10000000000, 99999999999, 100000000000, 999999999999,
231.     1000000000000, 9999999999999, 10000000000000, 99999999999999, 100000000000000,
232.     999999999999999, 1000000000000000, 9999999999999999, 10000000000000000,
233.     99999999999999999, 100000000000000000, 999999999999999999, 1000000000000000000,
234.     9999999999999999999, 10000000000000000000, 18446744073709551615
235.   );
236.  
237.   TestCntu64Tab: array[ 0..40 ] of UInt8 =
238.   (
239.     1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11,
240.     12, 12, 13, 13, 14, 14, 15, 15, 16, 16, 17, 17, 18, 18, 19, 19, 20, 20
241.   );
242.  
243. var
244.   s: QWord;
245.   x, i: Integer;
246.   a: array of DWord = nil;
247.  
248. begin
249.   SetLength(a, laps);
250.   for i := 0 to High(a) do
251.     a[i] := Random(MaxInt);
252.  
253.   x:=0;
254.   s:=GetTickCount64;
255.   for i := 0 to High(a) do
256.     Inc( x, DecCntu32( a[ i ] ) );
257.   WriteLn( 'DecCntu32: ', GetTickCount64-s );
258.  
259.   x:=0;
260.   s:=GetTickCount64;
261.   for i := 0 to High(a) do
262.     Inc( x, DecCnti32( a[ i ] ) );
263.   WriteLn( 'DecCnti32: ', GetTickCount64-s );
264.  
265.   x:=0;
266.   s:=GetTickCount64;
267.   for i := 0 to High(a) do
268.     Inc( x, DecCntu64( a[ i ] ) );
269.   WriteLn( 'DecCntu64: ', GetTickCount64-s );
270.  
271.   x:=0;
272.   s:=GetTickCount64;
273.   for i := 0 to High(a) do
274.     Inc( x, DecCntu64v2( a[ i ] ) );
275.   WriteLn( 'DecCntu64v2: ', GetTickCount64-s );
276.  
277.   x:=0;
278.   s:=GetTickCount64;
279.   for i := 0 to High(a) do
280.     Inc( x, DecCnti64( a[ i ] ) );
281.   WriteLn( 'DecCnti64: ', GetTickCount64-s );
282.  
283.   Write( LineEnding, 'Test DecCntu32: ' );
284.   for i := Low( TestValu32Tab ) to High( TestValu32Tab ) do begin
285.     if( DecCntu32( TestValu32Tab[ i ] )=TestCntu32Tab[ i ] ) then begin
286.       Write( '*' );
287.     end else begin
288.       Write( ' failed: ', TestValu32Tab[ i ] );
289.       Exit;
290.     end;
291.   end;
292.  
293.   Write( LineEnding, 'Test DecCntu64: ' );
294.   for i := Low( TestValu64Tab ) to High( TestValu64Tab ) do begin
295.     if( DecCntu64( TestValu64Tab[ i ] )=TestCntu64Tab[ i ] ) then begin
296.       Write( '*' );
297.     end else begin
298.       Write( ' failed: ', TestValu64Tab[ i ] );
299.       Exit;
300.     end;
301.   end;
302. end.
303.  

[BrunoK]

@BrunoK

Time that...it is slow. We are trying to find the fastest/faster way.

Yes, you are right !

I suppose it is difficult to match avk's stuff with shift and direct table.

Anyway, none of the other algos will handle negative numbers.

[Josh]

how about some bit shifting and guessing.
overloads for int64,int32,qword,....byte.

I have not fully tested, or checked speed,but shouldn't be too bad?

Code: Pascal  [Select][+][-]

1. unit FastDigits;
2. {$mode objfpc}{$H+}
3.  
4. interface
5.  
6. function DecimalLength(x:Int64):LongInt;overload;
7. function DecimalLength(x:QWord):LongInt;overload;
8. function DecimalLength(x:Int32):LongInt;overload;
9. function DecimalLength(x:Cardinal):LongInt;overload;
10. function DecimalLength(x:Word):LongInt;overload;
11. function DecimalLength(x:SmallInt):LongInt;overload;
12. function DecimalLength(x:ShortInt):LongInt;overload;
13. function DecimalLength(x:Byte):LongInt;overload;
14.  
15. implementation
16.  
17. const
18.   POW10_64: array[0..19] of QWord=(1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,10000000000,100000000000,1000000000000,10000000000000,100000000000000,1000000000000000,10000000000000000,100000000000000000,1000000000000000000,10000000000000000000);
19.   POW10_32: array[0..10] of LongWord=(1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,4294967295);
20.  
21. function BitLength64(n:QWord):LongInt;inline;
22. var r:LongInt;
23. begin
24.   r:=0;
25.   if (n shr 32)<>0 then r:=r+32;
26.   n:=n shr r;
27.   if (n shr 16)<>0 then r:=r+16;
28.   n:=n shr (r and 16);
29.   if (n shr 8)<>0 then r:=r+8;
30.   n:=n shr (r and 8);
31.   if (n shr 4)<>0 then r:=r+4;
32.   n:=n shr (r and 4);
33.   if (n shr 2)<>0 then r:=r+2;
34.   n:=n shr (r and 2);
35.   if (n shr 1)<>0 then r:=r+1;
36.   Result:=r+1;
37. end;
38.  
39. function BitLength32(n:LongWord):LongInt;inline;
40. var r:LongInt;
41. begin
42.   r:=0;
43.   if (n shr 16)<>0 then r:=r+16;
44.   n:=n shr r;
45.   if (n shr 8)<>0 then r:=r+8;
46.   n:=n shr (r and 8);
47.   if (n shr 4)<>0 then r:=r+4;
48.   n:=n shr (r and 4);
49.   if (n shr 2)<>0 then r:=r+2;
50.   n:=n shr (r and 2);
51.   if (n shr 1)<>0 then r:=r+1;
52.   Result:=r+1;
53. end;
54.  
55. function DecimalLength64(n:QWord):LongInt;inline;
56. var bits,guess:LongInt;
57. begin
58.   if n<10 then Exit(1);
59.   bits:=BitLength64(n);
60.   guess:=(bits*1233) shr 12;
61.   if n>=POW10_64[guess] then Inc(guess);
62.   Result:=guess;
63. end;
64.  
65. function DecimalLength32(n:LongWord):LongInt;inline;
66. var bits,guess:LongInt;
67. begin
68.   if n<10 then Exit(1);
69.   bits:=BitLength32(n);
70.   guess:=(bits*1233) shr 12;
71.   if n>=POW10_32[guess] then Inc(guess);
72.   Result:=guess;
73. end;
74.  
75. function DecimalLength(x:Int64):LongInt;overload;
76. begin
77.   if x<0 then Result:=DecimalLength64(QWord(-x))   // like abs
78.   else
79.     Result:=DecimalLength64(QWord(x));
80. end;
81.  
82. function DecimalLength(x:QWord):LongInt;overload;
83. begin
84.   Result:=DecimalLength64(x);
85. end;
86.  
87. function DecimalLength(x:Int32):LongInt;overload;
88. begin
89.   if x<0 then Result:=DecimalLength32(LongWord(-x))  // like abs
90.   else
91.     Result:=DecimalLength32(LongWord(x));
92. end;
93.  
94. function DecimalLength(x:Cardinal):LongInt;overload;
95. begin
96.   Result:=DecimalLength32(x);
97. end;
98.  
99. function DecimalLength(x:Word):LongInt;overload;
100. begin
101.   if x<10 then Exit(1)
102.   else
103.     if x<100 then Exit(2)
104.     else
105.       if x<1000 then Exit(3)
106.       else
107.         Exit(4);
108. end;
109.  
110. function DecimalLength(x:SmallInt):LongInt;overload;
111. begin
112.   if x<0 then Exit(1+DecimalLength(-x));  // like abs
113.   if x<10 then Exit(1)
114.   else
115.     Exit(2);
116. end;
117.  
118. function DecimalLength(x:ShortInt):LongInt;overload;
119. begin
120.   if x<0 then Exit(1+DecimalLength(-x));  // like abs
121.   if x<10 then Exit(1)
122.   else
123.     Exit(2);
124. end;
125.  
126. function DecimalLength(x:Byte):LongInt;overload;
127. begin
128.   if x<10 then Exit(1)
129.   else if x<100 then Exit(2)
130.   else
131.     Exit(3);
132. end;
133.  
134. end.
135.