Primfaktorzerlegung läuft viel zu langsam...

[fapsons]

Hallo Leute,

habe zur Primfaktorzerlegung hier einen Quelltext gefunden, den ich entsprechend abgeändert habe.
Er läuft allerdings, jedoch viel zu langsam, sodass bei größeren Werten das Programm abstürzt.
Könnt ihr mir da weiterhelfen, was ich evtl. verbessern kann?

Danke
-fapsons-

Delphi-Quellcode:

function Is_Prime(x: int64): Boolean;
var i :Integer;
begin
  result := true;
  for i := 2 to x-1 do
    if x mod i = 0 then result := false
end;



function Get_Prime_Factors(x: Int64): TIntArray;
var i, j, k :Integer;
    r       :TIntArray;
begin
  r := TintArray.Create;
  k := 1;
  for i := 2 to x do
  begin
       j := 0;
       while x mod i = 0 do
       begin
          x := x div i;
          inc(j)
       end;

       if j = 1 then
       begin
         r.ints[k] := i;
         k := k + 1;
       end;
  end;
  result := r;
end;

[mkinzler]

Delphi-Quellcode:

if x mod i = 0 then 
begin
    result := false;
    exit;
end;

[Chris P]

Hi,

also erstens brauchst du nur ungerade Teiler zu testen und zweitens schickt es wenn die for-Schleife
nur bis Wurzel aus x läuft, denn x = Wurzel(x) * Wurzel(x).

[MatWur]

PFZ ist eine komplizierte Sache, wenn sie für grosse Zahlen durchgeführt wird. Die traditionelle Methode des durchtesten wird dabei viel zu langsam. Als erste Optimierung würde ich vorschlagen in deiner Funktion Is_Prime die Testdivisionen auf die ungeraden Zahlen zu beschränken und nur bis SqRt (x) zu testen. Die Testdivisionen sollten später sogar nur die bisher ermittelten Primzahlen umfassen, um nochmal weniger Testdivisionen zu erhalten.
Falls es dir nur um die PFZ einiger bestimmter Zahlen geht empfehle ich dir folgende Seite, sie hat ein Java Applet das sehr gut und schnell mit modernen Methoden faktorisiert:
http://www.alpertron.com.ar/ECM.HTM

Ausserdem empfehle ich dir, dich mit dem "kleinen Fermat'schen Satz" zu befassen (Mathematik), der ist für die Bestimmung von Primzahlen bei grossen Zahlen elementar.

mfg

Matthias

[fapsons]

Vielen Dank schon mal für eure Hilfe...

Hab es noch nicht versucht mit deinen Verbesserungsvorschlägen MatWur, aber wie setze ich das denn um, dass meine For-Schleife nur ungerade Werte annimmt?

Wahrscheinlich gibt es für mein Problem auch eine viel einfachere Lösung und zwar besteht mein Wert, der zerlegt werden soll aus Faktoren, die jeweils Primzahlen sind.

Also X := 3 * 5 * 7 * 11 oder ähnlich
der höchste Faktor meines Wertes kann max. 31 sein.

Es müsste nur ausgegeben werden, welche einzelnen Faktoren mein Produkt enthält...

Hier nochmal der aktuelle Code mit der ersten Änderung:

Delphi-Quellcode:

function Is_Prime(x: int64): Boolean;
var i :Integer;
begin
  result := true;
  for i := 2 to x-1 do
    if x mod i = 0 then result := false
end;



function Get_Prime_Factors(x: Int64): TIntArray;
var i, j, k :Integer;
    r       :TIntArray;
begin
  r := TintArray.Create;
  k := 1;
  for i := 2 to x do
  begin
       j := 0;
       if x mod i = 0 then
       begin
          x := x div i;
          inc(j);
       end;

       if j = 1 then
       begin
         r.ints[k] := i;
         k := k + 1;
       end;
  end;
  result := r;
end;

[Chris P]

So habe ich das gelöst:

Delphi-Quellcode:

function IsPrime(const Value: Cardinal): Boolean;
var
   t: Cardinal;
begin
   if (Value = 2) then
   begin
      Result := TRUE;
      Exit;
   end;

   if (Value < 2) or (Value mod 2 = 0) then
   begin
      Result := FALSE;
      Exit;
   end;

   t := 3;
   while (t * t <= Value) do
   begin
      if (Value mod t = 0) then
      begin
         Result := FALSE;
         Exit;
      end
      else
         t := t + 2;
   end;
   Result := TRUE;
end;
// -----------------------------------------------------------------------------
function Factorize(const V: Cardinal): TFactors;
var
   t, x, Count: Cardinal;
begin
   t := 2;
   x := V;

   Count := 0;
   SetLength(Result, 0);

   while (t <= x) do
   begin
      if (x mod t = 0) then
      begin
         Count := Count + 1;
         SetLength(Result, Count);
         Result[Count - 1] := t;
         x := x div t;
         t := 2;
      end
      else
         t := t + 1;
   end;
end;

[MatWur]

ich wollte gerade anfangen, aber Chris P hat schon eine brauchbare Lösung abgeliefert.
Zuerst wird getestet ob die Zahl gleich 2 ist, wenn ja prim und raus.
Dann wird getestet ob es 0,1 oder eine gerade Zahl>2 ist, wenn ja nicht prim und raus.
Dann werden beginnend mit t=3 die ungeraden Zahlen abgetestet und falls ein Faktor gefunden wird -> nicht prim und raus.

Wenn bei deinen Zahlen tatsächlich nur Primzahlen bis 31 vorkommen kannst du den Schritt
while (t * t <= Value) do
ersetzen durch
while (t <= 31) do, damit kannst du bei grossen Zahlen noch einmal Zeit sparen.

Das er den Typ Cardinal statt wie du den Typ Int64 genommen hat sollte hoffentlich kein Problem sein. Weenn doch, bitte rückfragen.

mfg

Matthias

Edit: PS

eine for Schleife für ungerade Zahlen erhälst du folgendermaßen:

Delphi-Quellcode:

for i := 0 to 19 do begin
  n := 2*i+1;
  {rechnen mit n} end;

in dieser Schleife hat n nacheinander die Werte 1, 3, 5, ..., 37, 39

[Chris P]

@MatWur: Danke für die ergänzende Erklärung :thumb:

[Nikolas]

Ich würde diese Schreibweise bevorzugen:

Delphi-Quellcode:

for i:=1 to floor(sqrt(x)) do
 if (x mod (2*i+1)) = 0 then 
 begin 
   result:= false; 
   exit; 
 end;

Macht eigentlich nichts anderes, müsste aber schneller sein, da nicht bei jedem Durchlauf t*t mit x verglichen werden muss, sondern die maximale Anzahl der Durchläufe schon von Anfang an feststeht.
Und jemand mit einem etwas geschulten mathematischen Blick erkennst den Ausdruck 2*i+1 sofort als Reihe der ungeraden Zahlen.
Ich glaube schon gelesen zu haben, dass der Compiler aufsteigende Schleifen auch gerne durch downtoschleifen ersetzt, da anscheinend das prüfen auf Variable=0 einfacher ist als Variable=SonstiergWert. Ist hier zwar nicht direkt der Fall, da im niedrigsten Fall noch auf i=1 getestet wird, aber wär mal einen Gedanken wert, da die aufsteigende Schleife wahrscheinlich früher abbricht, als die absteigende.

[Chris P]

Das mag ja sein nur du rufst in jedem Schleifendurchlauf floor(...) und sqrt(...) auf.
Außerdem ist sqrt ungenau da es mit Fließkommazahlen arbeitet.

Das hat man bei bei meiner Lösung nicht.

[Nikolas]

Es würde mich wundern, wenn das der Fall wäre. Ich bin davon ausgegangen, dass der Compiler sieht, dass x innerhalb der Schleife nicht geändert wird und daher das floor(Sqrt(x)) nur einmal berechnet und sich merkt.
Inwiefern soll sqrt ungenau sein? Um ganz sicher zu gehen könnte man floor noch mit ceil austauschen, dann ist man auf der sicheren Seite, so lange sqrt keinen Fehler macht der größer als 1 ist :)
Und für Zahlen, bei denen ein so großer Fehler auftreten kann, sollte diese Art der Überprüfung auch nicht angewendet werden.

[Chris P]

Ich bin mir nicht sicher ob der Compiler das weiß, ob x innerhalb der Schleife verändert wird.
Ich denke, es wird bei jedem Durchlauf erneut berechnet.

Auf jeden Fall sind meine und deine Variante möglich.
Nur ich persönlich versuche Fließkommazahlen zu vermeiden wo es geht.

[fapsons]

Super ChrisP, bin begeistert. Deine Variante läuft einwandfrei.
Vielen Dank!!!

Jetzt hätte man nur noch das selber schaffen müssen...;) Aber ich bin leider noch ein blutiger Anfänger...*G*

[fapsons]

Ein Problem habe ich noch, könnte allerdings zu nem größeren werden...;)

Was ist, wenn mein x ein int64 sein muss.
Dann kann ich doch keine For-Schleife benutzen, oder?

Gibt es dafür auch eine Lösung?

[Chris P]

Freut mich!

Wenn du meine Variante einigermaßen nachvollziehen kannst, kannst du dich ja
mal an den Fermat versuchen. Das wäre dann die nächste Verbesserung.

P.S: Mit Int64 sollte es ebenfalls ohne Probleme gehen. Ersetze einfach Cardinal durch Int64.

[fapsons]

Die Funktion läuft soweit bis zum Wert 3234846615.
Mit dem letzten Wert, den ich benötige, läuft es leider nicht mehr...:(
100280245065

Ne Idee, woran es liegt?

Delphi-Quellcode:

 primzahlen := Tintarray.Create;
 primzahlen := Factorize(3234846615);


function Factorize(const V: int64): TIntArray;
var
   t, x, Count: Cardinal;
begin
   result := TIntArray.Create;
   t := 2;
   x := V;

   Count := 0;

   while (t <= x) do
   begin
      if (x mod t = 0) then
      begin
         Count := Count + 1;
         Result.ints[Count] := t;
         x := x div t;
         t := 2;
      end
      else
         t := t + 1;
   end;
end;

[Chris P]

Probier mal:

Delphi-Quellcode:

var
   t, x, Count: Int64;

[fapsons]

Super ChrisP,

bist mein persönlicher Held des Tage...;)! Tausenddank!

[Chris P]

Kein Problem :wink:

Freut mich wenn ich dir helfen konnte ...

Gruß
Chris P

[MatWur]

also sortieren^^

@ Chris P: kein Problem :mrgreen:

@ all: der Compiler erkennt den Ausdruck floor(sqrt(x)) als Konstante und berechnet ihn nur einmal. Innerhalb von for-Schleifen sind *immer* Anfangs- und Endwert der Schleife vor Schleifenbeginn bekannt bzw. wurden (1 mal) berechnet.

@ fapsons: es gibt mehrere Lösungsmöglichkeiten für dein problem mit der Schleife.
1.) du kannst theoretisch die Schleife durch eine 'while' oder eine 'repeat' Schleife ersetzen (ist aber kompliziert)
2.) besser du schreibst deine Schleife mit einem normalen Integer und übergibst dessen Wert innerhalb der Schleife einfach an eine Variable vom Typ Int64. Bsp:

Delphi-Quellcode:

var
  i: integer;
  i_gross: int64;
begin
  for i := 0 to 10 do begin
    i_gross := i;
    {rechnen mit i_gross} end;
end;

mfg

Matthias

[Chris P]

@MatWur:

Erkennt der Compiler also beim Kompilieren das x nicht verändert wird!?
Kann man das irgendwie nachlesen?

[MatWur]

ja, das erkennt der Compiler. Auszug aus der Delphi Language Reference:

Zitat:

Zitat von Delphi Language Reference

For purposes of controlling execution of the loop, the expressions initialValue and finalValue are evaluated only once, before the loop begins.

danach folgt noch die Erklärung, das dies der wesentlichste Unterschied zur Repeat- und While-Schleife ist.

mfg

Matthias

[Chris P]

@MatWur:

Toll! Jetzt habe ich auch wieder was dazugelernt!

Danke... :hi:

[xZise]

Außerdem wäre es möglich gewesen den Wert einmal in eine Variable zu schreiben ;)

PS: Irgendwie komme ich mit der Erklärung nicht da, weil eine solche Schleife funzt:

Delphi-Quellcode:

j := 2;
for i := 0 to j do
  j := j + 1;

Und er würde da nie rausspringen (außer i ist zu groß ;))

[MatWur]

die angegebene Schleife funktioniert zwar, aber die Schleife wird exakt 3 mal durchlaufen, für i=0, i=1 und i=2. Der Endwert der Schleife (j=2) wird innerhalb der Schleife *nicht* verändert obwohl die Variable geändert wird. Aber der geänderte Variablenwert wird nicht als neuer Endwert der Schleife eingesetzt.

Zitat:

Zitat von xZise

Außerdem wäre es möglich gewesen den Wert einmal in eine Variable zu schreiben ;)

genau das wird getan :zwinker: in eine eigene Variable für den Endwert die du dann nicht mehr siehst oder ändern kannst.

mfg

Matthias

[xZise]

Selstam.... es ging mal ... naja vielleicht täushce ich mich xD :angel2:

[fLaSh11]

Das hier ist ein sauschneller Code für eine Primfaktorzerlegung:
(ist halt Konsole, aber mit sehr wenig Arbeitsaufwand umzuwandeln...)

Delphi-Quellcode:

label
  lbl1,lbl2,lbl3,lbl4,lbl5,lbl6,lbl7,lbl8,lbl9;

var
  a,b: Integer;
  c: Extended;

begin
goto lbl2;

lbl1:
writeln('2');
a:=a div 2;
if a=1 then goto lbl9;

lbl2:
if frac(a/2)=0 then goto lbl1;
b:=3;

lbl3:
c:=sqrt(a)+1;

lbl4:
if b>=c then goto lbl8;
if frac(a/b)=0 then goto lbl6;

lbl5:
b:=b+2;
goto lbl4;

lbl6:
if a/b*b-a=0 then goto lbl7;
goto lbl5;

lbl7:
writeln(IntToStr(b));
a:=a div b;
goto lbl3;

lbl8:
writeln(IntToStr(a));

lbl9:
readln;

(ist unübersichtlich aber schnell)

//Edit1: Ich hab vergessen zu erwähnen, dass a die zu zerlegende Zahl ist!
//Edit2: Weiß jemand, ob ich das veröffentlichen darf, denn es war im Handbuch meines GTRs in Basic abgedruckt, habs eig. nur in Delphi verwandelt :mrgreen:

[Yamato]

Das kann man sogar noch verbessern: alle Primzahlen außer 2 und 3 sind von der Form 6n+-1 (dadurch werden alle Vielfachen von 3 eliminiert).

Eine kurze Erklärung einiger besserer Verfahren sowie ein Java-Applet gibt's hier:
http://www2.informatik.hu-berlin.de/~schoenbe/

Wer Lust auf Theorie hat, kann das ja mal in Delphi umsetzen.

[alzaimar]

Zitat:

Zitat von fLaSh11

Das hier ist ein sauschneller Code für eine Primfaktorzerlegung:

Na dann googel mal nach dem 'Sieve of Atkins'. Das findet alle Primzahlen bis 2^32 in ca. 1 Sekunde

Zitat:

Zitat von fLaSh11

//Edit2: Weiß jemand, ob ich das veröffentlichen darf, denn es war im Handbuch meines GTRs in Basic abgedruckt, habs eig. nur in Delphi verwandelt :mrgreen:

Ja, es ist banal und wird Keinen interessieren.

[marabu]

Hallo alzaimar,

Atkins ist der Halbgott mit der Gitarre, der Mathematiker heißt Atkin *grin*

Es gibt ein ausgefeiltes Sieve of Eratosthenes, welches für den 32-bit Zahlenraum eine gute bzw. bessere Wahl ist. Das Sieve of Atkin trumpft jenseits dieser Grenze auf, wenn ich richtig gelesen habe.

Noch ein Link: High Speed Factoring

Gute Nacht