Delphi-PRAXiS

Delphi-PRAXiS (https://www.delphipraxis.net/forum.php)
-   Object-Pascal / Delphi-Language (https://www.delphipraxis.net/32-object-pascal-delphi-language/)
-   -   probedivision -abbruch von schleife funktioniert nicht (https://www.delphipraxis.net/141424-probedivision-abbruch-von-schleife-funktioniert-nicht.html)

qwertz543221 8. Okt 2009 18:00


probedivision -abbruch von schleife funktioniert nicht
 
ich möchte folgende proceudre (probedivision)abrrechen und mit dem restlichen code weitermachen, doch wieso kann ich die schleife nicht beenden, wenn die abbruchbedingung erreicht ist?
Delphi-Quellcode:
function tform1.miller_rabin(n: ansistring; t: longint):boolean;
label l;
var
  n1,n2, y, r, x: string;
  s,j,i: longint;
const
 primes:array[1..5]of string=('2','3','5','7');//in meinem fall deujtlich größer
   // probedivison
function probedivision(n:ansistring):boolean;
var
 I:longint;
begin
i:=1;
result:=true;
while i<=5{9549} do
begin
if mathe.modulo(n,primes[i])='0'
 then
 begin
 result:=false;
 break;
 end
   else i:=i+1;
end;
end;

begin
result := false;
if Mathe.istGerade(n)
  then exit;

begin
{get n1 = n - 1} 
{get n2 = n - 2}
if probedivision(n)=true
 then
  begin
  n1 := n;
  Mathe.Minus1(n1);
  n2 := n1;
  Mathe.Minus1(n2);

  {calculate r,s with n-1=2^s*r} 
  r := n1;
  s := 0;
  while Mathe.istGerade(r) do
   begin
   r := Mathe.Quotient(r,'2');
   inc(s);
   end;
   while t>0 do
   begin
    {generate a in the range 2<=a<n-1, calculate y = a^r mod n}
    y := Mathe.Zufallszahl('2', n2);
    y := Mathe.PotenzModulo(y,r,n);
    {if y<>1 and y<>n-1 do}
    if (y<>'1') and (y<>n1)
     then
     begin
     j := 1;
     while (j <= s-1) and (y<>n1) do
     begin
     y := Mathe.ProduktModulo(y,y,n);
     {if y=1 then composite} 
     if y='1'
      then exit;
     inc(j);
     end;
      {if y<>n1 then composite} 
      if y<>n1 then exit;
    end;
    dec(t);
  end;
  {probably prime now}
  result := true;
end;
end;
end;

hoika 8. Okt 2009 18:06

Re: probedivision -abbruch von schleife funktioniert nicht
 
Hallo,


Breakpoint auf
if mathe.modulo(n,primes[i])='0'

und nachsehen, warum nicht 0 rauskommt.


Heiko

qwertz543221 8. Okt 2009 18:10

Re: probedivision -abbruch von schleife funktioniert nicht
 
passiert ist gar nichts, noch nicht einmal der breakpunkt hat gestoppt.

es muss null, rauskommen, denn die prüfmessage wird angezeigt.(habe ich nach der abfrage eingebaut)

stahli 8. Okt 2009 18:15

Re: probedivision -abbruch von schleife funktioniert nicht
 
Oha! ... sieht das in Deiner IDE auch so aus?

Rücke mal den Quelltext ordentlich zurecht, dann liest sich das schon mal leichter (und Fehler finden sich wie von selbst ;-) ).
Welche Schleife und Bedingung meinst Du genau?

Wenn die Bedingung erfüllt ist, wird der Compiler das auch berücksichtigen.
Also wird "break" mit Sicherheit gar nicht erreicht.

Stahli


[EDIT]
Wenn der Breakpoint nicht erreicht wird, ist sicher schon Mathe.istGerade(n) erfüllt und Exit ausgeführt...
Also Breakpoint auf die erste Zeile der Prozedur und sehen, was passiert.

qwertz543221 8. Okt 2009 18:20

Re: probedivision -abbruch von schleife funktioniert nicht
 
ich habe den break point auf den funktionskopf der inneren funktion gelegt, abbruch passierte trotzdem keiner - entschuldigt dei formatierung, ich stell es es gleich neu ein.

DeddyH 8. Okt 2009 18:22

Re: probedivision -abbruch von schleife funktioniert nicht
 
Du sollst den Breakpoint auf
Zitat:

Delphi-Quellcode:
if probedivision(n)=true

setzen und durchsteppen. Und lass mal die Abfrage auf true weg, die ist nicht nur unnötig, sondern kann auch falsche Ergebnisse liefern.

DP-Maintenance 8. Okt 2009 19:09

DP-Maintenance
 
Dieses Thema wurde von "Matze" von "Programmieren allgemein" nach "Object-Pascal / Delphi-Language" verschoben.
Delphi-ähnliches Thema. *g*

qwertz543221 8. Okt 2009 19:24

Re: probedivision -abbruch von schleife funktioniert nicht
 
ok habe ich gemacht - es funktioniert soweit. Danke

noch eine weitere frage:
ist es überhaupt günstig, erst probedivision bei der vordefinierten liste zu machen, bevor andere primzahltests angesetzt werden? - wenn nein, was wäre eine effizientere vorgehensweise?

gammatester 8. Okt 2009 21:11

Re: probedivision -abbruch von schleife funktioniert nicht
 
Zitat:

Zitat von qwertz543221
ok habe ich gemacht - es funktioniert soweit. Danke

noch eine weitere frage:
ist es überhaupt günstig, erst probedivision bei der vordefinierten liste zu machen, bevor andere primzahltests angesetzt werden? - wenn nein, was wäre eine effizientere vorgehensweise?

Ich konnte mir eigentlich nicht vorstellen, daß man meine Miller-Rabin-Funktion so versauen kann. :wall:

Selbstverständlich hat die Probedivision in der Funktion nichts zu suchen, wenn man nicht wieder alle Bedeutungen auf den Kopf stellen will. Wenn Du Deine Funktion IsProbablePrime oder ähnlich genannt hättest, wäre es OK. Im übrigen würde man die Anzahl der Probedivisionen abhängig von Bitlänge von n machen.

Außerdem: Da Du aber, wie üblich offensichtlich völlig ahnungslos, einfach Code zusammenwürfelst, hast Du übersehen, daß Deine Primzahlliste selbstverständlich bei 3 anfangen (bzw die 2 nicht enthalten) sollte, da Du direkt vor der ersten Probedivision durch 2 ausgeschlossen hast, daß n gerade ist. Oder ist Dir nicht klar, daß "n mod 2 = 0" dasselbe bedeutet wie "n ist gerade"?


Alle Zeitangaben in WEZ +1. Es ist jetzt 00:02 Uhr.

Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz