Catch if variable overflow in delphi

Question

I'm working on program that shows all narcissistic numbers from 0 to max. Where max is value typed by user. I got all code already now I am trying to improve it. So due this I have few questions.

• I need to check every digit of number and make them to the n-th power. So I decided to create tab[0..9] which contains indexOfTab to n-th power and then when I sum all digits from number it works like that:

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

  Now i am wondering if comparing is faster than this:

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

• I also want to catch if sum overflow. And I know how to do this by if .. then. But I am wondering if there is a way to NOT checking on every operation if sum change sign, only that program will CATCH that this variable overflowed and then it will do some code.

---

EDIT:

 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

First of all your method of using a table of values will be by far the fastest method to use. As far as overflow is concerned, I would like to come back to that shortly.

If you are serious about running as fast possible, there are ways of making things go faster by analysing the problem a little. It is very tempting to assume that to find all values when you know how to find one, you just need to iterate through all values up to your max. It is rarely true that this is efficient, I am afraid, and this is such a case.

To see that this is true, just think about calculating the numbers 1034, 1304, 1403 and 1340. All the calculations are actually exactly the same, so we can reduce our calculations very substantially by only examining digits going in descending order (in our case 4310). Having calculated 4^4 + 3^4 + 1^ 4 + 0^4 we then simply need to check that the result contains the digits 4,3,1 and 0. If it does then the number calculated is narcissistic. This notion also helps with minimising overflow tests, because it means that if 8000, for example overflows, there is no point in even checking larger numbers. On the other hand there is a balance between short circuiting, and introducing complexity through if statement.

The down side to this is that numbers are not generated in order, so some sort of sorting may be required at the end. (I have not done this). On the upside, though, it allows for a parallel for loop to be used. In practice this did not save much time (maybe 10% on my machine) because the overheads of using multiple threads largely offset the gains in doing things in parallel. The code below shows both ways.

The program below allows the user to input a number of digits (rather than a maximum value) to test and also deals with overflows. I did that for simplicity of coding. On my machine calculation all 19 digit narcissistic < 2^63 took about 6 seconds.

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.

It would be interesting to know how this approach compares with yours.

The result for 19 digit numbers is shown below:

(Non parallel) and

(Parallel)