Recent

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

Bart

  • Hero Member
  • *****
  • Posts: 5275
    • Bart en Mariska's Webstek
Re: simple problem: count digits of number
« Reply #15 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

ASerge

  • Hero Member
  • *****
  • Posts: 2222
Re: simple problem: count digits of number
« Reply #16 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.

engkin

  • Hero Member
  • *****
  • Posts: 3112
Re: simple problem: count digits of number
« Reply #17 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.

ASerge

  • Hero Member
  • *****
  • Posts: 2222
Re: simple problem: count digits of number
« Reply #18 on: March 02, 2018, 01:53:48 am »
@ASerge, I heard you did not like the source code of CntTbl. Wait until you see this one:
What about Int64 and measurements?

engkin

  • Hero Member
  • *****
  • Posts: 3112
Re: simple problem: count digits of number
« Reply #19 on: March 02, 2018, 02:26:03 am »
@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.
« Last Edit: March 02, 2018, 05:26:16 am by engkin »

isidroco

  • New Member
  • *
  • Posts: 12
Re: simple problem: count digits of number
« Reply #20 on: March 02, 2018, 03:34:36 am »
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
« Last Edit: March 02, 2018, 03:37:43 am by isidroco »

engkin

  • Hero Member
  • *****
  • Posts: 3112
Re: simple problem: count digits of number
« Reply #21 on: March 02, 2018, 05:07:41 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;

ASerge

  • Hero Member
  • *****
  • Posts: 2222
Re: simple problem: count digits of number
« Reply #22 on: March 02, 2018, 05:13:00 am »
Since the constants are code generated (had to use GMP):
It's not even compiled.

ASerge

  • Hero Member
  • *****
  • Posts: 2222
Re: simple problem: count digits of number
« Reply #23 on: March 02, 2018, 05:24:10 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.

ASerge

  • Hero Member
  • *****
  • Posts: 2222
Re: simple problem: count digits of number
« Reply #24 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.


engkin

  • Hero Member
  • *****
  • Posts: 3112
Re: simple problem: count digits of number
« Reply #25 on: March 02, 2018, 05:28:55 am »
Since the constants are code generated (had to use GMP):
It's not even compiled.

Corrected the range check errors.

isidroco

  • New Member
  • *
  • Posts: 12
Re: simple problem: count digits of number
« Reply #26 on: March 03, 2018, 04:01:11 pm »
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.


isidroco

  • New Member
  • *
  • Posts: 12
Re: simple problem: count digits of number
« Reply #27 on: March 03, 2018, 04:33:17 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...

« Last Edit: March 03, 2018, 04:36:35 pm by isidroco »

ASerge

  • Hero Member
  • *****
  • Posts: 2222
Re: simple problem: count digits of number
« Reply #28 on: March 03, 2018, 05:12:12 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 :)

engkin

  • Hero Member
  • *****
  • Posts: 3112
Re: simple problem: count digits of number
« Reply #29 on: March 03, 2018, 06:19:35 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. ...

I got inspired this morning by the dumbest and probably quickest function:
Nice idea, pretty fast.

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?

 

TinyPortal © 2005-2018