### 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

Discuss (16 comments)