modulo-Beschleunigung

[Ullli]

Hallo,

ich habe ein Programm geschrieben, das etwas langsam läuft, weil darin viele mod-Operationen vorkommen. Es wird immer wieder n mod x, x € einer Gruppe von acht vorkommenden Zahlen gerechnet. Kann man das beschleunigen??

[Dax]

Sind diese Zahlen in der Form 2^x?

[Ullli]

nein, sind sie leider nicht. Aber ich kenne sie schon vor Durchlauf des Programms, könnte sie also in einen array schreiben und irgendetwas damit machen.

[Zacherl]

Zeig mal ein bisschen Code ..

[Ullli]

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?!