Coding Challenge I

Pages: 1 2 3 4 5 6 7 8 9

Solution from HP

I spent a couple of hours this evening putting together my entry, which I have attached. I did it in Delphi, mostly because I figured no one else would bother with a Delphi submission so I wanted my favorite compiler represented

program pi;

//Included binary is compiled on Delphi 6 update 2
//with the following compiler switches

{$O+} //turn on optimizations
{$R-} //turn off range checking
{$I-} //turn off I/O checking
{$Q-} //turn off Overflow checking
{$V-} //turn off shortstring type checking
{$P-} //turn off open params (not needed)
{$D-} //turn off debugging info
{$C-} //turn off assertions

{$APPTYPE CONSOLE}

{
  Changes made:
  1. All calls to Low(A) replaced with constant 0.
     Low(A) will always equal to zero with a dynamic
     array. Low() and High() function calls are not
     free in Delphi and incur overhead.
  2. Unrolled the first loop inside of the main
     outer loop. According to my profiling, the program
     spends the majority of its time inside of this loop.
     Tried different levels of unlooping and
     gauged performance, the best level seemed to be to
     unloop by a factor of 4, anything more than this
     had very little affect. This appears to be the only loop
     which would benefit from unrolling (of course
     I could be wrong about that) It may have been possible
     to get a minor speedup by unrolling the outerloop, but odds
     are it would have made it worse, and it would have resulted
     in some HORRIBLE looking code, so I declined to even try.
  3. Reorganized if-then-else statement on Q var to
     place the most common code path first by move the most
     common case (Q <> 9 or 10) and placed other two conditions
     within a case statement. This is pretty much a Delphi
     specific optimization as in Delphi Case Statements are
     quite a bit more efficient than if-than-else statements
     strung together. This had very littel if any measurable
     effect, but it didnt hurt so I left it in.
  4. Re-arranged the way the worker function is called. The
     original code passed the variable NumDigits, which represented
     how many digits of pi to compute. This variable was used to
     then determine the size of the array. This was not optimal
     for register use, because NumDigits was never actually used
     inside of any loops, but the arraysize is. So I reversed it. Now
     numDigits is a global var, and the arraysize is passed into the
     working function. This allows Delphi (theoretically) to place
     this var in a register. It also eliminates mulitple calls to
     High(A) which are now no longer needed (and incur overhead, see 1.)

  Note: All these optimizations result in a VERY small speedup. I only
        took a wack at it because I figured it unlikely anyone else
        would even submit a Delphi entry. I honestly believe there
        is little more that could be done without either resorting
        to assembly code or ending up with some really ugly and hard to
        read code. Delphi simply isnt built for speed, it is built for ease
        of use and doing all these tricks and such to speed it up for such
        a minor improvement are probably a waste of time in most cases. Also
        my system is an Athlon XP 1800+ and that is what I optimized on. These
        optimizations may not be effective on a P4 system, and may even slow it
        down. I dont really know as I dont have one…
}

var
  NumDigits: Integer;
  Code: Integer;
  F: TextFile;
  A: array of LongInt;

function ComputePi(ArrayHigh: Integer): string;
var
  I, J, K, P, Q, X, Nines, Predigit: Integer;
  PiLength: Integer;
begin
  SetLength(Result, NumDigits+1);
  PiLength := 1;
  for I := 0 to ArrayHigh do
    A[I] := 2;
  Nines := 0;
  Predigit := 0;
  for J := 0 to NumDigits-1 do
  begin
    Q := 0;
    P := 2 * ArrayHigh + 1;
    I := ArrayHigh;
    while ((I+1) mod 4) <> 0 do
    begin
      X := 10*A[I] + Q*(I+1);
      A[I] := X mod P;
      Q := X div P;
      dec(P,2);
      dec(I);
    end;
    while I > -1 do
    begin
      X := 10*A[I] + Q*(I+1);
      A[I] := X mod P;
      Q := X div P;
      dec(P,2);
      X := 10*A[I-1] + Q*(I);
      A[I-1] := X mod P;
      Q := X div P;
      dec(P,2);
      X := 10*A[I-2] + Q*(I-1);
      A[I-2] := X mod P;
      Q := X div P;
      dec(P,2);
      X := 10*A[I-3] + Q*(I-2);
      A[I-3] := X mod P;
      Q := X div P;
      dec(P,2);
      dec(i,4);
    end;
    A[0] := Q mod 10;
    Q := Q div 10;
    if ((Q < 9) or (Q > 10)) then
    begin
      Result[PiLength] := Chr(Predigit + Ord(‘0’));
      Predigit := Q;
      for K := 1 to Nines do
        Result[PiLength+K] := ‘9’;
      PiLength := PiLength + Nines + 1;
      Nines := 0;
    end
    else
    case Q of
      9: Inc(Nines);
      10:
      begin
        Result[PiLength] := Chr(Predigit + 1 + Ord(‘0’));
        for K := 1 to Nines do
          Result[PiLength+K] := ‘0’;
        PiLength := PiLength + Nines + 1;
        Predigit := 0;
        Nines := 0;
      end;
    end;
  end;
  Result[PiLength] := Chr(Predigit + Ord(‘0’));
end;

begin
  if ParamCount = 0 then
    WriteLn(‘usage: pi #DIGITS [FILE]’)
  else
  begin
    Val(ParamStr(1), NumDigits, Code);
    if Code <> 0 then
    begin
      WriteLn(‘Invalid # digits: ‘, ParamStr(1));
      Halt(1);
    end;
    SetLength(A, 10*NumDigits div 3);
    if ParamCount > 1 then
    begin
      AssignFile(F, ParamStr(2));
      Rewrite(F);
      WriteLn(F, ComputePi(High(A)));
      CloseFile(F);
    end
    else
      WriteLn(ComputePi(High(A)));
  end;
end.

Pages: « Prev  1 2 3 4 5 6 7 8 9