Gepostet: |
schneller Faktorisierungsalgorithmus | ||||||||||
Hallo Leute, ich bin echt am Verzweifeln... Folgendes habe ich bisher für eine Hausarbeit programmiert: module Seq357 where seq357 :: [Integer] erzeugt eine (potentiell unendlich lange aufsteigend sortierte) Liste aller Zahlen der Form 3^a * 5^b * 7^c mit a, b, c >= 0 seq357n dürfte klar sein. Die main-Funktion ist vorgegeben. Ich brauche eine Funktion, dass die Primzahlfaktoren der berechneten Summe in einer Zeit <= 30 sec. berechnet. Meiner braucht für die Hälfte schon so ca. 40sec. Ich habe im Netz schon nach anderen Algorithmen gesucht, aber bin nicht wirklich an schnelle gestoßen. Vlt könnt ihr mir helfen, wo ich das ganze optimieren kann, um diese Zeitvorgabe einzuhalten?! Mit Dank und freundlichen Grüßen Aljoscha |
|||||||||||
Zum Seitenanfang | |||||||||||
Gepostet: |
|||||||||||
Hallo Aljoscha, mir scheint, das Problem liegt bereits in der Funktion seq357. Einfach alle Zahlen 1, 2, ... durchprobieren funktioniert bei kleinen Zahlen sehr gut. Bei großen Zahlen sind aber oft riesige Lücken zwischen je zwei gefundenen Zahlen. Da die Funktion auch alle diese Zahlen durchprobiert, kostet dies unglaublich viel Zeit. Viel schneller wäre es die Zahlen 3^a*5^b*7^c der Reihe nach zu erzeugen, also 3^1*5^0*7^0=3, 3^0*5^1*7^0=5, 3^0*5^0*7^1=7, 3^2*5^0*7^0=9, etc. Dabei mußt du aufpassen, daß die Zahlen wirklich der Größe nach berechnet werden. Die Exponenten müssen also geschickt geändert werden, damit die nächste Zahl immer größer als alle schon berechneten ist. Das Funktionsprinzip deines Faktorisierungsalgorithmus' hab ich zwar auf die Schnelle nicht ganz verstanden, der wird vermutlich aber nicht die Hauptzeit bei der Berechnung ausmachen. Du solltest erstmal die Funktion seq357 schneller machen. Wenn die Faktorisierung dann noch zu lange dauert, kann man da immer noch eine bessere Methode suchen. Viele Grüße, Siracusa |
|||||||||||
Zum Seitenanfang | |||||||||||