Palindrom-Zahlen

Gestern bin ich auf eine kleine Herausforderung für den Entwickler in mir gestoßen. Delphi.about.com sucht einen Algorithmus der für einen Zahlenbereich (z.B. 1 bis 10.000.000) die Anzahl der vorhandenen Palindromzahlen findet.

Eine Palindromzahl ist eine Zahl, die von vorne und hinten gelesen den gleichen Wert hat. Z.B. 121, 3663 oder 98789.

Da in Delphi String-Vergleiche bzw. die Umwandlungen von Integer zu String unglaublich langsam sind (zumindest für n > 1 Million), kann man soetwas wie das folgende komplett vergessen:

function IsPalindrome(aNumber : integer) : boolean;
begin
  result := IntToStr(aNumber) = ReverseString(IntToStr(aNumber));
end;

Stattdessen sollte man lieber die Integer direkt vergleichen. Hierfür braucht man eine Funktion, die einen Integer umdrehen kann:

function ReverseInteger(aNumber : integer) : integer;
begin
  result := 0;
  while aNumber > 0 do
  begin
    result := 10 * result + aNumber mod 10;
    aNumber := aNumber div 10;
  end;
end;

Modulo und Integer-Divisionen sind aber auch nicht ohne. Von daher wäre es doch praktisch, wenn man die Umwandlungen und Divisionen weglassen könnte und stattdessen direkt die Ziffern vergleicht. Um auf die Ziffern zuzugreifen können muss man den Integer in einen Array laden.

Type TByteArray = array of byte;
function IntToByteArray(aNumber : integer) : TByteArray;
var
  i : integer;
begin
  SetLength(result,8); // 8 Stellen, das reicht für 10.000.000
  for i := 0 to 7 do // Array mit Nullen initialisieren
  begin
    result[i] := 0;
  end;
  i := 0;
  while aNumber > 0 do
  begin
    result[i] := aNumber mod 10;
    aNumber := aNumber div 10;
    inc(i);
  end;
end;

Danach finden sich die Einer im Index 0, die Zehner im Index 1, die Hunderter im Index 2, usw. Diesen array kann man nun ganz einfach auf Palindrome überprüfen.

function IsPalindrom(aNumber : TByteArray; aDigits : byte) : boolean;
var
  a, b : integer;
begin
  result := true;
  a := 0;
  b := aDigits-1;
  while (a < b) and result do
  begin
    result := result and (aNumber[a] = aNumber[b]);
    inc(a);
    dec(b);
  end;
end;

Wenn man jetzt versucht den Zahlenbereich mit einer Schleife abzuarbeiten hat man noch nicht viel gewonnen, da man bei der Umwandlung von Integer nach Array wieder jede Menge Modulo und Integer-Divisionen hat. Also muss man die Zahl direkt im Array erhöhen.

procedure IncArray(aArray : TByteArray; aDigit : byte);
begin
  if aDigit <= 7 then // Unser Array ist auf 8 Stellen (Index 0-7) beschränkt
  begin
    inc(aArray[aDigit]); // Feld erhöhen
    if (aArray[aDigit] mod 10 = 0) then // bei überlauf
    begin
      aArray[digit] := 0; // Feld auf 0 setzen
      if aDigit < 7 then incArray(aDigit+1); // und nächstes Feld erhöhen (Rekursion!)
    end;
  end;
end;

Das Erhöhen in einem Array ist natürlich komplizierter als eine Zahl zu erhöhen. Man hat zwar mehr Additionen, aber keine Modulo-Operation oder Integer-Division mehr. Dadurhc spart man wertvolle Taktzyklen ein, da eine CPU wesentlich schneller addieren als teilen kann.

Das fertige Projekt kann man hier herunterladen. Den Sourcecode gibt es hier.

Im fertigen Projekt kann man schließlich noch die Anzahl der Threads wählen, die auf die Suche nach Palindromzahlen gehen sollen. Damit kam ich auf einem Intel Core 2 Duo T5750 auf durchschnittlich 0,16 Sekunden mit 5 Threads. (Minimum: 0,13 Sekunden)

Mein Mitbewohner hat das Verfahren optimiert während Ich das Ganze implementiert habe.