Faktorisierung

[Antigo]

Hi,
Ich habe ein kleines Programm zu Faktorisierung von beliebigen Zahlen geschrieben.

Faktorisierung bedeutet, dass man eine Zahl als ein Produkt von Primzahlen darstellt. Diese Primzahlfaktoren werden aufsteigend asugegeben. Dadurch ist diese Darstellung für jede Zahl eindeutig.

Beispiel:
Zahl 6 ist 2 * 3. DIe Zahlen 2 und 3 sind hier die Primzahlen aus denen sich die Zahl 6 zusammensetzt.

oder
Die Zahl 2145 ist 3 * 5 * 11 * 13.

Kommt ein Faktor zweimal vor, wird er als Exponent dargestellt. 8 ist beispielsweise 2 * 2 * 2. Es wird jedoch als 2^3 ausgegeben.


Alles weitere ist angehangen



edit:
~~~~~~~~~~~~~~~~~~~~~~Update~~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~
Dank der Hilfe von vielen DP Mitgliedern, konnte ich das Programm um einiges schneller machen. Zum direkten Vergleich lasse ich das alte Programm auch angehangen.

Was jetzt noch fehlt:
Zum einen ein Statusbalken, der anzeigt, wieweit man in der Berechnung berets fortgeschritten ist. Das hat auf Anhieb nicht hingehauen so wie ich das wollte. Also muss ich mir nochmal Gedanken machen.
Zum anderen gibt es noch zwei drei Bugs die ich noch beheben muss. Die Zahlen 6,9,15,21 werden fälschlicherweise als Primzahl angegeben. Jensseits der 20er Marke scheint jedoch alles zu funktionieren. Notfall werde ich diese Zahlen als Sonderfälle behandeln.

[Antigo]

Also im Prizip gehe Ich so vor:

Nehme die Zahl, teile Sie durch i.
Wenn i Teiler von Zahl und eine Primzahl, dann merke dir dass.
Wenn nicht, dann erhöhe i um 1.
Fange von vorne an.


Das ist grob gesagt mein Algorithmus.

Bei der Zahl 452 würde er also so vorgehen:

Teile 452 durch 2 => 2 ist Teiler. => 2 Ist Prim => 452 div 2 = 226.
Teile 226 durch 2 => 2 ist Teiler => 2 Ist Prim =>226 div 2 = 113.
Teile 113 durch 2 => 2 ist kein Teiler.
Teile 113 durch 3 =>3 ist kein Teiler.
Teile 113 durch 4 => 4 ist kein Teiler.
Teile 113 durch 5 => 5 ist kein Teiler.
...
Teile 113 durch 113 => 113 ist Teiler => 113 ist Prim => 113 div 113 => 1 => Algorithms fertig!


Das heisst ich musste bis zur 113 Zahlen ausprobieren. DIe Wurzel von 425 ist aber ~21. Daher reicht es nicht bis zur Wurzel einer Zahl zu gehen.


Ich hoffe jetzt ist es klarer worauf ich hinaus will

[negaH]

Du testet nur alle Primzahlen bis Quadratwurzel von N, nicht bis zur Hälte von N.

Mein DECMath hast du ja schon, dann teste mal mein TSmallPrimeSieve in Unit Prime.pas. Mit diesem Sieb berechnet man sequientiell alle Primzahlen bis 2^32 in ca. 13 Sekunden (P4 1.5GHz)

Nach jedem Entfernen eines gefundenen Faktors solltest du N noch mit Prime.IsPrime(N) oder NIsProbablePrime(N) überprüfen ob es eine Primzahl ist. Wenn ja kannst du deine Fatorization schon vorzeitig beenden und N ist dann der größte übrig bleibende Primfaktor.

Etwa so:

Delphi-Quellcode:

procedure TrialDivFactorize(N: IInteger);
var
  F: Cardinal;
begin
  repeat
    F := NSmallFactor(N);
    if F > 1 then
    begin
      NDiv(N, F);
      Write(F, ', ');
    end else 
    begin
      if F = 1 then
        if NIsProbablePrime(N) then Write(NStr(N))
          else Write(NStr(N), ' composite');
      Break;
    end;
  until False;
  WriteLn;
end;

Deine Methode kannst du beschleunigen:

1.) den Fall Faktor ist 2 erschlagen wird am Anfang separat
2.) danach mit Faktor 3 weitermachen und diesen immer um +2 inkrementieren, nicht +1 !!

Das würde deine Verfahren doppelt schneller machen.

3.) ein TBit Array wird benötigt wobei jedes Bit die Zahlen 3,5,7,9,11,13,15,17 usw. bestimt. Nachdem die 3 als Faktor fertig ist wird nun in diesem Array alle Bits mit Index 3,6,9,12,15 also 3*x herausgestrichen. Alle diese Faktoren die in diesem TBIt Array markiert wurden sind KEINE Primzahlen und müssen auch nicht mehr getestet werden. Die Faktoren 9 und 15 würden also nicht mehr getestet werden. In deinem TBit Array bleibt am Ende nur die Zahlen auf FALSE die Primzahlen sind.
Du testest jetzt bis Wurzel(N).

Dies macht das Verfahren nochmals wesentlich schneller und man stösst defakto an die Grenzen dieses Verfahrens. Entweder weil die Laufzeit immer größer wird (quadratisch) oder weil der Speicherbedarf für unser TBit Array zu groß wird.


Gruß Hagen

[negaH]

Dein ProgressBar Problem kannst du ebenfalls sehr sauber lösen.

Du testest insgesamt exakt Sqrt(N) Faktoren. Max der ProgressBar auf Sqrt(N) setzen und .Position := AktuellerFaktor;

[edit]
Falls Sqrt(N)/2-1 größer sein sollte als ProgressBar.Max fassen kann (glaube ist ein SmallInt) dann eben so

ProgressBar.Max := 100;
ProgressBar.Position := Round(Faktor / Sqrt(N)) * 100)
[/edit]

Gruß Hagen

[Antigo]

Zitat:

Nach jedem Entfernen eines gefundenen Faktors solltest du N noch mit Prime.IsPrime(N) oder NIsProbablePrime(N) überprüfen ob es eine Primzahl ist. Wenn ja kannst du deine Fatorization schon vorzeitig beenden und N ist dann der größte übrig bleibende Primfaktor.

Ja gute Idee, danke

Zitat:

Du testet nur alle Primzahlen bis Quadratwurzel von N, nicht bis zur Hälte von N.

Bei meinem jetzigen Verfahren würde das aber nicht funktionieren. Ich hab ja oben aufgezeigt, dass der letzte Primzahlfaktor größer als die Wurzel der zu faktorisierenden Zahl ist.
Wenn ich aber die Zahl (N wie du sie nennst) auf Prim prüfe. Könnte es sein, dass es reicht bis zur Wurzel zu gehen. Da muss ich mal drüber nachdenken.


Das mit dem Bitarray muss ich mir auch mal überlegen, das spart sicherlich auch extrem Zeit ein. Die Schritte mit denen ich vorgehe auf 2 zu erhöhrnen (i+2) hatte ich mir auch schon überlegt. Werde ich so schell wie möglich implementieren.

Zitat:

Dein ProgressBar Problem kannst du ebenfalls sehr sauber lösen.

Du testest insgesamt exakt Sqrt(N) Faktoren. Max der ProgressBar auf Sqrt(N) setzen und .Position := AktuellerFaktor;

[edit]
Falls Sqrt(N)/2-1 größer sein sollte als ProgressBar.Max fassen kann (glaube ist ein SmallInt) dann eben so

ProgressBar.Max := 100;
ProgressBar.Position := Round(Faktor / Sqrt(N)) * 100)
[/edit]

JO so ähnlich hatte ich mir das auch überlegt. Da die Rechenzeit aber nicht linear ansteigt, kann man keinen gleichmässigen Balken ausgeben. Aber wie gesagt wollte ich das auch nur zur Orientierung angeben, und dafür reicht das.



Vielen Dank für deine Hilfe

[Jelly]

Zitat von jfheins:

Zitat von Antigo:

Ich bin noch am Überlegen ob ich dass nicht abfangen sollte und die Zahl an sich erstmal überprüfen sollte, ob sie Prim ist...

Machs liber nicht, denn ein zuverlässiger Primzahltest geht *zufällig* alle Zahlen durch, bis zur Hälfte

Nö... Bis zur Quadratwurzel reicht. Denn wär die Zahl grösser als die Quadratwurzel, so müsste der 2. Faktor auf jeden Fall kleiner sein als die Quadratwurzel, weil ja sonst das Produkt definitiv grösser wird als die Ursprungszahl. Und die Zahl kleiner als die Quadratwurzel hast Du ja schon in einem Anlauf vorher getestet.

[Khabarakh]

Zitat von Antigo:

Ich hab ja oben aufgezeigt, dass der letzte Primzahlfaktor größer als die Wurzel der zu faktorisierenden Zahl ist.

Und ? Sobald i größer als die Quadratwurzel ist, muss der Teilungsrest eine Primzahl, also der letzte Primzahlfaktor, sein.
Dein Beispiel von oben umgeschrieben:
Teile 452 durch 2 => 2 ist Teiler. => 2 Ist Prim => 452 div 2 = 226.
Teile 226 durch 2 => 2 ist Teiler => 2 Ist Prim =>226 div 2 = 113.
Teile 113 durch 2 => 2 ist kein Teiler.
Teile 113 durch 3 =>3 ist kein Teiler.
Teile 113 durch 5 => 5 ist kein Teiler.
Teile 113 durch 7 => 7 ist kein Teiler.
...
Teile 113 durch 21 => 21 ist kein Teiler => 113 ist prim und letzter Faktor

[Antigo]

jo Ich habs jetzt geschnallt. Danke für die Aufklärung

Ich hab jetzt folgendes angepasst:
Der Algorithmus ist jetzt aufgeteilt. Erst wird der Sonderfall Primzahl 2 überprüft. Danach gehts mit der 3 weiter und dann rechne ich immer 2 auf die Zahl drauf, so dass ich alle Graden Zahlen, die ja sowieso keine Primzahlen seien können, von vornerein umgehen kann.
Dann überprüfe ich jetzt jedesmal die neue Zahl, die aus der Zahl geteilt durch Primzahlfaktor entsteht, ob sie Prim ist. Dadurch spare ich mir auch eine riesige Menge Zahlen, die Ich überprüfen müsste.
Darüber hinaus gehe ich jetzt auch nur noch bis zur Wurzel der Zahl, da ich jetzt verstanden hab warum das funktioniert

Bisher hab ich das nur bei Methode 3 eingebaut. Jetzt muss ich noch Methode 2 anpassen und dann lade ich die neue Version hoch. Die alte lasse ich auch mal stehen, damit man den Geschwindigkeits Boost sehen kann


danke nochmal an alle

[Cöster]

Zitat von Antigo:

Teile 452 durch 2 => 2 ist Teiler. => 2 Ist Prim => 452 div 2 = 226.
Teile 226 durch 2 => 2 ist Teiler => 2 Ist Prim =>226 div 2 = 113.
Teile 113 durch 2 => 2 ist kein Teiler.
Teile 113 durch 3 =>3 ist kein Teiler.
Teile 113 durch 4 => 4 ist kein Teiler.
Teile 113 durch 5 => 5 ist kein Teiler.
...
Teile 113 durch 113 => 113 ist Teiler => 113 ist Prim => 113 div 113 => 1 => Algorithms fertig!

Ich sag's noch einmal:
Die Abfrage (ich hab sie oben mal fett gemacht), ob die Zahl eine Primzahl ist, kannst du dir auch sparen!
Sie ist nämlich IMMER eine Primzahl.
Wenn sie keine wäre, hätte sie ja einen Teiler, der (natürlich) kleiner ist als die Zahl. Du findest aber, sobald du einen Teiler findest, immer den kleinsten möglichen Teiler der Zahl. Also zuerst findest du den kleinsten möglichen Teiler von 452, dann von 226 und dann von 113. Das wäre bei jedem Beispiel so. Wenn dir mein Beweis nicht reicht oder ich ihn nicht gut genug erklärt hab, versuche mir ein Beispiel zu nennen, bei dem bei der Abfrage "ist Prim" der Wert False zurückgegeben wird! Du wirst keins finden.

[Antigo]

Sorry das ich dich übergangen hab. Du hast tatsächlich recht. Wenn Ich einen Teiler einer Zahl finde, kann sie kein Vielfaches einer anderen Zahl sein, denn wenn sie das wäre, hätte der Algorithmus schon vorher abgebrochen und diese Zahl als Teiler genommen. Demnach muss der kleinste Teiler der Zahl auch eine Primzahl. Genial
Vielen Dank für den Hinweis, da bin ich irgendwie nicht drauf gekommen.

Das heisst ich brauche den Primzahltest nur noch um die Zahl, die aus der Division der ursprünglichen Zahl durch ihren kleinsten Teiler entstanden ist, auf Prim zu überprüfen. SO kann ich dann verhindern das ich überflüssiger Weise nach einem Teiler einer Zahl suche, die Prim ist.

Danke nochmal

[Antigo]

SO ich hab mal eine neue Version hochgeladen. Ich denke mal der Geschwindigkeits Unterschied ist deutlich spürbar. Der Fehler das einige kleine Zahlen fälschlicherweise als Primzahlen erkannt werden (alle <30) ist mir bekannt. Alle weiteren Fehler bitte melden