delphi - delphi中捕获变量溢出

Question

我正在开发显示所有 narcissistic numbers 的程序从 0 到最大值其中 max 是用户输入的值。我已经得到了所有代码，现在我正在努力改进它。因此，我有几个问题。

• 我需要检查数字的每一位数字并求其n次方。所以我决定创建 tab[0..9] ，其中包含 indexOfTab 的 n 次方，然后当我对数字中的所有数字求和时，它的工作原理如下:

  sum := sum + tab[x]; //where x is the digit that is currently checked 
  

  现在我想知道比较是否比这更快:

  sum:= sum + power(x,n); 
  

• 我还想捕获总和是否溢出。我知道如何通过 if .. then 来做到这一点。但我想知道是否有一种方法可以在总和改变符号时不检查每个操作，只有该程序会捕获该变量溢出，然后执行一些代码。

<小时/>

编辑:

 while (tmpNum>0) do //tmpNum - digit of currenlty checked number(curNum)
 begin
   try
     suma:= suma+tab[tmpNum mod 10]; //suma =0 
     //tab[x] = x^(curNum.Length);
   Except
     suma:= 0;
     tmpNum:=0;
     //here do something more 
   end;

   tmpNum:= tmpNum div 10; //divide number to get next modulo 
 end;

Answer 1

首先，使用值表的方法将是迄今为止最快的方法。至于溢出问题，我想稍后再讨论。

如果你真的想跑得尽可能快，有一些方法可以通过稍微分析一下问题来让事情跑得更快。当您知道如何查找某个值时，很容易假设要查找所有值，只需迭代所有值直至达到最大值。恐怕这很少是有效的，而这就是这种情况。

要知道这是真的，只需考虑计算数字 1034、1304、1403 和 1340。所有计算实际上完全相同，因此我们可以通过仅检查按降序排列的数字来大大减少计算量(在我们的例子中是 4310)。计算完 4^4 + 3^4 + 1^4 + 0^4 后，我们只需检查结果是否包含数字 4、3、1 和 0。如果包含数字，则计算出的数字是自恋的。这个概念还有助于最大限度地减少溢出测试，因为这意味着如果 8000(例如 8000)溢出，则即使检查更大的数字也是没有意义的。另一方面，在短路和通过 if 语句引入复杂性之间存在平衡。

这样做的缺点是数字不是按顺序生成的，因此最后可能需要某种排序。 (我没有这样做)。不过，从好的方面来说，它允许使用并行 for 循环。实际上，这并没有节省太多时间(在我的机器上可能节省 10%)，因为使用多个线程的开销很大程度上抵消了并行处理的 yield 。下面的代码显示了两种方式。

下面的程序允许用户输入一些数字(而不是最大值)来测试并处理溢出。我这样做是为了简化编码。在我的机器上计算所有 19 位自恋 < 2^63 大约需要 6 秒。

unit UnitNarcisistCalc;

interface

uses
  System.Classes,
  System.SysUtils,
  System.Threading,
  System.SyncObjs;

type
  TCalcArray = array[ 0..9] of int64;

  TNarcisistCalc = class
    (* Calculated narcisistic number of a certain size *)
  private
    class function CheckResult( const pSum : int64; const DigitsUsed : TCalcArray; const DigitCount : integer ) : boolean;
    class procedure AddADigit( const pDigit, pDigitsLeft : integer; const pSumSoFar : int64;
                         const pPowers, DigitsUsed : TCalcArray;
                         const pResults : TStrings; const DigitCount : integer );
  protected
  public
    class procedure CalcNos( const pOfSize : integer; const pResults : TStrings;
          pParallel : boolean );
  end;

implementation

{ TNarcisistCalc }

class procedure TNarcisistCalc.AddADigit(const pDigit, pDigitsLeft: integer;
  const pSumSoFar: int64; const pPowers, DigitsUsed: TCalcArray;
  const pResults: TStrings; const DigitCount : integer );
var
  iNewSum : int64;
  i : integer;
  iDigitsUsed : TCalcArray;
  iOverflowMsg : string;
  j: Integer;
begin
  {
    This recursive function builds the sum progressively until
    pDigitsLeft = 0; We are careful to make all parameters const
    so we don't accidently reuse anything.
  }
  iDigitsUsed := DigitsUsed;
  iNewSum := pSumSoFar + pPowers[ pDigit ];
  inc( iDigitsUsed[ pDigit ]);
  if iNewSum < 0 then
  begin
    // overflow - so ditch this strand.
    iOverflowMsg := 'Overflowed while evaluating ';
    for i := 9 downto 0 do
    begin
      for j := 1 to iDigitsUsed[ i ] do
      begin
        iOverflowMsg := iOverflowMsg+ IntToStr( i );
      end;
    end;
    pResults.Add( iOverflowMsg );
    exit;
  end;
  if pDigitsLeft > 1 then  // because we are not descrementing pDigitsLeft left even though logically we should
  begin
    for i := 0 to pDigit do
    begin
      AddADigit( i, pDigitsLeft - 1, iNewSum, pPowers, iDigitsUsed, pResults, DigitCount + 1 );
    end;
  end
  else
  begin
    // lowest level
    if CheckResult( pSumSoFar, iDigitsUsed, DigitCount + 1 ) then
    begin
      pResults.Add( IntToStr( pSumSoFar ));
    end;
  end;
end;

class procedure TNarcisistCalc.CalcNos(const pOfSize: integer;
  const pResults: TStrings; pParallel : boolean);
var
  fPowers : TCalcArray;
  fUsed : TCalcArray;
  i: Integer;
  j: Integer;
  iMaxDigit : integer;
  iOverflow : Boolean;
  iSum : int64;
  iOverflowMsg : string;
  iStrings : array[ 0.. 9 ] of TStringList;
begin
   // calculate the powwers
   pResults.Clear;
   iOverFlow := FALSE;
   iMaxDigit := 0;
   for i := 0 to 9 do
   begin
     fPowers[ i ] := i;
     fUsed[ i ] := 0;
     for j := 2 to pOfSize do
     begin
       fPowers[ i ] := fPowers[ i ] * i;
       if fPowers[ i ] < 0 then
       begin
         // overflow
         iOverflow := TRUE;
         iOverflowMsg := 'Overflowed while evaluating ' + IntToStr( i ) + '^' + IntToStr( pOfSize );
         pResults.Add( iOverflowMsg );
         break;
       end;
     end;
     if iOverflow then
     begin
       break;
     end
     else
     begin
       iMaxDigit := i;
     end;
   end;
   // we have set up our tabs and also prepared to not test any digits that
   // would automatically give an overflow
   if pParallel then
   begin
     TParallel.&For( 1, iMaxDigit, procedure(I : Integer )
       var
         iSum : int64;
       begin
         iStrings[ i ] := TStringList.Create;
         iSum := 0;
         AddADigit( i, pOfSize, iSum, fPowers, fUsed, iStrings[ i ], 0 );
       end);
       for i := 1 to iMaxDigit do
       begin
         pResults.AddStrings( iStrings[ i ]);
         iStrings[ i ].Free;
       end;
   end
   else
   begin
     for i := 1 to iMaxDigit do
     begin
       iSum := 0;
       AddADigit( i, pOfSize, iSum, fPowers, fUsed, pResults, 0 );
     end;
   end;
end;

class function TNarcisistCalc.CheckResult(const pSum: int64;
  const DigitsUsed: TCalcArray; const DigitCount : integer): boolean;
var
  iDigitsUsed : TCalcArray;
  iDigit, iSum : int64;
  iDigitCount : integer;
begin
  { what we are doing here is checking if pSum contains the
    same digits that were used to create it in the first place. }
  iDigitsUsed := DigitsUsed;
  iDigitCount := DigitCount;
  iSum := pSum;
  while iSum > 0 do
  begin
    iDigit := iSum mod 10;
    iSum := iSum Div 10;
    if iDigitsUsed[ iDigit ] > 0 then
    begin
      dec( iDigitsUsed[ iDigit ]);
      dec( iDigitCount );
    end
    else
    begin
      Result := FALSE;
      exit;
    end;
  end;
  Result := iDigitCount = 0;
end;

end.

了解这种方法与您的方法相比如何会很有趣。

19位数字的结果如下所示:

(非并行) 和

(并行)