Matroids Matheplanet Forum Index
Moderiert von Spock mire2
Mathematische Software & Apps » Mathematica » Divisors[x][[2]] optimieren
Autor
Universität/Hochschule Divisors[x][[2]] optimieren
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 1511
  Themenstart: 2021-09-22 23:51

Hallo zusammen, mit Divisors[x][[2]] bekommt man ja den kleinsten echten Teiler einer Zahl. Bei großen Zahlen wird das jedoch sehr langsam. Besonders Zahlen des Types "kleiner Primfaktor" * RSA-Zahl müssen sich doch gut optimieren lassen. Ich suche nun den schnellsten Weg. Ansätze: a) statt "ALLE Teiler" müsste man sofort nach dem 1. Teiler abbrechen. Natürlich könnte man mit einer Schleife alle Mod[x,Prime[n]] durchgehen... b) Funktion in DLL auslagern... Vorschläge? Grüße


   Profil
Primentus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.02.2016
Mitteilungen: 1342
Wohnort: Deutschland
  Beitrag No.1, eingetragen 2021-09-23 00:09

Hallo hyperG, eine Möglickeit, die es auf jeden Fall noch gäbe, wäre: \sourceon Mathematica FactorInteger[x][[1, 1]] \sourceoff Die bei FactorInteger durch die Primfaktorenzerlegung erzeugte Liste dürfte bei sehr großen Zahlen vermutlich kürzer sein, als die Liste der oftmals sehr vielen Teiler bei Verwendung von Divisors. Je länger die erstellten und verwendeten Listen werden und je mehr es davon gibt, desto langsamer wird es nämlich in der Regel. Oftmals scheinen die beiden Funktionen ähnlich schnell zu sein, aber vielleicht ergibt sich bei sehr häufiger Anwendung (also im Mittel) ja doch ein zeitlicher Vorteil bei FactorInteger. Das ist erstmal das, was mir auf die Schnelle einfällt. Selber händisch teilen, wie etwa auf Rest "Null" prüfen mit Mod ginge natürlich auch, wie Du schon sagtest. Bei sehr großen Zahlen wird Mod zwar auch irgendwann langsamer, aber bei nur kleinen Teilern und den momentan zu untersuchenden Stellenanzahlen bei der Fragestellung "Schleifen in Zahlenfolge" (siehe entsprechender Thread) dürfte das jedoch noch nicht sonderlich ins Gewicht fallen. LG Primentus


   Profil
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 1511
  Beitrag No.2, vom Themenstarter, eingetragen 2021-09-23 16:19

Hallo Primentus, ich habe sogar noch einen Zusatzparameter gefunden, der genau die Abkürzung für kleine einfache Teiler erledigt (die anderen beiden Teiler sind sehr groß): \sourceon Mathematica aRSA=8874990734040105871503942490249165332503748243178195915613; Divisors[aRSA][[2]]//Timing FactorInteger[aRSA][[1,1]]//Timing FactorInteger[aRSA,Automatic][[1,1]]//Timing Out[23]= {11.8125,79} Out[24]= {11.78125,79} Out[25]= {1.921875,79} \sourceoff Sah zunächst genau nach dem gesuchten aus: etwa 10 mal schneller!! Aber dann kam der Rückschlag: \sourceon Mathematica (**) Divisors[11052631578947368417400582155838300853869632670753880551][[2]]//Timing FactorInteger[11052631578947368417400582155838300853869632670753880551][[1,1]]//Timing FactorInteger[11052631578947368417400582155838300853869632670753880551,Automatic][[1,1]]//Timing {10.187 s,1801756122305627857543} {9.8593 s,1801756122305627857543} {1.9687 s,11052631578947368417400582155838300853869632670753880551} \sourceoff Er scheint also immer kurz vor 2 s aus der Funktion herauszuspringen, auch wenn noch kein Faktor ermittelt werden konnte :-(


   Profil
Primentus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.02.2016
Mitteilungen: 1342
Wohnort: Deutschland
  Beitrag No.3, eingetragen 2021-09-23 16:34

Hallo hyperG, interessant - diesen Parameter Automatic kannte ich noch nicht in diesem Zusammenhang. Warum es im zweiten Beispiel fehlschlägt, liegt vermutlich daran, dass der sog. "kleinste Teiler" 1801756122305627857543 wohl schon zu groß ist. Einen Teiler mit 22 Dezimalstellen würde ich zumindest nicht mehr als klein empfinden. Aber vielleicht kannst Du ja in Dein Programm etwas einbauen, dass wenn FactorInteger mit Parameter Automatic wieder die ursprünglich übergebene Zahl liefert, dass Du dann doch ausnahmsweise mit Divisors arbeitest oder eben den FactorInteger-Aufruf nochmal wiederholst, nur dann eben ohne Automatic. So würde dann zumindest der Großteil der Zahlen sehr schnell abgearbeitet werden - die Frage ist nur, wie häufig das vorkommt, dass ein kleinster Teiler so groß ist. Eigentlich würde ich aber schon davon ausgehen, dass in den meisten Zahlen auch ein kleinster Teiler kleiner als 1000 vorkommen sollte. LG Primentus


   Profil
hyperG hat die Antworten auf ihre/seine Frage gesehen.

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]