Quadratisches & Zahlkörpersieb < Sonstiges < Schule < Mathe < Vorhilfe
|
Hallo,
In welcher Einheit werden die Laufzeiten der beiden Faktorisierungsverfahren angegeben? Ist das die Anzahl der benötigten Schritte oder direkt die Zeit? Für das Quadratische Sieb habe ich die Formel: [mm] \exp\left(\sqrt{\log n\cdot\log \log n}\right), [/mm] wobei n für die zu faktorisiernde Zahl steht. Angenommen ich will eine 100-stellige Zahl faktorisieren, z.B.10^99 , dann bekomme ich als Ergebnis 5,469 [mm] \cdot [/mm] 10^60, kann das stimmen?
Dann habe ich für die Laufzeit des Zahlkörpersiebs die Formel [mm] e^{(C+o(1))(n)^\frac13(\log n)^\frac23}, [/mm] wobei n diesmal direkt die Anzahl der Stellen der Zahl angibt und C entweder [mm] (\bruch{32}{9})^\bruch{1}{3} [/mm] oder [mm] (\bruch{64}{9})=^\bruch{1}{3} [/mm] ist, jenachdem ob das spezielle oder das allgemeine Zahlkörpersieb genomen wird. Bei dieser Formel weiß ich aber nicht, was das o(1) bedeutet, ich hab schonmal rausgefunden, dass es wohl O-Notation heißt, aber was bedeutet das für das Ergebnis, wenn ich z.B. eine 100-stellige Zahl faktorisieren möchte?
Liebe Grüße
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hey,
Ich habe eben gesehen, dass beim quadratischen Sieb manchmal auch ln statt log verwendet wird, was ja zu einem ganz anderen Ergebnis führen würde. Dann bekäme ich für n=10^99 1,898 [mm] \cdot [/mm] 10^15 raus. Was von beiden stimmt den jetzt? Ich hoffe, mir kann noch jemand helfen.
Liebe Grüße
|
|
|
| |
|
Hallo sandy_cheeks,
> Hey,
>
> Ich habe eben gesehen, dass beim quadratischen Sieb
> manchmal auch ln statt log verwendet wird, was ja zu einem
> ganz anderen Ergebnis führen würde.
In der angelsächsischen Literatur wird [mm] \log [/mm] anstelle von [mm] \ln [/mm] benutzt. Könnte es daran liegen?
Nur wir Deutschen benutzen - glaube ich - [mm] \ln.
[/mm]
In welchem Zusammenhang steht deine Frage übrigens?
Ich habe davon noch nie gehört... ![[verwirrt]](/images/smileys/verwirrt.gif "[verwirrt]")
Vielleicht sollte man deine Frage in [welches?] Hochschulforum verschieben, damit du Antworten bekommst?
> Dann bekäme ich für
> n=10^99 1,898 [mm]\cdot[/mm] 10^15 raus. Was von beiden stimmt den
> jetzt? Ich hoffe, mir kann noch jemand helfen.
> Liebe Grüße
Gruß informix
|
|
|
| |
|
Hey, danke für die Antwort! Also es geht um das Faktorisierungsproblem - es ist einfach zwei große Primzahlen zu multiplizieren, aber wenn man die beiden Faktoren nicht kennt, ist es schwer das Produkt wieder zu zerlegen.
Das Quadratische Sieb ist ein Faktorisierungsverfahren, das bis zu 110-stelligen Zahlen benutzt wird, danach z.B. das Zahlkörpersieb. Ich brauche gar nicht zu wissen, wie genau die beiden funktionieren, ich bräuchte nur Beispiele für die Laufzeiten. Zum Beispiel: Wie lange würde es dauern, eine 100-stellige Zahl mit dem Quadratischen Sieb zu faktorisieren. Aber ich komme mit den beiden Formeln nicht zurechte, ich habe nirgendwo gefunden, in welcher Einheit das Ergebnis angegeben wird, ich denke mal, das sit die Anzhal der Schritte und dann kommt es eben auf den Rechner an, wie lange der dafür braucht.
Aber zu deiner Antwort: log und ln ist doch was ganz unterschiedliches, oder? Was benutze ich denn jetzt um auf das richtige Ergebnis zu kommen?
Und wie verschiebe ich meine Frage (tut mir Leid, ich kenn mich hier noch nicht so aus^^) oder macht das jemand anders?
LG
|
|
|
| |
|
Hallo,
ich nehme mal an es geht um die Effizienz des Algorithmus? Ich kenne dieses von dir angegebene Verfahren nicht.. (wie funktioniert es?). Bei der Ermittlung der Effizienz geht man so vor, dass man sich die dominante Rechenoperation (oder Funktion) heraussucht und schaut, wie oft diese in Abhängigkeit der Eingabewerte benutzt werden.
Zudem schätzt man in aller Regel nur die Größenordnung ab: [mm]O(1)
Die Effizenz durch die Laufzeit abzuschätzen ist keine gute Idee (da diese sehr rechnerabhängig ist).
Ich hoffe ich habe deine Frage richtig verstanden....
Mit freundlichen Grüßen,
Christoph
|
|
|
| |
|
Hallo sandy_cheeks,
> Hey, danke für die Antwort! Also es geht um das
> Faktorisierungsproblem - es ist einfach zwei große
> Primzahlen zu multiplizieren, aber wenn man die beiden
> Faktoren nicht kennt, ist es schwer das Produkt wieder zu
> zerlegen.
> Das Quadratische Sieb ist ein Faktorisierungsverfahren, das
> bis zu 110-stelligen Zahlen benutzt wird, danach z.B. das
> Zahlkörpersieb. Ich brauche gar nicht zu wissen, wie genau
> die beiden funktionieren, ich bräuchte nur Beispiele für
> die Laufzeiten. Zum Beispiel: Wie lange würde es dauern,
> eine 100-stellige Zahl mit dem Quadratischen Sieb zu
> faktorisieren. Aber ich komme mit den beiden Formeln nicht
> zurechte, ich habe nirgendwo gefunden, in welcher Einheit
> das Ergebnis angegeben wird, ich denke mal, das sit die
> Anzhal der Schritte und dann kommt es eben auf den Rechner
> an, wie lange der dafür braucht.
>
> Aber zu deiner Antwort: log und ln ist doch was ganz
> unterschiedliches, oder? Was benutze ich denn jetzt um auf
> das richtige Ergebnis zu kommen?
Langsam! die Angelsachsen schreiben [mm] \log, [/mm] wenn sie den  Logarithmus [<-- click it!] zur Basis e meinen, in Deutschland schreibt man [mm] \log_e{a}=\ln{a}
[/mm]
Aber [mm] \log_{10}{a}=\lg{a} [/mm] wenn die Basis 10 lautet, sonst bei allgemeiner Basis b: [mm] \log_b{a}.
[/mm]
>
> Und wie verschiebe ich meine Frage (tut mir Leid, ich kenn
> mich hier noch nicht so aus^^) oder macht das jemand
> anders?
Das können nur Moderatoren.
Aber es geht ja zunächst um das Verständnis der Abkürzungen; das ist für Schüler auch interessant.
Gruß informix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:20 Fr 09.01.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:20 Di 13.01.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
