Lazarus

Free Pascal => Beginners => Topic started by: chickpea on January 30, 2018, 12:02:33 pm

Title: simple problem: count digits of number
Post by: chickpea on January 30, 2018, 12:02:33 pm
Hi there,

Here's my approach to counting the digits of a number in pascal.
It does work, but as soon as I enter a number with more than 5 digits the program returns a 5.
I don't get why. If anyone could give me a hint that'd be great.
Comments and program names in German, but I suppose you get the idea.

Thanks in advance!




program ZifferAnzahl (input, output);


  type
  tNatZahl = 0..maxint;
 
  var
  inZahl : tNatZahl;
 
function countZiff (inZahl : tNatZahl) : tNatZahl;

{ gibt Anzahl der Ziffern von inZahl zurück }

  var
  i,
  j : tNatZahl;
 
begin

  { initialisierung }
 
  i := inZahl;
  j := 0;
 
  { inZahl so oft durch 10 Teilen, bis 0 erreicht wird }
 
  while i > 0 do
    begin
    i := i div 10;
    j := j + 1
    end;
 
  countZiff := j
end; { countZiff }


begin
  writeln ('Bitte Zahl eingeben');
  readln (inZahl);
  writeln(countZiff(inZahl))
end. { ZifferAnzahl }
   
Title: Re: simple problem: count digits of number
Post by: rvk on January 30, 2018, 12:19:07 pm
You are probably in TP mode. {$mode TP}
There maxint is a 2 byte integer.
Which is maximum 32767 (see, 5 digits)

Add {$mode objfpc} just below program and your Integer will be 4 bytes.

B.T.W. you can check this by adding the lines
Code: Pascal  [Select][+][-]
  1. writeln(sizeof(inZahl));
  2. writeln(maxint);

Of course you can also do this instead of changing mode:
Code: Pascal  [Select][+][-]
  1. type
  2.   tNatZahl = 0..99999999;
Title: Re: simple problem: count digits of number
Post by: chickpea on January 30, 2018, 04:05:34 pm
Great, that was the error indeed. Thanks for explaining.

Working correctly when change to

tNatZahl = 0..999999999;

Cheers
Title: Re: simple problem: count digits of number
Post by: Bart on January 30, 2018, 09:08:30 pm
Perhaps: tNatZahl = QWord;

Another dummy approach  O:-)
Code: Pascal  [Select][+][-]
  1. uses sysutils;
  2.  
  3. function countZiff (inZahl : tNatZahl) : tNatZahl;
  4. begin
  5.   Result := Length(IntToStr(inZahl));
  6. end;
  7.  

or
Code: Pascal  [Select][+][-]
  1. uses Math;
  2.  
  3. function countZiff (inZahl : tNatZahl) : tNatZahl;
  4. begin
  5.   Result := Floor(Log10(inZahl));
  6. end;
  7.  

Bart
Title: Re: simple problem: count digits of number
Post by: furious programming on February 05, 2018, 05:43:04 am
@chickpea: you don't need a custom function, just use some helpers from SysUtils unit:

Code: Pascal  [Select][+][-]
  1. Count := MyIntVar.ToString.Length;

It's readable enough.
Title: Re: simple problem: count digits of number
Post by: Bart on February 05, 2018, 01:45:10 pm
Quote from: furious programming on February 05, 2018, 05:43:04 am
Code: Pascal  [Select][+][-]
  1. Count := MyIntVar.ToString.Length;

That's basically the same as I wrote above (Length(IntToStr(InZahl))), proabbly a bit less efficient (unless all this code for the helper is inlined), albeit more fancy.
The Log10 approach might actually be faster?

Bart
Title: Re: simple problem: count digits of number
Post by: isidroco on February 28, 2018, 07:43:43 pm
Floating point Log will always be slower, it involves series calculation even when done in mathcoprocessor will be slow, and sending/getting results from coprocessor will probably be slower than integer operations unless number of digits is very big (>50) in which log10 might be faster.

PS: In my old days when clocking stuff in 80286 cpus, I found out in TP5.0 that x*0.33333333 was a lot faster than x/3. (x: real) (And a lot was about 3 times faster). So it's better to multiply by a constant than divide by it's inverse.
Title: Re: simple problem: count digits of number
Post by: A.S. on February 28, 2018, 08:25:10 pm
Function "countZiff" is incorrect: it returns 0 if inZahl=0, but "0" contains the single digit zero, so countZiff(0) must return 1.
Title: Re: simple problem: count digits of number
Post by: Bart on February 28, 2018, 10:30:37 pm
Quote from: isidroco on February 28, 2018, 07:43:43 pm
Floating point Log will always be slower, it involves series calculation even when done in mathcoprocessor will be slow, and sending/getting results from coprocessor will probably be slower than integer operations unless number of digits is very big (>50) in which log10 might be faster.

The IntToStr part also costs time.

Code: Pascal  [Select][+][-]
  1. program Project1;
  2. {$mode objfpc}{$h+}
  3.  
  4. uses SysUtils, Math;
  5.  
  6. function cntIntToStr(Z: Integer): Integer;
  7. begin
  8.   Result := Length(IntToStr(Z));
  9. end;
  10.  
  11. function cntTypeHelper(Z: Integer): Integer;
  12. begin
  13.   Result := Z.ToString.Length;
  14. end;
  15.  
  16. function cntLog10(Z: Integer): Integer;
  17. begin
  18.   if Z = 0 then
  19.     Result := 1
  20.   else
  21.     Result := 1+Floor(Log10(Z));
  22. end;
  23.  
  24. const
  25.   cycle = 1000000;
  26. var
  27.   i: Integer;
  28.   T0, T1: QWord;
  29.   Sample, Res: Integer;
  30. begin
  31.   Sample := MaxInt; //2147483647
  32.   T0 := GetTickCount64;
  33.   for i := 1 to cycle do Res := cntIntToStr(Sample);
  34.   T1 := GetTickCount64;
  35.   writeln(format('cntIntToStr  : %.4d ticks (Res = %d)',[T1-T0,Res]));
  36.  
  37.   T0 := GetTickCount64;
  38.   for i := 1 to cycle do Res := cntTypeHelper(Sample);
  39.   T1 := GetTickCount64;
  40.   writeln(format('cntTypeHelper: %.4d ticks (Res = %d)',[T1-T0,Res]));
  41.  
  42.   T0 := GetTickCount64;
  43.   for i := 1 to cycle do Res := cntLog10(Sample);
  44.   T1 := GetTickCount64;
  45.   writeln(format('cntLog10     : %.4d ticks (Res = %d)',[T1-T0,Res]));
  46. end.

Outputs:
Code: [Select]
cntIntToStr  : 1328 ticks (Res = 10)
cntTypeHelper: 1359 ticks (Res = 10)
cntLog10     : 0047 ticks (Res = 10)

Notice that using typehelpers this is just a little bit slower than using classic Length(IntToStr()), but the Log10 is way faster.

Bart
Title: Re: simple problem: count digits of number
Post by: isidroco on March 01, 2018, 02:14:18 am
Quote from: Bart on February 28, 2018, 10:30:37 pm
Notice that using typehelpers this is just a little bit slower than using classic Length(IntToStr()), but the Log10 is way faster.
Bart

Thanks for the eyeopener, evidently TP5 real type without using coprocessor were a lot slower than today's implementation which uses it. And IntToStr involves a lot of DIV instructions. (In my days 80387 math coprocessor costed 800u$ so most machines didn't have it...). Actually I had to program log(X+1) and it's inverse using taylor series, and it was quite faster than using internal LOG(x+1) for values of x close to 0. Math coprocessor have internal instructions for that: FYL2XP1 / F2XM1
Title: Re: simple problem: count digits of number
Post by: engkin on March 01, 2018, 05:12:19 am
On my old laptop this seems faster:
Code: Pascal  [Select][+][-]
  1.   function cntTbl(Z: integer): integer;
  2.   begin
  3.     if Z <= 9 then
  4.       Result := 1
  5.     else if Z <= 99 then
  6.       Result := 2
  7.     else if Z <= 999 then
  8.       Result := 3
  9.     else if Z <= 9999 then
  10.       Result := 4
  11.     else if Z <= 99999 then
  12.       Result := 5
  13.     else if Z <= 999999 then
  14.       Result := 6
  15.     else if Z <= 9999999 then
  16.       Result := 7
  17.     else if Z <= 99999999 then
  18.       Result := 8
  19.     else if Z <= 999999999 then
  20.       Result := 9
  21.     else if Z <= 9999999999 then
  22.       Result := 10
  23.     else if Z <= 99999999999 then
  24.       Result := 11
  25.     else if Z <= 999999999999 then
  26.       Result := 12
  27.     else if Z <= 9999999999999 then
  28.       Result := 13
  29.     else if Z <= 99999999999999 then
  30.       Result := 14
  31.     else if Z <= 999999999999999 then
  32.       Result := 15
  33.     else if Z <= 9999999999999999 then
  34.       Result := 16
  35.     else if Z <= 99999999999999999 then
  36.       Result := 17
  37.     else if Z <= 999999999999999999 then
  38.       Result := 18
  39.     else if Z <= 9999999999999999999 then
  40.       Result := 19;
  41.   end;

Did not try a case statement.
Title: Re: simple problem: count digits of number
Post by: isidroco on March 01, 2018, 02:46:29 pm
Based on last post this would converge faster:
Code: Pascal  [Select][+][-]
  1. function cntTbl(Z: int64): int64;
  2. begin
  3.   if Z<0 then Z:=abs(Z);
  4.   if Z < 10^8 then
  5.     if Z < 10^4 then
  6.       if Z < 10^2 then
  7.         if Z < 10^1 then result:=1 else result:=2
  8.       else
  9.         if Z < 10^3 then result:=3 else result:=4
  10.     else
  11.       if Z < 10^6 then
  12.         if Z < 10^5 then result:=5 else result:=6
  13.       else
  14.         if Z < 10^7 then result:=7 else result:=8
  15.   else
  16.         Return( 8 + cntTbl( z div 10^8) );
  17. end;
  18.  

Which would recurse call if more than 8 digits, and will return digit count of negative numbers. Same code could be used for real values (although in that case, in last statement I would switch to LOG10 instead of recurse calling to quickly get results for high exponents ).
Title: Re: simple problem: count digits of number
Post by: howardpc on March 01, 2018, 04:59:41 pm
Quote from: engkin on March 01, 2018, 05:12:19 am
Did not try a case statement.

In my tests case is marginally the fastest so far.

Code: Pascal  [Select][+][-]
  1. program CompareCountDigits;
  2. {$mode objfpc}{$h+}
  3.  
  4. uses SysUtils, Math;
  5.  
  6. const
  7.   Number: int64 = MaxInt; //2147483647
  8.   Iterations: DWord = 1000000;
  9.  
  10. type
  11.   TCountFunc = function(anInt: Int64): Int64;
  12.  
  13.   TFuncEnum = (cfIntToStr, cfTbl, cfTbl64, cfCaseTbl, cfTypeHelper, cfLog10);
  14.  
  15.   TFuncRec = record
  16.     func: TCountFunc;
  17.     name: String;
  18.   end;
  19.  
  20.   TFuncRecArray = array[TFuncEnum] of TFuncRec;
  21.  
  22. function GetFName(aFuncEnum: TFuncEnum): String;
  23. begin
  24.   WriteStr(Result, aFuncEnum);
  25.   Delete(Result, 1, 2);
  26. end;
  27.  
  28. function DoFunction(func: TCountFunc; out ticks: QWord): Int64;
  29. var
  30.   i: Integer;
  31.   t0: QWord;
  32. begin
  33.   t0 := GetTickCount64;
  34.   for i := 1 to iterations do
  35.     Result := func(Number);
  36.   ticks := GetTickCount64;
  37.   Dec(ticks, t0);
  38. end;
  39.  
  40. function cntIntToStr(Z: Int64): Int64;
  41. begin
  42.   Result := Length(IntToStr(Z));
  43. end;
  44.  
  45. function cntTbl(Z: Int64): Int64;
  46.   begin
  47.     if Z <= 9 then
  48.       Result := 1
  49.     else if Z <= 99 then
  50.       Result := 2
  51.     else if Z <= 999 then
  52.       Result := 3
  53.     else if Z <= 9999 then
  54.       Result := 4
  55.     else if Z <= 99999 then
  56.       Result := 5
  57.     else if Z <= 999999 then
  58.       Result := 6
  59.     else if Z <= 9999999 then
  60.       Result := 7
  61.     else if Z <= 99999999 then
  62.       Result := 8
  63.     else if Z <= 999999999 then
  64.       Result := 9
  65.     else if Z <= 9999999999 then
  66.       Result := 10
  67.     else if Z <= 99999999999 then
  68.       Result := 11
  69.     else if Z <= 999999999999 then
  70.       Result := 12
  71.     else if Z <= 9999999999999 then
  72.       Result := 13
  73.     else if Z <= 99999999999999 then
  74.       Result := 14
  75.     else if Z <= 999999999999999 then
  76.       Result := 15
  77.     else if Z <= 9999999999999999 then
  78.       Result := 16
  79.     else if Z <= 99999999999999999 then
  80.       Result := 17
  81.     else if Z <= 999999999999999999 then
  82.       Result := 18
  83.     else if Z <= 9223372036854775807 then
  84.       Result := 19;
  85.   end;
  86.  
  87. function cntCaseTbl(Z: Int64): Int64;
  88.   begin
  89.     case Z of
  90.       0..9: Exit(1);
  91.       10..99 : Exit(2);
  92.       100..999: Exit(3);
  93.       1000..9999: Exit(4);
  94.       10000..99999: Exit(5);
  95.       100000..999999: Exit(6);
  96.       1000000..9999999: Exit(7);
  97.       10000000..99999999: Exit(;
  98.       100000000..999999999: Exit(9);
  99.       1000000000..9999999999: Exit(10);
  100.       10000000000..99999999999: Exit(11);
  101.       100000000000..999999999999: Exit(12);
  102.       1000000000000..9999999999999: Exit(13);
  103.       10000000000000..99999999999999: Exit(14);
  104.       100000000000000..999999999999999: Exit(15);
  105.       1000000000000000..9999999999999999: Exit(16);
  106.       10000000000000000..99999999999999999: Exit(17);
  107.       100000000000000000..999999999999999999: Exit(18);
  108.       1000000000000000000..9223372036854775807: Exit(19);
  109.     end;
  110.   end;
  111.  
  112. function cntTbl64(Z: int64): int64;
  113. begin
  114.   if Z<0 then Z:=abs(Z);
  115.   if Z < 100000000 then
  116.     if Z < 10000 then
  117.       if Z < 100 then
  118.         if Z < 10 then result:=1 else result:=2
  119.       else
  120.         if Z < 1000 then result:=3 else result:=4
  121.     else
  122.       if Z < 1000000 then
  123.         if Z < 1000000 then result:=5 else result:=6
  124.       else
  125.         if Z < 10000000 then result:=7 else result:=8
  126.   else Exit(8 + cntTbl( z div 100000000) );
  127. end;
  128.  
  129. function cntTypeHelper(Z: Int64): Int64;
  130. begin
  131.   Result := Z.ToString.Length;
  132. end;
  133.  
  134. function cntLog10(Z: Int64): Int64;
  135. begin
  136.   if Z = 0 then
  137.     Result := 1
  138.   else
  139.     Result := 1+Floor(Log10(Z));
  140. end;
  141.  
  142. var
  143.   fra: TFuncRecArray;
  144.   fe: TFuncEnum;
  145.   fr: TFuncRec;
  146.   res: Int64;
  147.   ticks: QWord;
  148.  
  149. begin
  150.   fra:=default(TFuncRecArray);
  151.   for fe in TFuncEnum do
  152.     fra[fe].name := GetFName(fe);
  153.  
  154.   fra[cfIntToStr].func :=  @cntIntToStr;
  155.   fra[cfTbl].func :=       @cntTbl;
  156.   fra[cfTbl64].func :=     @cntTbl64;
  157.   fra[cfCaseTbl].func :=   @cntCaseTbl;
  158.   fra[cfTypeHelper].func:= @cntTypeHelper;
  159.   fra[cfLog10].func :=     @cntLog10;
  160.  
  161.   for fr in fra do begin
  162.     res := DoFunction(fr.func, ticks);
  163.     WriteLn(fr.name, ticks:4, ' ticks (result = ', res, ')');
  164.   end;
  165.  
  166.   ReadLn;
  167. end.

Typical output:

IntToStr 523 ticks (result = 10)
Tbl  12 ticks (result = 10)
Tbl64  14 ticks (result = 10)
CaseTbl   9 ticks (result = 10)
TypeHelper 528 ticks (result = 10)
Log10  53 ticks (result = 10)
Title: Re: simple problem: count digits of number
Post by: isidroco on March 01, 2018, 05:42:13 pm
My version is faster if digits are less than 8 (made a 16 digit version but was unnecessary long), if typical cases are higher than 8 digits probably is worthwhile. Also negative numbers should be contempleted in all versions, an ABS() statement must be added to all other versions.
Try comparing with 7 digits numbers and post results, thanks!
Title: Re: simple problem: count digits of number
Post by: Thaddy on March 01, 2018, 05:48:23 pm
Code: Bash  [Select][+][-]
  1. IntToStr2334 ticks (result = 10)
  2. Tbl 149 ticks (result = 10)
  3. Tbl64 237 ticks (result = 10)
  4. CaseTbl  96 ticks (result = 10)
  5. TypeHelper2398 ticks (result = 10)
  6. Log10 464 ticks (result = 10)
On a Raspberry pi 3.
Title: Re: simple problem: count digits of number
Post by: Bart on March 01, 2018, 07:22:06 pm
Nice additions!!
I thought of that (if then else, and case), but it was a bit too late for me.
Once we have a 128-bit or even 256-bit or 1024-bit integer type, this will become a bit hard to maintain maybe, whilst the ToString and Log10 versions should keep working simply by adjusting the parameter type.

B.t.w.: returning an Int64 for the count is a bit optimistic (a number with 2^63-1 digits?) maybe?
How many bits would that number be?

Bart
Title: Re: simple problem: count digits of number
Post by: ASerge on March 01, 2018, 08:39:44 pm
Tried to measure on random input data (range Int64) function CntCaseTbl:
Code: Pascal  [Select][+][-]
  1. function CntCaseTbl(Z: Int64): Integer;
  2. begin
  3.   case Abs(Z) of
  4.     0..9: Result := 1;
  5.     10..99 : Result := 2;
  6.     100..999: Result := 3;
  7.     1000..9999: Result := 4;
  8.     10000..99999: Result := 5;
  9.     100000..999999: Result := 6;
  10.     1000000..9999999: Result := 7;
  11.     10000000..99999999: Result := 8;
  12.     100000000..999999999: Result := 9;
  13.     1000000000..9999999999: Result := 10;
  14.     10000000000..99999999999: Result := 11;
  15.     100000000000..999999999999: Result := 12;
  16.     1000000000000..9999999999999: Result := 13;
  17.     10000000000000..99999999999999: Result := 14;
  18.     100000000000000..999999999999999: Result := 15;
  19.     1000000000000000..9999999999999999: Result := 16;
  20.     10000000000000000..99999999999999999: Result := 17;
  21.     100000000000000000..999999999999999999: Result := 18;
  22.   else
  23.     Result := 19;
  24.   end;
  25.   if Z < 0 then
  26.     Inc(Result);
  27. end;

and modified CntTbl:
Code: Pascal  [Select][+][-]
  1. function CntTbl(Z: Int64): Integer;
  2. var
  3.   ZAbs: Int64;
  4. begin
  5.   ZAbs := Abs(Z);
  6.   if ZAbs >= 1000000000 then // ZAbs >= 1e9
  7.     if ZAbs >= 100000000000000 then // ZAbs >= 1e14
  8.       if ZAbs >= 10000000000000000 then // ZAbs >= 1e16
  9.         if ZAbs >= 1000000000000000000 then // ZAbs >= 1e18
  10.           Result := 19
  11.         else // 1e16 <= ZAbs < 1e18
  12.           if ZAbs >= 100000000000000000 then // ZAbs >= 1e17
  13.             Result := 18
  14.           else // 1e16 <= ZAbs < 1e17
  15.             Result := 17
  16.       else // 1e14 <= ZAbs < 1e16
  17.         if ZAbs >= 1000000000000000 then // ZAbs >= 1e15
  18.           Result := 16
  19.         else // 1e14 <= ZAbs < 1e15
  20.           Result := 15
  21.     else // 1e9 <= ZAbs < 1e14
  22.       if ZAbs >= 100000000000 then // ZAbs >= 1e11
  23.         if ZAbs >= 1000000000000 then // ZAbs >= 1e12
  24.           if ZAbs >= 10000000000000 then // ZAbs >= 1e13
  25.             Result := 14
  26.           else // 1e12 <= ZAbs < 1e13
  27.             Result := 13
  28.         else // 1e11 <= ZAbs < 1e12
  29.           Result := 12
  30.       else // 1e9 <= ZAbs < 1e11
  31.         if ZAbs >= 10000000000 then // ZAbs >= 1e10
  32.           Result := 11
  33.         else // 1e9 <= ZAbs < 1e10
  34.           Result := 10
  35.   else // 0 <= ZAbs < 1e9
  36.     if ZAbs >= 10000 then // ZAbs >= 1e4
  37.       if ZAbs >= 1000000 then // ZAbs >= 1e6
  38.         if ZAbs >= 10000000 then // ZAbs >= 1e7
  39.           if ZAbs >= 100000000 then // ZAbs >= 1e8
  40.             Result := 9
  41.           else // 1e7 <= ZAbs < 1e8
  42.             Result := 8
  43.         else // 1e6 <= ZAbs < 1e7
  44.           Result := 7
  45.       else // 1e4 <= ZAbs < 1e6
  46.         if ZAbs >= 100000 then // ZAbs >= 1e5
  47.           Result := 6
  48.         else // 1e4 <= ZAbs < 1e5
  49.           Result := 5
  50.     else // 0 <= ZAbs < 1e4
  51.       if ZAbs >= 100 then // ZAbs >= 1e2
  52.         if ZAbs >= 1000 then // ZAbs >= 1e3
  53.           Result := 4
  54.         else // 1e2 <= ZAbs < 1e3
  55.           Result := 3
  56.       else // 0 <= ZAbs < 1e2
  57.         if ZAbs >= 10 then // ZAbs >= 1e1
  58.           Result := 2
  59.         else // 0 <= ZAbs < 1e1
  60.           Result := 1;
  61.   if Z < 0 then
  62.     Inc(Result);
  63. end;

The results are fifty-fifty.
The smaller number of comparisons in CntTbl is compensated by a large number of jumps.
Looking at the CntTbl source code  %) I prefer CntCaseTbl.
Title: Re: simple problem: count digits of number
Post by: engkin on March 01, 2018, 11:42:12 pm
@ASerge, I heard you did not like the source code of CntTbl. Wait until you see this one:
Code: Pascal  [Select][+][-]
  1. function cntBitly(Z: integer): integer;
  2. const
  3.   digits:array[0..31] of integer =(1{*0-0},1{1-3},1{2-7},
  4.                                    1{*3-15},2{4-31},2{5-63},
  5.                                    2{*6-127},3{7-255},3{8-511},
  6.                                    3{*9-1023},4{10-2047},4{11-4095},4{12-8191},
  7.                                    4{*13-16383},5{14-32767},5{15-65535},
  8.                                    5{*16-131071},6{17-262143},6{18-524287},
  9.                                    6{*19-1048575},7{20-2097151},7{21-4194303},7{22-8388607},
  10.                                    7{*23-16777215},8{24-33554433},8{25-67108863},
  11.                                    8{*26-134217727},9{27-268435455},9{28-536870911},
  12.                                    9{*29-1073741823},10{30-2147483647},10{31-4294967295});
  13.  
  14.   limits:array[0..31] of integer =(99{0-1},99{1-3},99{2-7},
  15.                                    10{3-15},99{4-31},99{5-63},
  16.                                    100{6-127},999{7-255},999{8-511},
  17.                                    1000{9-1023},9999{10-2047},9999{11-4095},9999{12-8191},
  18.                                    10000{13-16383},99999{14-32767},99999{15-65535},
  19.                                    100000{16-131071},999999{17-262143},999999{18-524287},
  20.                                    1000000{19-1048575},9999999{20-2097151},9999999{21-4194303},9999999{22-8388607},
  21.                                    10000000{23-16777215},99999999{24-33554433},99999999{25-67108863},
  22.                                    100000000{26-134217727},999999999{27-268435455},999999999{28-536870911},
  23.                                    1000000000{29-1073741823},9999999999{30-2147483647},9999999999{31-4294967295});
  24. var
  25.   vbsr: Cardinal;
  26. begin
  27.   vbsr := BsrDWord(Z);
  28.   Result := digits[vbsr];
  29.   if z>=limits[vbsr] then
  30.     inc(Result);
  31. end;

There is still space for enhancement.
Title: Re: simple problem: count digits of number
Post by: ASerge on March 02, 2018, 01:53:48 am
Quote from: engkin on March 01, 2018, 11:42:12 pm
@ASerge, I heard you did not like the source code of CntTbl. Wait until you see this one:
What about Int64 and measurements?
Title: Re: simple problem: count digits of number
Post by: engkin on March 02, 2018, 02:26:03 am
Quote from: ASerge on March 02, 2018, 01:53:48 am
Quote from: engkin on March 01, 2018, 11:42:12 pm
@ASerge, I heard you did not like the source code of CntTbl. Wait until you see this one:
What about Int64 and measurements?

Since the constants are code generated (had to use GMP):
Code: Pascal  [Select][+][-]
  1. function cntBitly64(Z: Int64): Integer;
  2. const
  3.   digits:array[0..62] of integer =(
  4.   1{0-1},1{1-3},1{2-7},
  5.   1{*3-15},2{4-31},2{5-63},
  6.   2{*6-127},3{7-255},3{8-511},
  7.   3{*9-1023},4{10-2047},4{11-4095},4{12-8191},
  8.   4{*13-16383},5{14-32767},5{15-65535},
  9.   5{*16-131071},6{17-262143},6{18-524287},
  10.   6{*19-1048575},7{20-2097151},7{21-4194303},7{22-8388607},
  11.   7{*23-16777215},8{24-33554431},8{25-67108863},
  12.   8{*26-134217727},9{27-268435455},9{28-536870911},
  13.   9{*29-1073741823},10{30-2147483647},10{31-4294967295},10{32-8589934591},
  14.   10{*33-17179869183},11{34-34359738367},11{35-68719476735},
  15.   11{*36-137438953471},12{37-274877906943},12{38-549755813887},
  16.   12{*39-1099511627775},13{40-2199023255551},13{41-4398046511103},13{42-8796093022207},
  17.   13{*43-17592186044415},14{44-35184372088831},14{45-70368744177663},
  18.   14{*46-140737488355327},15{47-281474976710655},15{48-562949953421311},
  19.   15{*49-1125899906842623},16{50-2251799813685247},16{51-4503599627370495},16{52-9007199254740991},
  20.   16{*53-1801439850948198},17{54-36028797018963967},17{55-72057594037927935},
  21.   17{*56-144115188075855871},18{57-288230376151711743},18{58-576460752303423487},
  22.   18{*59-1152921504606846975},19{60-2305843009213693951},19{61-4611686018427387903},19{62-9223372036854775807}
  23.   );
  24.  
  25.   limits:array[0..62] of Int64 =(
  26.   99{0-1},99{1-3},99{2-7},
  27.   10{*3-15},999{4-31},999{5-63},
  28.   100{*6-127},9999{7-255},9999{8-511},
  29.   1000{*9-1023},99999{10-2047},99999{11-4095},99999{12-8191},
  30.   10000{*13-16383},999999{14-32767},999999{15-65535},
  31.   100000{*16-131071},9999999{17-262143},9999999{18-524287},
  32.   1000000{*19-1048575},99999999{20-2097151},99999999{21-4194303},99999999{22-8388607},
  33.   10000000{*23-16777215},999999999{24-33554431},999999999{25-67108863},
  34.   100000000{*26-134217727},9999999999{27-268435455},9999999999{28-536870911},
  35.   1000000000{*29-1073741823},99999999999{30-2147483647},99999999999{31-4294967295},99999999999{32-8589934591},
  36.   10000000000{*33-17179869183},999999999999{34-34359738367},999999999999{35-68719476735},
  37.   100000000000{*36-137438953471},9999999999999{37-274877906943},9999999999999{38-549755813887},
  38.   1000000000000{*39-1099511627775},99999999999999{40-2199023255551},99999999999999{41-4398046511103},99999999999999{42-8796093022207},
  39.   10000000000000{*43-17592186044415},999999999999999{44-35184372088831},999999999999999{45-70368744177663},
  40.   100000000000000{*46-140737488355327},9999999999999999{47-281474976710655},9999999999999999{48-562949953421311},
  41.   1000000000000000{*49-1125899906842623},99999999999999999{50-2251799813685247},99999999999999999{51-4503599627370495},99999999999999999{52-9007199254740991},
  42.   10000000000000000{*53-18014398509481983},999999999999999999{54-36028797018963967},999999999999999999{55-72057594037927935},
  43.   100000000000000000{*56-144115188075855871},9223372036854775807{57-288230376151711743},9223372036854775807{58-576460752303423487},
  44.   1000000000000000000{*59-1152921504606846975},9223372036854775807{60-2305843009213693951},9223372036854775807{61-4611686018427387903},9223372036854775807{62-9223372036854775807}
  45.   );
  46.  
  47. var
  48.   vbsr: Cardinal;
  49. begin
  50.   vbsr := BsrQWord(Abs(Z));
  51.   Result := digits[vbsr];
  52.   if z>=limits[vbsr] then
  53.     inc(Result);
  54. end;

The real change is to switch from BsrDWord to BsrQWord.
Title: Re: simple problem: count digits of number
Post by: isidroco on March 02, 2018, 03:34:36 am
Quote from: ASerge on March 01, 2018, 08:39:44 pm
and modified CntTbl:
Modified CntTbl is inefficient, it should discard half at each comparisson so as to have fewer comparissons. It could be important to know which are most often used results, if 50% of cases are 6 digits, a well chosen case will be a lot faster.
Log10 has the big advantage that can be used with real types.


PS: Can someone answer me here: https://forum.lazarus.freepascal.org/index.php?topic=40282.0
Title: Re: simple problem: count digits of number
Post by: engkin on March 02, 2018, 05:07:41 am
Quote from: isidroco on March 02, 2018, 03:34:36 am
should discard half at each comparisson so as to have fewer comparissons.

Did you say discard half:
Code: Pascal  [Select][+][-]
  1.   function cntBSrch(Z: int64): integer;
  2.   const
  3.     tbl: array[1..19] of int64 =
  4.       (9, 99, 999, 9999, 99999, 999999, 9999999, 99999999, 999999999, 9999999999, 99999999999,
  5.       999999999999, 9999999999999, 99999999999999, 999999999999999, 9999999999999999,
  6.       99999999999999999, 999999999999999999, 9223372036854775807);
  7.   var
  8.     L, H, I: integer;
  9.     absZ: int64;
  10.   begin
  11.     absZ := abs(z);
  12.     L := Low(tbl);
  13.     H := High(tbl);
  14.     I := L + (H - L) div 2;
  15.     while H > L do
  16.     begin
  17.       if absZ=tbl[I] then
  18.         break
  19.       else
  20.       begin
  21.         if absZ>tbl[I]  then
  22.           L := I + 1
  23.         else
  24.           H := I - 1;
  25.       end;
  26.       I := L + (H - L) div 2;
  27.     end;
  28.     Result := I;
  29.   end;
Title: Re: simple problem: count digits of number
Post by: ASerge on March 02, 2018, 05:13:00 am
Quote from: engkin on March 02, 2018, 02:26:03 am
Since the constants are code generated (had to use GMP):
It's not even compiled.
Title: Re: simple problem: count digits of number
Post by: ASerge on March 02, 2018, 05:24:10 am
Quote from: isidroco on March 02, 2018, 03:34:36 am
Modified CntTbl is inefficient, it should discard half at each comparisson so as to have fewer comparissons.
You declare that the function is inefficient, but give arguments that are already implemented in this function. The depth of "if" is not more than 5, which is logical, because only 2^5 can close 19 characters.
Give your effective example.
Title: Re: simple problem: count digits of number
Post by: ASerge on March 02, 2018, 05:26:11 am
Test project.
Code: Pascal  [Select][+][-]
  1. program project1;
  2. {$APPTYPE CONSOLE}
  3. {$MODE OBJFPC}
  4.  
  5. uses SysUtils, Math;
  6.  
  7. type
  8.   TInfo = record
  9.     N: Int64;
  10.     DigitsCount: Integer;
  11.   end;
  12.  
  13.   TInfoArray = array of TInfo;
  14.  
  15.   TCountDigitFunc = function(N: Int64): Integer;
  16.  
  17. procedure Measure(const FuncName: string; const Func: TCountDigitFunc;
  18.   const Data: TInfoArray);
  19. var
  20.   Start, Ticks: QWord;
  21.   iData: Integer;
  22. begin
  23.   Start := GetTickCount64;
  24.   for iData := Low(Data) to High(Data) do
  25.     if Data[iData].DigitsCount <> Func(Data[iData].N) then
  26.     begin
  27.       Writeln('Error in ', FuncName, ' for N return ', Func(Data[iData].N), ' digits');
  28.       Exit;
  29.     end;
  30.   Ticks := GetTickCount64 - Start;
  31.   Writeln(FuncName: 12, Ticks: 7, ' ticks');
  32. end;
  33.  
  34. function CntCaseTbl(Z: Int64): Integer;
  35. begin
  36.   case Abs(Z) of
  37.     0..9: Result := 1;
  38.     10..99 : Result := 2;
  39.     100..999: Result := 3;
  40.     1000..9999: Result := 4;
  41.     10000..99999: Result := 5;
  42.     100000..999999: Result := 6;
  43.     1000000..9999999: Result := 7;
  44.     10000000..99999999: Result := 8;
  45.     100000000..999999999: Result := 9;
  46.     1000000000..9999999999: Result := 10;
  47.     10000000000..99999999999: Result := 11;
  48.     100000000000..999999999999: Result := 12;
  49.     1000000000000..9999999999999: Result := 13;
  50.     10000000000000..99999999999999: Result := 14;
  51.     100000000000000..999999999999999: Result := 15;
  52.     1000000000000000..9999999999999999: Result := 16;
  53.     10000000000000000..99999999999999999: Result := 17;
  54.     100000000000000000..999999999999999999: Result := 18;
  55.   else
  56.     Result := 19;
  57.   end;
  58.   if Z < 0 then
  59.     Inc(Result);
  60. end;
  61.  
  62. function CntTbl(Z: Int64): Integer;
  63. var
  64.   ZAbs: Int64;
  65. begin
  66.   ZAbs := Abs(Z);
  67.   if ZAbs >= 1000000000 then // ZAbs >= 1e9
  68.     if ZAbs >= 100000000000000 then // ZAbs >= 1e14
  69.       if ZAbs >= 10000000000000000 then // ZAbs >= 1e16
  70.         if ZAbs >= 1000000000000000000 then // ZAbs >= 1e18
  71.           Result := 19
  72.         else // 1e16 <= ZAbs < 1e18
  73.           if ZAbs >= 100000000000000000 then // ZAbs >= 1e17
  74.             Result := 18
  75.           else // 1e16 <= ZAbs < 1e17
  76.             Result := 17
  77.       else // 1e14 <= ZAbs < 1e16
  78.         if ZAbs >= 1000000000000000 then // ZAbs >= 1e15
  79.           Result := 16
  80.         else // 1e14 <= ZAbs < 1e15
  81.           Result := 15
  82.     else // 1e9 <= ZAbs < 1e14
  83.       if ZAbs >= 100000000000 then // ZAbs >= 1e11
  84.         if ZAbs >= 1000000000000 then // ZAbs >= 1e12
  85.           if ZAbs >= 10000000000000 then // ZAbs >= 1e13
  86.             Result := 14
  87.           else // 1e12 <= ZAbs < 1e13
  88.             Result := 13
  89.         else // 1e11 <= ZAbs < 1e12
  90.           Result := 12
  91.       else // 1e9 <= ZAbs < 1e11
  92.         if ZAbs >= 10000000000 then // ZAbs >= 1e10
  93.           Result := 11
  94.         else // 1e9 <= ZAbs < 1e10
  95.           Result := 10
  96.   else // 0 <= ZAbs < 1e9
  97.     if ZAbs >= 10000 then // ZAbs >= 1e4
  98.       if ZAbs >= 1000000 then // ZAbs >= 1e6
  99.         if ZAbs >= 10000000 then // ZAbs >= 1e7
  100.           if ZAbs >= 100000000 then // ZAbs >= 1e8
  101.             Result := 9
  102.           else // 1e7 <= ZAbs < 1e8
  103.             Result := 8
  104.         else // 1e6 <= ZAbs < 1e7
  105.           Result := 7
  106.       else // 1e4 <= ZAbs < 1e6
  107.         if ZAbs >= 100000 then // ZAbs >= 1e5
  108.           Result := 6
  109.         else // 1e4 <= ZAbs < 1e5
  110.           Result := 5
  111.     else // 0 <= ZAbs < 1e4
  112.       if ZAbs >= 100 then // ZAbs >= 1e2
  113.         if ZAbs >= 1000 then // ZAbs >= 1e3
  114.           Result := 4
  115.         else // 1e2 <= ZAbs < 1e3
  116.           Result := 3
  117.       else // 0 <= ZAbs < 1e2
  118.         if ZAbs >= 10 then // ZAbs >= 1e1
  119.           Result := 2
  120.         else // 0 <= ZAbs < 1e1
  121.           Result := 1;
  122.   if Z < 0 then
  123.     Inc(Result);
  124. end;
  125.  
  126. function cntLog10(Z: Int64): Integer;
  127. begin
  128.   if Z = 0 then
  129.     Result := 1
  130.   else
  131.   begin
  132.     Result := 1 + Floor(Log10(Abs(Z)));
  133.     if Z < 0 then
  134.       Inc(Result);
  135.   end;
  136. end;
  137.  
  138. procedure FillRandomInfoData(var Data: TInfoArray);
  139. var
  140.   i: Integer;
  141. begin
  142.   Randomize;
  143.   for i := Low(Data) to High(Data) do
  144.     Data[i].N := RandomRange(Low(Int64) + 1, High(Int64));
  145. end;
  146.  
  147. procedure FillDigitsCount(var Data: TInfoArray);
  148. var
  149.   i: Integer;
  150. begin
  151.   for i := Low(Data) to High(Data) do
  152.     Data[i].DigitsCount := CntCaseTbl(Data[i].N);
  153. end;
  154.  
  155. var
  156.   Data: TInfoArray;
  157.   i: Integer;
  158. begin
  159.   SetLength(Data, 2000000);
  160.   for i := 1 to 10 do
  161.   begin
  162.     FillRandomInfoData(Data);
  163.     FillDigitsCount(Data);
  164.     Measure('CntCaseTbl', @CntCaseTbl, Data);
  165.     Measure('CntTbl', @CntTbl, Data);
  166.     Measure('cntLog10', @cntLog10, Data);
  167.     Writeln('');
  168.   end;
  169.   //Measure('cntBitly64', @cntBitly64, Data);
  170.   Readln;
  171. end.

Title: Re: simple problem: count digits of number
Post by: engkin on March 02, 2018, 05:28:55 am
Quote from: ASerge on March 02, 2018, 05:13:00 am
Quote from: engkin on March 02, 2018, 02:26:03 am
Since the constants are code generated (had to use GMP):
It's not even compiled.

Corrected the range check errors.
Title: Re: simple problem: count digits of number
Post by: isidroco on March 03, 2018, 04:01:11 pm
Quote from: ASerge on March 02, 2018, 05:24:10 am
You declare that the function is inefficient, but give arguments that are already implemented in this function. The depth of "if" is not more than 5, which is logical, because only 2^5 can close 19 characters.
Give your effective example.
I meant using IF to split powers of 2 digits, which would give up to 32 digits with 5 comparissons, althought that would make sense only with real types.  For int64 it's the same.

Title: Re: simple problem: count digits of number
Post by: isidroco on March 03, 2018, 04:33:17 pm
Quote from: engkin on March 01, 2018, 11:42:12 pm
function cntBitly(Z: integer): integer;
There is still space for enhancement.

It will fail for Z= 0 because: "BsrDWord: When the input is 0, the result is 255 (unsigned equivalent of -1)."
So it will try to get an out of range value in arrays. That will add another IF to function.
I got inspired this morning by the dumbest and probably quickest function:
Code: Pascal  [Select][+][-]
  1. var
  2.   digitsArr : array[0..10^10] of word;
  3.  {It only needs 20gb of ram for up to 9 digits}
  4.  
  5. procedure initializeArray;
  6.   var i: Int64; digits: word;
  7. begin
  8.   digits:=1;
  9.   for i:=0 to 10^10 do
  10.   begin
  11.     digitsArr:= digits;
  12.     if i mod 10= 0 then inc(digits);
  13.   end;
  14. end;
  15.  
  16. function cntTable(z: int64): int64;
  17. var
  18.   vbsr: Cardinal;
  19. begin
  20.   z:=abs(z);
  21.   if z<10^10 cntTable:= digitsArray[ z ]
  22.   else cntTable:= cntTable( z div 10^10)+ 10;
  23. end;
  24.  

I nice touch was making array of Word instead of Byte, I could have chosen longInt too but that would be a waste of Ram :)
Another funny thing is InitializeArray which will do 10^10 mod operations, I wonder how much it will take...

Title: Re: simple problem: count digits of number
Post by: ASerge on March 03, 2018, 05:12:12 pm
Quote from: isidroco on March 03, 2018, 04:01:11 pm
I meant using IF to split powers of 2 digits, which would give up to 32 digits with 5 comparissons, althought that would make sense only with real types.  For int64 it's the same.
I realized that you are not a reader, but a writer :)
Title: Re: simple problem: count digits of number
Post by: engkin on March 03, 2018, 06:19:35 pm
Quote from: isidroco on March 03, 2018, 04:33:17 pm
Quote from: engkin on March 01, 2018, 11:42:12 pm
function cntBitly(Z: integer): integer;
There is still space for enhancement.

It will fail for Z= 0 because: "BsrDWord: When the input is 0, the result is 255 (unsigned equivalent of -1)."
So it will try to get an out of range value in arrays. That will add another IF to function.
Good catch. I most likely will not use an IF here. A simple AND and an additional entry into the arrays:
Code: Pascal  [Select][+][-]
  1. function cntBitly64(Z: Int64): Integer;
  2. const
  3.   digits:array[0..63] of integer =(
  4. ...
  5.   1
  6.   );
  7.  
  8.   limits:array[0..63] of Int64 =(
  9. ...
  10.   9
  11.   );
  12. begin
  13.   vbsr := BsrQWord(Abs(Z)) and 63;
  14. ...

Quote from: isidroco on March 03, 2018, 04:33:17 pm
I got inspired this morning by the dumbest and probably quickest function:
Nice idea, pretty fast.

Quote from: isidroco on March 03, 2018, 04:33:17 pm
I nice touch was making array of Word instead of Byte, I could have chosen longInt too but that would be a waste of Ram :)
Another funny thing is InitializeArray which will do 10^10 mod operations, I wonder how much it will take...
I like how you are concerned about wasting memory.

Maybe the array should be included in the executable then you will not need to call InitializeArray?
Title: Re: simple problem: count digits of number
Post by: Bart 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
Title: Re: simple problem: count digits of number
Post by: ASerge on March 03, 2018, 08:40:13 pm
Quote from: engkin on March 02, 2018, 05:28:55 am
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
Title: Re: simple problem: count digits of number
Post by: isidroco 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]
Title: Re: simple problem: count digits of number
Post by: ASerge on March 04, 2018, 12:09:25 am
Quote from: isidroco on March 03, 2018, 11:21:31 pm
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.
Title: Re: simple problem: count digits of number
Post by: Bart on March 04, 2018, 12:18:50 am
Quote from: isidroco on March 03, 2018, 11:21:31 pm
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
Title: Re: simple problem: count digits of number
Post by: Solecist 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/
Title: Re: simple problem: count digits of number
Post by: Kays on June 22, 2021, 02:21:20 pm
Quote from: Bart on January 30, 2018, 09:08:30 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;
Title: Re: simple problem: count digits of number
Post by: BeniBela 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?
Title: Re: simple problem: count digits of number
Post by: Bart 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
Title: Re: simple problem: count digits of number
Post by: Bart 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
Title: Re: simple problem: count digits of number
Post by: MathMan 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
Title: Re: simple problem: count digits of number
Post by: Bart 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
Title: Re: simple problem: count digits of number
Post by: Stefan Glienke on February 05, 2024, 05:42:20 pm
I recently came across this problem and this is what I found to be the fastest function.

Code: Pascal  [Select][+][-]
  1. function CountDigits(Z: Int64): Integer;
  2. var
  3.   X: UInt64;
  4. begin
  5.   X := Abs(Z);
  6.   if X < 10000000000 then
  7.     if X < 10000 then
  8.       if X < 100 then
  9.         Result := 2 - Ord(X < 10)
  10.       else
  11.         Result := 4 - Ord(X < 1000)
  12.     else
  13.       if X < 100000000 then
  14.         if X < 1000000 then
  15.           Result := 6 - Ord(X < 100000)
  16.         else
  17.           Result := 8 - Ord(X < 10000000)
  18.       else
  19.         Result := 10 - Ord(X < 1000000000)
  20.   else
  21.     if X < 100000000000000 then
  22.       if X < 1000000000000 then
  23.         Result := 12 - Ord(X < 100000000000)
  24.       else
  25.         Result := 14 - Ord(X < 10000000000000)
  26.     else
  27.       if X < 1000000000000000000 then
  28.         if X < 10000000000000000 then
  29.           Result := 16 - Ord(X < 1000000000000000)
  30.         else
  31.           Result := 18 - Ord(X < 100000000000000000)
  32.       else
  33.         Result := 20 - Ord(X < 10000000000000000000);
  34.   Inc(Result, Ord(Z < 0));
  35. end;

As a bonus, it's also quite nice to read and understand due to the unintentional formatting.

By the way, since I see benchmark code using GetTickCount64. Don't do that - see https://learn.microsoft.com/en-us/windows/win32/api/sysinfoapi/nf-sysinfoapi-gettickcount64#remarks
Even though this still would not be 100% accurate for microbenchmarks such as this rather use QueryPerformanceCounter/QueryPerformanceFreq - or simply use TStopwatch - I think the FPC RTL should have that by now, doesn't it?
Title: Re: simple problem: count digits of number
Post by: dsiders on February 05, 2024, 06:06:20 pm
Quote from: Stefan Glienke on February 05, 2024, 05:42:20 pm
I recently came across this problem and this is what I found to be the fastest function.

Code: Pascal  [Select][+][-]
  1. function CountDigits(Z: Int64): Integer;
  2. var
  3.   X: UInt64;
  4. begin
  5.   X := Abs(Z);
  6.   if X < 10000000000 then
  7.     if X < 10000 then
  8.       if X < 100 then
  9.         Result := 2 - Ord(X < 10)
  10.       else
  11.         Result := 4 - Ord(X < 1000)
  12.     else
  13.       if X < 100000000 then
  14.         if X < 1000000 then
  15.           Result := 6 - Ord(X < 100000)
  16.         else
  17.           Result := 8 - Ord(X < 10000000)
  18.       else
  19.         Result := 10 - Ord(X < 1000000000)
  20.   else
  21.     if X < 100000000000000 then
  22.       if X < 1000000000000 then
  23.         Result := 12 - Ord(X < 100000000000)
  24.       else
  25.         Result := 14 - Ord(X < 10000000000000)
  26.     else
  27.       if X < 1000000000000000000 then
  28.         if X < 10000000000000000 then
  29.           Result := 16 - Ord(X < 1000000000000000)
  30.         else
  31.           Result := 18 - Ord(X < 100000000000000000)
  32.       else
  33.         Result := 20 - Ord(X < 10000000000000000000);
  34.   Inc(Result, Ord(Z < 0));
  35. end;

As a bonus, it's also quite nice to read and understand due to the unintentional formatting.

By the way, since I see benchmark code using GetTickCount64. Don't do that - see https://learn.microsoft.com/en-us/windows/win32/api/sysinfoapi/nf-sysinfoapi-gettickcount64#remarks
Even though this still would not be 100% accurate for microbenchmarks such as this rather use QueryPerformanceCounter/QueryPerformanceFreq - or simply use TStopwatch - I think the FPC RTL should have that by now, doesn't it?

TStopWatch is in 3.3.1. It's even in the system.diagnostics unit.


Title: Re: simple problem: count digits of number
Post by: Thaddy on February 05, 2024, 06:20:55 pm
A lot of code which can of course be done in a couple of lines:
Code: Pascal  [Select][+][-]
  1. program countdigitsexample;
  2. {$mode objfpc}
  3. uses math;
  4.  
  5. function CountDigits(n: Int64): Integer;inline;
  6. begin
  7.   if n = 0 then
  8.     Result := 1 // Special case for zero
  9.   else
  10.     Result := Trunc(Log10(Abs(n))) + 1;
  11. end;
  12.  
  13. var
  14.   num: Int64;
  15. begin
  16.   writeln('Enter an integer:');
  17.   readln(num);
  18.   writeln('Number of digits:', CountDigits(num));
  19. end.

 :D :D :o ::) :P

Translated from: https://www.geeksforgeeks.org/c-program-to-count-the-digits-of-a-number/

Because it does not loop and has just one comparison, it may even be more efficient over other solutions.
Btw: if this was already suggested in this long thread, I apologize, but I can't find it on quick examination.
[edit] Bart did something similar, but he uses floor() instead of trunc() so crashes on zero, which I handled separately. Floor() is also more expensive than Trunk().
Title: Re: simple problem: count digits of number
Post by: Stefan Glienke on February 06, 2024, 02:59:24 pm
Unless there is some other Log10 that does not take a float like that in Math this is ten times slower than the "lot of code".
Title: Re: simple problem: count digits of number
Post by: Zvoni on February 06, 2024, 03:29:14 pm
Quote from: Stefan Glienke on February 06, 2024, 02:59:24 pm
Unless there is some other Log10 that does not take a float like that in Math this is ten times slower than the "lot of code".
I looked into the source of the math-unit, and there it's just a multiplication of the natural logarithm "ln" (which apparantely is a compiler intrinsic) with a "magic" number
So i can't fathom how THAT could be slower than any looping

math-unit - Line 1005 pp (FPC3.2.2-32Bit)
Code: Pascal  [Select][+][-]
  1. function log10(x : float) : float;
  2.   begin
  3.     log10:=ln(x)*0.43429448190325182765;  { 1/ln(10) }
  4.   end;  

mathh.inc
Code: Pascal  [Select][+][-]
  1. function Ln(d : ValReal) : ValReal;[internproc:fpc_in_ln_real];  

In math.inc
Code: Pascal  [Select][+][-]
  1. function fpc_ln_real(d : ValReal) : ValReal;compilerproc;
  2.     begin
  3.       { Function is handled internal in the compiler }
  4.       runerror(207);
  5.       result:=0;
  6.     end;                
Title: Re: simple problem: count digits of number
Post by: Stefan Glienke on February 06, 2024, 03:36:58 pm
Quote from: Zvoni on February 06, 2024, 03:29:14 pm
i can't fathom how THAT could be slower than any looping
There is no looping involved in any of the fastest functions but just at most 5 register compares and 4 conditional jumps.
TinyPortal © 2005-2018