For-do Schleife mit Sprung

[F.W.]

Ich programmiere gerade einen Primzahlgenerator. Der soll von einer Zahl, bis zu einer Zahl(die der Anwender eingibt) prüfen.
Da braucht man ja eigentlich nur alle ungeraden Zahlen zu prüfen, denn alle geraden Zahlen kann man ja durch 2 teilen.

Ich habe die Suchfunktion schon fertig programmiert, allerdings mit einer For-Do-Anweisung. Und die geht bei mir immer nur 1 hoch.
Kann man da noch irgendwas dranhängen, wie z.B.:

Delphi-Quellcode:

 for I := 3 to ZAHL Step 2 do begin
...
 end;

Sollte es keine For-DoAnweisung mit einem solchen(oder ähnlichem) Feature geben, was könntet ihr mit noch empfehlen.

Es kommt halt auch auf die Geschwindigkeit an, sonst würde ich alle Zahlen nehmen, und vorher mit "if Trunc(Zahl/2)*2 = Zahl then GERADE ZAHL" auf gerade Zahlen überprüfen lassen, aber da dauerte es (wenn auch nur wenige Sekunden, aber das summiert sich ja) länger.

Danke schonmal! :mrgreen:

[himitsu]

Ein Hallöle von http://www.FrankNStein.de/Smiley-Wolke.gif,

Code:

[b]For[/b] I := 1 [b]to[/b] (ZAHL - 1) [b]div[/b] 2 [b]do Begin[/b]
  [color=red]TestZahl[/color] := (I * 2) + 1;
  ...
[b]End[/b];

Da ja auch nur bis Zahl / 2 geprüft werden braucht:

Code:

[b]For[/b] I := 1 [b]to[/b] ZAHL [b]div[/b] 4 [b]do Begin[/b]
  [color=red]TestZahl[/color] := (I * 2) + 1;
  ...
[b]End[/b];

http://www.delphipraxis.net/images/common/divider.jpg
http://www.FrankNStein.de/Smiley-Kuss.gif * * http://www.FrankNStein.de/Smiley-Spinne.gif * * * http://www.FrankNStein.de/Smiley-Winken.gif

[Pseudemys Nelsoni]

du könntest in die prozedur doch "inc(I)" einfügen

[phlux]

Meines wissens nach darf man die Schleifenvariable nicht innerhalb der Schleife verändern :mrgreen:

[Pseudemys Nelsoni]

und wieso?

[phlux]

Stell dir vor was passiert wenn du i größer als die Bedingung zum Abbruch der Schleife änderst ;)
Außerdem meckert der Komplizierer dann :P

[phlux]

Entweder du nimmst ne while oder eine repeat Schleife, das die einzige möglichkeit in meinen augen :cyclops:

[Matze]

Ist das nicht egal, welche Schleife?

Alle 3 bewirken, meiner Meinung nach, das gleiche:

Delphi-Quellcode:

for i:=1 to Zahl do
begin
...
end;

while i<Zahl do
begin
...
end;

repeat
...
until i=Zahl

Naja, gleich ist es nicht, aber es müsste ja das Ähnliche bewirken, oder?

[Niels]

Es ging ja darum, dass die Laufvariable geändert werden soll. Das ist bei For-Schleifen nun mal nicht möglich. Naja Repeat und While ist eigentlich das gleiche - eins hat halt ne Eintrittsbedingung und das andre ne Austrittsbedingung. Musste halt immer nehmen wie's am besten passt grad (auch von der Logik her). Der Quellcode sollte ja möglichst selbstkommentierend sein.

MfG Niels

[Luckie]

Bei while und repeat bist du selbst dafür verantwortlich dass die Abbruchbedingung greift, sprich hie rmuss man in diesem Fall selber i inkrementieren, bei der for-Schleife wird vorher die Anzahl der Schleifendurchläufe ermittelt und dann die Schleife auch nur so und so viel mal druchlaufen.

Das man den Schleifen in einer for-Schleife nicht ändern kann (so ohne weiteres, mit einem Trick geht es) ist Compiler bedingt. Mit C/C++ Compiler kann man das machen. Nur wenn der Compiler weiß, wie oft eine Schleife durchlaufen wird, kann er besser optimieren. Desweitern sehe ich keinen Sinn darin in einer for-Schleife den Schleifenzähler ändern zu wollen, sie wurde extra für Schleifen komzepiert bei denen man weiß, wie oft sie durchlaufen wird.

Die Lösung wäre also hier eine while-Schleife.

[Niels]

Zitat:

Zitat von Luckie

..., mit einem Trick geht es)...

Wie? :gruebel:

[phlux]

Genau Luckie zauber mal was aus deinem Hut (oder der roten Mütze :xmas: ) :)

[Luckie]

Abrakadabra, dreimal schwarzer Kater. Schwupps:

Delphi-Quellcode:

procedure TForm1.Button1Click(Sender: TObject);
var
  i: Integer;
begin
  for i := 0 to 9 do
  begin
    Inc(Integer(Pointer(@i)^));
    ShowMessage(IntToStr(i));
  end;
end;

[nailor]

goil! das ist ja end-praktisch. man sollte die while schleifen weglassen, die sind ja voll überflüssig :warn:

[phlux]

Also überschreibst du nur die Stelle im Speicher (wo der Zählwert steht), ohne das der Compiler es beim kompilieren merkt??

[nailor]

Ja. jedem Menschen fällt auf, dass

Delphi-Quellcode:

@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@i^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

wenn man gleich viele @ wie ^s hat, wieder genau i ist. Aber der Compiler prüft sowas (zurecht) nicht nach. Allerdings habe ich immer gedacht, dass Schleifen intern anders funktionieren, und Luckies Gebastel daher eh nicht funktioniert. Aber eigentlich ist es mir ***egal, obs geht oder nicht, weil ich das (hoffentlich) nie brauchen werde!

[phlux]

Vielen dank für diesen wertvollen Post, ich werd ihn mir einrahmen :D :thumb:

[nailor]

ich helfe, wo ich kann! PS: Nicht überreiben, irgendwann meckert Delphi von wegen "zu lange Zeile"

[Niels]

Was man eventuell dann beachten sollte, dass die schleife

Delphi-Quellcode:

for i := m to n do

die Abbruchsbedingung (wenn man das so nennen kann) bei i = n+1 liegt. Wenn i also erstmal > i+1 ist dann hat man ne feine Endlosschleife.

MfG Niels

[HAF4ever]

Zitat:

Zitat von phlux

Meines wissens nach darf man die Schleifenvariable nicht innerhalb der Schleife verändern :mrgreen:

das kann ganz schön lustig werden ...
der compiler übersetzt das dann entweder mit einen increase and jump oder einen decrease and jump und bricht ab wenn er den wert erreicht hat bzw wenn er 0 erreicht hat ...
verändert man die variable, dann könnte da ziemlich schnell eine endlos schleife daraus werden ...

[Pseudemys Nelsoni]

Zitat:

goil! das ist ja end-praktisch. man sollte die while schleifen weglassen, die sind ja voll überflüssig

ich find die wichtiger als die Repeat schleife :\

[phlux]

Beide Schleifen sind wichtig, vllt solltet ihr euch mal klar machen was der Unterschied zwischen einer "Kopf" und ner "Fuß" gesteuerten Schleife ist ;)

[nailor]

[offtopic] das Gegenteil von "Kopf" gesteuert ist "Schwanz" gesteuert [/offtopic]

Mein Beitrag mit "goil! dann..." war ironisch gemeint. Das nur nochmal für alle, denen das nicht ganz klar war.
Fakt ist, dass man ausgehen von einer while-Schleife die beiden anderen relativ schnell geschrieben hat:

bei der repeat-Schleife:

Delphi-Quellcode:

anweisung;
while ISTrue do
anweisung;

bei der for schleife:

Delphi-Quellcode:

while soOft >= 0 do
begin
dec(soOft);
anweisung;
end;

aber wer will das schon immer machen. Also doch gut, dass es alle drei gibt!

[d3g]

Zitat:

Zitat von Nailor

Allerdings habe ich immer gedacht, dass Schleifen intern anders funktionieren, und Luckies Gebastel daher eh nicht funktioniert.

Wenn der Optimierer Lust dazu hat, ist das auch so. Dann wird das CX-Register als Schleifenvariable benutzt und der Sprung funktioniert mit dem LOOP-Befehl statt mit einem CMP- und einem JZ-Befehl (braucht 3 Takte weniger). Der Nachteil ist natürlich, dass die Schleife dann rückwärts läuft, was nicht immer gewollt ist und was du ganz hart zu spüren bekommst, wenn der Optimierer mal Amok läuft.

[F.W.]

Ich denke, ich werde mich für den Code von himitsu entscheiden, der ist für mich(auf Grund meiner Erfahrung und Faulheit) der Beste.

Danke für die vielen Antworten!. :thuimb:

[nailor]

noch ein tipp: du musst nichtmal bis "maxZahl div 2" durchgehen. "ceil(sqrt(maxZahl))" reicht!

[F.W.]

Die Anweisung kann ja schnell mal 10 Sekunden (und meistens noch drüber) dauern. Damit ich Fortschritte sehen kann, habe ich mir was ausgedacht:

Ich nehme mir die Startzeit und die Endzeit und führe dann SecondsBetween(...) aus. Allerdings ist eine Sekunde bei solchen größenverhältnissen nicht gerade genau. Aber mit einem Timer(der dann aller 10 ms den Zeitwert erhöht) kann ich's nicht machen, weil der ja seine Anweisungen erst nach der Beendigung der Primzahlsuche fortsetzt.

Habt ihr noch 'ne Idee?

[Luckie]

wie wird der Fortschritt angezeiht? Ruf in der Schleife mal die Refresh-Methode der entsprechenden Komponent auf. Oder pack das in einen Thread und lass dir vom Thread eine Message an dein fenster schicken bei jedem Fortschritt.

[F.W.]

Also der Fortschritt wird über eine TProgressBar angezeigt. Das habe ich schon ziemlich optimiert. Aber darüber sehe ich ja nicht, wie lange es von Zahl X bis Zahl Y gesucht hat. Ich habe ja schon oben meine momentane Zeitmessmethode beschrieben. Aber wie kann ich es Zehntelsekundengenau machen?

Wie meinst du das, mit der Refresh-Methode? Soll ich einen Timer mit der Aufgabe "Benötigte Zeit := Benötigte Zeit + 0,01" und den dann mit der Refresh-Methode aufrufen?

[nailor]

Luckie meinte, dass wenn du innerhalb deiner Methode den Progress erhöhst, man das trotzdem erst sehen wird, wenn deine Methode fertig abgearbeitet ist. Um das zu verhindern, und zwischendurch die ANzeige auf den aktuellen Stand, sollte man irgendwas von wegen Repaint/Refresh/Update einbauen [aber nicht ZU OFT, sonst wirds merklich langsamer]

[F.W.]

Der Fortschritt wird auch so weitergezeichnet. Was ich brauche ist halt irgendwas, was die Zeit "zählt".

[nailor]

dann mach deine Anzeige nicht von der Zeit abhängig, sondern von der Anzahl der untersuchten Zahlen

[F.W.]

Die Zeit ist wichtig für mich, damit ich(weil ich ja noch dran rumm progge) weiß, welcher Quellcode besser(schneller) ist. Außerdem hat ja jeder Computer eine andere Geschwindigkeit.

[jbg]

Zitat:

Zitat von Nailor

Allerdings habe ich immer gedacht, dass Schleifen intern anders funktionieren, und Luckies Gebastel daher eh nicht funktioniert.

Luckies Code funktioniert, da ein Borland Mitarbeiter des Compiler-Teams diesen Spezialfall bedacht hat und dem Code-Optimierer dieses beigebracht hat. Was der Compiler in diesem Fall erzeugt ist eine nicht optimierte for-Schleife, bei der die Manipulation ohne Folgen (Endbedingung ausgeschlossen) möglich ist.

Zitat:

Zitat von d3g

Wenn der Optimierer Lust dazu hat, ist das auch so. Dann wird das CX-Register als Schleifenvariable benutzt und der Sprung funktioniert mit dem LOOP-Befehl statt mit einem CMP- und einem JZ-Befehl (braucht 3 Takte weniger).

Das war mal zu 386-Zeiten so. Beim 486 ist der LOOP Befehl im Vergleich zu "DEC, JZ" eine lahme Schnecke. Selbst ein "CMP, JE" ist auf einem Pentium schneller. Dadurch ist es egal ob nun das ECX Register oder ein anderes freies als Zähler benutzt wird, was der Delphi-Compiler sich auch zu Nutze macht.


Noch eine Idee für die for-Schleife mit einem Step:

Delphi-Quellcode:

var
  i, ii: Integer;
begin
  for ii := 0 to (Count div 2 - 1) do
  begin
    i := ii * 2; // => SHL ist nicht gerade langsam
    // hier mit i arbeiten
  end;
end;

[phlux]

Zitat:

Zitat von jbg

Noch eine Idee für die for-Schleife mit einem Step:

Delphi-Quellcode:

var
  i, ii: Integer;
begin
  for ii := 0 to (Count div 2 - 1) do
  begin
    i := ii * 2; // => SHL ist nicht gerade langsam
    // hier mit i arbeiten
  end;
end;

*lol* kommt da nicht (Count div 2 - i) hin???

[jbg]

Zitat:

Zitat von phlux

kommt da nicht (Count div 2 - i) hin???

Wieso sollte da i hinkommen?

[nailor]

Zitat:

Zitat von F.W.

Die Zeit ist wichtig für mich, damit ich(weil ich ja noch dran rumm progge) weiß, welcher Quellcode besser(schneller) ist. Außerdem hat ja jeder Computer eine andere Geschwindigkeit.

Ganz an den Anfang ein GetTickCount; ganz ans Ende noch eins. Daraus die Rechenzeit bestimmen!

Zum Anzeigen des Fortschritts mit Anzahl der untersuchten Zahlen arbeiten. Ehrlich!!!


:mrgreen: :mrgreen: :mrgreen: Oder den ganzen Code zweimal ausführen, damit du beim zweiten mal vorher weißt, wielange er braucht, und davon den Fortschritt abhängig machen kannst. :mrgreen: :mrgreen: :mrgreen:

[phlux]

Zitat:

Zitat von jbg

Zitat:

Zitat von phlux

kommt da nicht (Count div 2 - i) hin???

Wieso sollte da i hinkommen?

Kp :roll: ergibt auch keinen Sinn, vergiss es einfach :lol:

[F.W.]

Die Differenz der beiden GetTickCount s gibt mir also den Zeitunterschied in 1000stel-Sekunden zurück :o

Sehr schön danke!!!! :thuimb:

[jbg]

Die Auflösung ist nicht ganz 1/1000, sondern liegt etwas darunter.