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.

[jmit]

Hallo,

nettes Programm. Mach weiter so.

Ist das gewollt, das der Abbruchbutton keine Funktion hat.

Gruß Jörg

[Flare]

Also bei mir funktioniert der Abbruchbutton. Allerdings merkt man das ja erst bei zu großen Zahlen.
Und ein was: Du hscreibst, dass man beliebig große Zahlen nehmen kann, aber zum Beispiel für die Zahl 12345678901234567890 braucht er 0 (Milli)Sekunden, also sehr schnell. Jedoch für die Zahl 123456789012345678901 braucht er sehr sehr lange (nach 10 Sekunden über oben genannten Button abgebrochen). Da stimmt irgendetwas nicht würde ich sagen...


Flare

[Chewie]

@Flare: Klar kann das sein.

Die Quersumme von 12345678901234567890 ist 90, also durch 3 teilbar. Was das heißt, lernt man nicht erst in einer Vorlesung über Modulo-Arithmetik, sondern bereits in der Grundschule ;)

[Antigo]

Danke für das Feedback.

Es ist tatsächlich so, dass eine Zahl in Nullzeit berechnet werden kann. Und diese Zahl+1 ewigkeiten braucht. Das hängt einfach davon ab durch was sie teilbar ist. Ist sie direkt durch zwei teilbar. Ist die Zahl mit der man weiterrechnet nur noch halb so groß. Ist sie erst durch eine 4 oder 5 Stellige Zahl teilbar, muss diese erstmal gefunden werden ;)

Am längsten dauern übrigens Primzahlen, da das Programm solange Teiler sucht, bis der Teiler den er ausprobiert größer ist als die Hälfte der Zahl. Dann bricht er ab und deklariert die Zahl als Prim. Ich bin noch am Überlegen ob ich dass nicht abfangen sollte und die Zahl an sich erstmal überprüfen sollte, ob sie Prim ist...


Noch kurz zum Thema beliebig große Zahlen. Damit ist nur gemeint, das das Programm mit diesen zahlen "umgehen" kann. Das heisst nach endlich viel Zeit würde das Programm zu einem Ergebnis kommen. WIelange das ist, ist natürlich eine andere Frage ;)

edit: Ich sehe grade du hast die Zahl nicht nur um eins erhöht, sondern eine eins drangehangen, was den Wert der Zahl vertausendfacht und dadurch natürlich auch die Rechenzeit explodieren lässt.


Ich gucke mal ob ich so etwas wie einen Fortschrittsbalken bauen kann, der sagt welche Zahlen er schon probiert hat, und wieviele noch nicht. Dazu noch eine Zwischenspeicherfunktion und mann kann sich auch an größere Zahlen wagen ^^

[jfheins]

Zitat:

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 Quadratwurzel ... das wäre dann ein wenig doppelt gemoppelt ;)
(Natürlich könnte man auch nur jede ungerade probieren, aber ... ihr wisst, was gemint ist ;) )

Zitat:

sondern eine eins drangehangen, was den Wert der Zahl vertausendfacht und dadurch natürlich auch die Rechenzeit explodieren lässt.

Nana, bleib' mal auf Boden ... hinten eine Stelle mehr sollte (im Dezimalsystem) die Zahl höchstens ver-10-fachen, aber nicht 1000 ;)

Das mit der Hälfte weis ich aber doch eigentlich :wall:
Ich habe mich halt am Autor des Zitats orientiert :stupid:

[Antigo]

äh jo :oops:
da ist es wohl mit mir durchgegangen. Aber mir fällt grad ein wie ich dadrauf gekommen bin. Wenn man an eine Zahl eine STelle dranhängt ist diese Zahl 1000% der alten Zahl. Das ist aber trotzdem "Nur" der Faktor 10 um den die Zahl größer wird. Trotzdem, je größer die Zahl an sich schon ist, desto extremer steigt die Mehr Belastung des Programmes wenn man eine STelle dranhängt. ISt logisch....

[marcelwhip]

bei delphi gibts doch diesen fortschrittsbalken
mit dem befehl "name.stepit" kannst du den balken um einen festgelegten wert wachsen lassen.
allerdings stell ich mir die realisierung problematisch vor, da wenn ich das programm richtig verstanden habe, die zeit sich nicht linear verhält, denn je kleiner die zahl, desto kürzer die berechnungsdauer..
oder bin ich aufm holzweg?

[fwsp]

niemand hat gesagt, dass der fortschritt linear visualisiert werden muss.
:???:

[marcelwhip]

schon gut, aber wen nervt das nicht, wenn bei der installation von programmen der balken ne halbe stunde bei 19% ist, und dann in 3 minuten auf hundert geht?!
und unsere uhren, jedenfalls meine^^ geht ziemlich linear, jedenfalls hoff ich das

[Antigo]

Also man kann mit Sicherheit keinen vernünftigen Statusbalken bauen, der gleichmässig von 0 bis 100% geht. Dafür müsste man vorher schon wissen, wieviele Teiler die Zahl hat und welche das sind ^^

Aber zumindest kann man angeben wieviele Zahlen schon getestet wurden und wieviele noch übrig sind. So das man ungefähr abschätzen kann wieweit man in der Berechnung ist. DIe Frage ist nur inwiefern das auf die Performance schlägt wenn man den Status der Berechnung ständig ausgeben lässt... Müsste man mal ausprobieren.

[Chewie]

Wenn man bei jedem Schritt den Balken aktualisiert, dann ja, das würde es lange verzögern.
Aber wenn mans bei jedem 100. oder so macht macht es wenig aus.

[Khabarakh]

Zitat:

Zitat von Antigo

Am längsten dauern übrigens Primzahlen, da das Programm solange Teiler sucht, bis der Teiler den er ausprobiert größer ist als die Hälfte der Zahl.

Zitat:

Zitat von jfheins

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

Was habt ihr denn mit eurer Hälfte :stupid: ? Ein Test bis zur Quadratwurzel reicht vollkommen.

[Cöster]

Zitat:

Zitat von Antigo

Am längsten dauern übrigens Primzahlen, da das Programm solange Teiler sucht, bis der Teiler den er ausprobiert größer ist als die Hälfte der Zahl.

Es reicht doch, wenn du so lange ausprobierst, bis der Teiler größer ist als die Wurzel der Zahl.

Beispiel:
Die Zahl lautet 53, Wurzel ist also zwischen 7 und 8. Du versuchst einfach 2, 3, 5, 7 (du solltest die unteren Primzahlen in einem Array speichern, damit du Zahlen wie 4 oder 6 gar nicht erst ausprobieren musst), die nächste Zahl wäre 11, liegt also über der Wurzel und du brauchst sie gar nicht mehr auszuprobieren, da der andere Teiler dann ja kleiner als die Wurzel wäre, aber die hast du ja schon alle ausprobiert.

Außerdem solltest du rekursiv rechnen (vielleicht machst du das ja auch schon). Dann müsstest du bei z.B. 100 nur 6 mal probieren:
100/2 -> 50
50/2 -> 25
25/2 -> geht nicht
25/3 -> geht nicht
25/5 -> 5 //jetzt nicht wieder die Zahlen kleiner als 5 ausprobieren, die hast du ja schon alle getestet
5/5 -> 1 fertig

Wenn du nach 100/2 allerdings weiterprobieren würdest mit 100/3, müsstest du wirklich bis 50 durchprobieren. Das bedeutete ein Vielfaches des Rechenaufwandes. Wie soll das dann erst bei größeren Zahlen sein?

[Antigo]

Also beim Primzahltest ist es klar das ich nur bis zur Wurzel gehen muss. Hier gehe ich ja so vor, das ich die Zahl durch alle Zahlen teile (natürlich nur wenn die Zahl keine 0,2,4,6,8 oder 5 am Ende hat; und eben auch nur bis zur Wurzel der Zahl) und gucke ob ein Rest übig ist. Ist bei einer einzigen Division kein Rest übrig (zahl mod i =0) ist die Zahl keine Primzahl.

Bei der Faktorisierung ist das allerdings anders. Hier muss ich bis zur Hälfte durchgehen.
Ich gehe ja folgendermassen vor (Methode 2/Methode 3), dass ich die Zahl durch alle Zahlen teile und nach einem ganzzahligen Teiler suche (wiederum zahl mod i = 0). Habe ich einen gefunden, überprüfe ich ob dieser Teiler auch eine Primzahl ist, wenn nicht, dann gehts weiter mit dem nächsten Teiler den ich finde. Ich kann hier erst sicher sein, dass ich keinen ganzzahligen Teiler der Zahl finde, wenn ich bis zur Hälfte der Zahl alle Zahlen die diese teilen auf Prim überprüft habe. Wenn ich hier schon nach der Wurzel der Zahl aufhöre, sind plötzlich alle Zahlen prim ;)


Zum rekursiven. Ich habe es so programmiert wie du es geschrieben hast. Allerdings hat das bei mir nichts mit rekursiv zu tun ;) Ich gehe einfach eine Schleife durch, also iterativ (so heisst das gegenteil glaub ich ^^)

[Khabarakh]

Zitat:

Zitat von Antigo

Bei der Faktorisierung ist das allerdings anders. Hier muss ich bis zur Hälfte durchgehen.
Ich gehe ja folgendermassen vor (Methode 2/Methode 3), dass ich die Zahl durch alle Zahlen teile und nach einem ganzzahligen Teiler suche (wiederum zahl mod i = 0). Habe ich einen gefunden, überprüfe ich ob dieser Teiler auch eine Primzahl ist, [...]

Wozu denn das :shock: ? Wenn du den zu testenden Teiler schrittweise erhöhst, muss der erste Treffer auch eine Primzahl sein.

[negaH]

Zitat:

Nana, bleib' mal auf Boden ... hinten eine Stelle mehr sollte (im Dezimalsystem) die Zahl höchstens ver19fachenb, aber nicht 1000

du meinst ver-10-fachen oder ?

Je nach Wertebereich der zu faktorisierenden Zahl wird man mit unterschiedlichen Verfahren arbeiten müssen.

Hat man zb. eine Liste aller kleinen Primzahlen bis 2^32 so kann man logischerweise nur Zahlen bis 2^64 damit per Trial Division testen.

Gruß Hagen

[Antigo]

Das war der erste Ansatz den ich verfolgt hatte (Methode 1). Ich hab die Zahl einfach durch alle Primzahlen geteilt die kleiner gleich der Hälfte der Zahl waren. Dafür musste ich aber bei großen Zahlen mehrere hunderttausend Primzahlen errechnen, was einfach unglaublich viel Rechenzeit kostet.

Besser funktioniert es andersrum(Methode2+3). Jetzt suche ich nicht mehr nach einer Primzahl die gleichzeitig Teiler der Zahl ist, sondern nach einem Teiler der Zahl der gleichzeitig Primzahl ist. Dadurch muss ich unfassbar weniger Primzahlen berechnen als vorher.

edit: das ging an Khabarakh

[Khabarakh]

Zitat:

Zitat von Antigo

Besser funktioniert es andersrum(Methode2+3). Jetzt suche ich nicht mehr nach einer Primzahl die gleichzeitig Teiler der Zahl ist, sondern nach einem Teiler der Zahl der gleichzeitig Primzahl ist. Dadurch muss ich unfassbar weniger Primzahlen berechnen als vorher.

Hmm, kannst du deine Vorgehensweise noch etwas ausführen? Die Möglichkeit zum Selbst Nachschauen ist ja leider nicht gegeben ;) .

[Cöster]

Zitat:

Zitat von Khabarakh

Zitat:

Zitat von Antigo

Bei der Faktorisierung ist das allerdings anders. Hier muss ich bis zur Hälfte durchgehen.
Ich gehe ja folgendermassen vor (Methode 2/Methode 3), dass ich die Zahl durch alle Zahlen teile und nach einem ganzzahligen Teiler suche (wiederum zahl mod i = 0). Habe ich einen gefunden, überprüfe ich ob dieser Teiler auch eine Primzahl ist, [...]

Wozu denn das :shock: ? Wenn du den zu testenden Teiler schrittweise erhöhst, muss der erste Treffer auch eine Primzahl sein.

Ganz genau! Wenn du es nämlich so machst, wie ich es beschrieben hab, wird die Zahl, ja nie durch z.B. 4 teilbar sein. Wenn doch, wäre sie ja bereits bei der 2 geteilt worden und diese Zahl wird nicht weiter überprüft, sondern nur noch die Hälfte dieser Zahl (100 teilst du nie durch 4 sondern erst durch 2, dann hast du ja nur noch 50 und die lässt sich dann nicht mehr durch 4 teilen). Wenn man also (nach meinem Verfahren) einen möglichen Teiler findet, ist er immer eine Primzahl.

[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:

Zitat von jfheins

Zitat:

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:

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:

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 ;)

[Antigo]

ok ich bräuchte dann nochmal eure Hilfe.
Und zwar beim Statusbalken.

Ich hab mir folgendes überlegt:
Ich habe zwei Werte:
i -> Variable die alle Werte bis zur Wurzel der zu faktorisierenden Zah durchgeht
a -> Wurzel der zu faktorisierenden Zahl.

Wenn ich jetzt wissen will wieviel Prozent i von a ist. Rechne Ich i/a*100. Da ich mit Integer Werten arbeite rechne ich aber erst i*100 und das Ergebnis davon durch a, was aufs selbe rauskommt.

Mein Code sieht jetzt so aus:

Delphi-Quellcode:

    Nmul(z,i,100);
    Ndiv(z,a);
    Progressbar1.Position:= Nint32(z);
    Application.Processmessages;

Das funktioniert soweit auch sehr gut. Es wird alles richtig angezeigt, nur wenn ich folgende Primzahl teste:
2813418473392999
dann dauert das auf meinem System über 2 Minuten bis das Programm mir anzeigt das es eine Primzahl ist. Während dessen wächst der Statusbalken brav.
Nehme ich jetzt aber den oben geposteten COde raus, braucht das Programm nur noch 4 Sekunden(!).
Das heisst der Code bremst das Programm immens ab. ALso müsste ich ihn seltener ausführen lassen. HAt jemand eine Idee wie ich das bewerkstellige, bzw. am besten bewerkstellige. Ich könnte natürlich alle Variablen global definieren, also aus der eigentlichen Faktorisierungsprozedur rausholen und mit einem Timer alle paar Sekunden den Status abfragen, aber vielleicht gibts da noch eine bessere methode?!


danke schonmal :)


edit: wobei sich dieser Balken eigentlich sowieso nur bei Primzahlen lohnt, da bei allen anderen Zahlen sowieso vor der Wurzel der Zahl abgebrochen wird, wenn die faktorisierung abgeschlossen ist. Von daher würde der Balken irgendwo bei einem drittel oder so abbrechen, was auch wieder blöd wäre....

[negaH]

rechne

Delphi-Quellcode:

var
  Root,Steps,Counter:
begin
  Root := N^0.5;
  Steps := N / Root / 2 / 100; 
  Counter := Steps;
  repeat
    if Counter <= 0 then 
    begin
      ProgressBar.Position := Root / Prime * 100;
      Counter := Steps;
    end;
    Counter := Counter -1;
  until ....
end;

oder so

Delphi-Quellcode:

var
  Tick: Cardinal;
begin
  Tick := GetTickCount + 250;
  repeat
    if GetTickCount >= Tick then
    begin
      Tick := GetTickCount + 250;
      ProgressBar.Position := Prime / Root * 100;
      ProgressBar.Update;
    end;
  until ...
end;

Im letzten Fall wird die ProgressBar nur 4 mal pro Sekunde = 250ms aktualisiert. Ich würde diese Methode vorziehen da sie die ProgressBar unabhängig vom eigentlichen Programmcode in einem exakten zeitlichen Interval aktualisert.

Ansonsten solltest du mit NIsProbablePrime(N) VOR jeder Trial Divison auf Prim überprüfen (aber nur bei großem N -> NSize(N) > 32).
NIsProbablePrime() soll laut Pomerance (anerkannter Mathematiker) erst bei Zahlen größer 10^1000 eine Falschantwort liefern. Pomerance hat ein Preisgeld ausgesetzt für denjenigen der als erster eine Zahl findet bei dem sein Primzahltest diese Zahl als Primzahl ausweist obwohl es keine ist. Das ist bei Pseudo-Primzahl-Tests immer eine Wahrscheinlichkeit, weshalb es eben nur ein Pseudo-Primzahl-Test ist. Bisher hat noch kein Mensch eine solche Zahl gefunden, Pomerance sitzt also noch auf seinem Preisgeld.


Gruß Hagen

[Antigo]

Deine zweite Methode gefällt mir. Ich werd das mal einbauen, danke :)

Zitat:

Ansonsten solltest du mit NIsProbablePrime(N) VOR jeder Trial Divison auf Prim überprüfen

Jo das hatte ich auch schon überlegt, aber ich denke mal das lasse ich. Oder ich baue eine Checkbox ein, und nur wenn diese aktiviert ist, wird die Zahl vor dem faktorisieren auf Prim geprüft.

[negaH]

Zitat:

jo das hatte ich auch schon überlegt, aber ich denke mal das lasse ich. Oder ich baue eine Checkbox ein, und nur wenn diese aktiviert ist, wird die Zahl vor dem faktorisieren auf Prim geprüft.

Das ist ansich auch eine gute Idee, da NIsProbablePrime() intern ja selber eine Trial Division bis 2^32 ausführt. Am besten wäre es NIsProbablePrime(N) nur dann aufzurufen wenn N mehr als 64 Bits groß ist -> NSize(N) > 64.

Allerdings wenn du NSPP(N, [1,2]) statt NIsProbablePrime(N) benutzt dann wird intern keine Trial Division mehr durchgeführt, das wäre dann schneller.

In meiner DEMO zum DECMath solltest du dir mal die Unit TestUnit.pas genauer anschauen. Darin dürftest du 3 Funktion finden

Delphi-Quellcode:

function NPollardRho(var D: IInteger; const N: IInteger): Boolean;
function NPollardPM1(var D: IInteger; const N: IInteger; Bound: Cardinal = 0): Boolean;
function NWilliamsPP1(var D: IInteger; const N: IInteger): Boolean;

Das sind alles Faktorizations-Verfahren.

Gruß Hagen

[negaH]

Probiere mal die Zahl 18303891083514198529 == 1919369 * 9536410707641 mit Methode 3 aus.

Gruß Hagen

[Antigo]

Vielen Dank für den Hinweis. Hat etwas gedauert bis ich mich rangesetzt hab, weil ich irgendwie keine Lust hatte den Fehler zu suchen, wenn er bei einer einzigen Zahl vorkommt. Es war aber nur ein Ausgabe Fehler. Das heisst er hat die 2 Faktoren gefunden, aber an einer bestimmten Stelle im Code wurde der Wert prim trotzdem auf true gesetzt, so dass die Meldung ** ist Prim ausgegeben wurde. Ich lade die neue Version gleich hoch.


edit: direkt das nächste Problem: Ich kann den Vorgang bei Methode 3 nicht abbrechen lassen. Ich sage bei jedem Schleifendurchlauf: Application.Processsmessages; genau wie bei Methode 1 und da funktioniert es. Bei Methode 3 kann ich aber nichtmal aufden Button der den Vorgang abbrechen soll klicken, die Anwendung hängt sich einfach auf. Gibts da noch einen Trick für?

[negaH]

Zitat:

Gibts da noch einen Trick für?

Keine Ahnung, ohne die Sourcen zu kennen kann man keine Aussage treffen.

Gruß Hagen

[Antigo]

naja mein Code sieht grob so aus

Delphi-Quellcode:

while (true) {Abfragen} and (not abbruch) do begin

  ...

  ...
  Application.Processmessages;
end;

Mit einem Klick auf Button 2 kann man die Variable abbruch auf true setzen und damit die Schleife abbrechen. Wie gesagt funktioniert das bei Methode 1, bei Methode 2 aus irgendeinem Grund jedoch nicht.

Daher meine Frage: Gibt es noch eine andere Methode die Applikation vor dem "aufhängen" zu bewahren?

[negaH]

ich mache solche dinge immer so

Delphi-Quellcode:

procedure TForm1ButtonClick(Sender: TObject);
var
  Tick: Cardinal;
begin
  if FInAction = 0 then
  try
    Inc(FInAction);
    Button.Caption := 'Abbruch'; 
    Tick := GetTickCount + 100;
    while FInAction = 1 do
    begin
      ...
      if Tick >= GetTickCount then
      begin
        Inc(Tick, 100);
        Application.ProcessMessages;
      end;
    end;
  finally
    FinAction := 0;
    Button.Caption := 'Start';
  end else
  begin
    Inc(FInAction); // ist >= 1, wir setzte FInAction auf > 1, bedeutet Abbrechen
    Button.Caption := 'beende';
  end;
end;

1.) FInAction: Integer wird als Field in deinem TForm deklariert. FInAction kann 3 Staties annehmen
FInAction == 0, bedeutet nichts wird aktuell berechnet und zb. Button hat die Caption == "Start"
FInAction == 1, bedeutet unsere Berechnung läuft, Button.Caption = "Abbrechen"
FinAction >= 2, bedeutet unsere Berechnung soll auf Benutzerwusch hin beendet werden

2.) FInAction macht also die Methode .ButtonClick() vor Rekursionen sicher das diese Methode nicht reentrant sein kann -> weil wir ja Application.ProcessMessages aufrufen

3.) Application.ProcessMessage wird in einem festen Intervall aufgerufen, hier alle 100 Millisekunden. Das macht deine Berechnung weitaus schneller

In deiner TForm1.OnCloseQuery() Methode solltest du nun Abfragen ob FInAction == 0 ist. Wenn ja, dann kannst du das Form schließen lassen, wenn nein dann wird FInAction inkrementiert und OnCloseQuery verhindert das Form zu schließen.

Gruß Hagen
Gruß Hagen

[Hawkeye219]

Ein kleiner Dreher ist drin: beim Vergleich der 'Ticks' müssen die beiden Seiten vertauscht werden:

Delphi-Quellcode:

if GetTickCount >= Tick then

Gruß Hawkeye