Thema: Delphi modulo-Beschleunigung

Einzelnen Beitrag anzeigen

Ullli

Registriert seit: 20. Mär 2007
4 Beiträge
 
Delphi 2005 Personal
 
#5

Re: modulo-Beschleunigung

  Alt 6. Apr 2007, 11:27
Hi, ich muß immer wieder Zahlen n auf ihre modulo-Reste testen, diese Schleife wird sehr häufig durchlaufen:

Delphi-Quellcode:
n := ...
  r := n mod 17;
  if r = 1 then
  begin
    ...
  end
  else
    if r = 4 then
    begin
      ...
    end;
Von allgemeinerem Interesse ist das Problem vielleicht bei Primzahl-Sieben.
Mein Eratosthenes-Sieb braucht auf meiner alten Gurke für Primzahlen < 10^9 ca 40s.
Da ich Primeln bis 10^12 brauche, bin ich auf Atkin (siehe wiki) umgestiegen. Dort fallen viele Rechnungen modulo 12 an. z.B.:

Delphi-Quellcode:
n := ...
  r := n mod 12;
  if (r = 1) or (r = 5) then
    Sieve.Bits[n] := not Sieve.Bits[n];
Durch die ganzen modulos läuft Atkin bei mir noch langsamer als Eratosthenes, was eigentlich nicht sein sollte.
Da gibts doch bestimmt irgendwelche Tricks?!
  Mit Zitat antworten Zitat