Re: Faktorisierung
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 ;) |
Re: Faktorisierung
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:
Deine Methode kannst du beschleunigen:
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; 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 |
Re: Faktorisierung
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 |
Re: Faktorisierung
Zitat:
Zitat:
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:
Vielen Dank für deine Hilfe :) |
Re: Faktorisierung
Zitat:
|
Re: Faktorisierung
Zitat:
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 |
Re: Faktorisierung
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 :) |
Re: Faktorisierung
Zitat:
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. |
Re: Faktorisierung
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 :) |
Re: Faktorisierung
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 ;)
|
Alle Zeitangaben in WEZ +1. Es ist jetzt 02:01 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