Laufzeit des Euklidischen Algorithmus
Hallo, wäre echt super, wenn mir jemand helfen könnte.
Und zwar suche ich nach einer Möglichkeit zu beweisen, dass sich der Rest im Euklidischen Algorithmus alle zwei Schritte mindestens halbiert. Ich weiß, dass sich der Rest mehr als halbiert, jedoch möchte ich nur beweisen, dass er sich halbiert und das ohne Verwendung von Fibonacci-Zahlen. Ich komme allerdings nicht darauf wie man das machen könnte. Habe gerade ein Brett vor'm Kopf. Im Internet finde ich leider keine Abhilfe. Überall wird nur beschrieben, wie man ermittelt, dass die Laufzeit höchstens 5 mal die Anzahl der Ziffern von b ist -,-!
Danke im vorraus, auch wenn ich mir sicher bin, dass da niemand helfen kann^^!
Mfg KGaru21
1 Antwort
Wenn du a durch b dividierst, dann gilt für den Rest r auf jeden Fall
r < b.
-
Fall r <= b/2. Dann hast du die Halbierung schon
-
Fall b/2 < r < b. Dann ist aber b-r < b/2, so dass der Rest im nächsten Schritt kleiner als b/2 ist.
Zahlenbeispiel mit 81 und 35
81 = 2 * 35 + 11. In diesem Beispiel ist 11 kleiner als die Hälfte von 35 und alles ist gut.
zweites Beispiel: 81 und 30.
81 = 2 * 30 + 21.
Hier ist 21 größer also die Hälfte von 30, aber die Differenz 30-21 ist dann logischerweise kleiner als die Hälfte von 30, daher folgt im nächsten Schritt:
30 = 1 * 21 + 9 (denn von den Zahlen 9 und 21 mit der Summe 30 können ja schlecht beide größer als die Hälfte von 30 sein.
Schon richtig, aber ich wollte ja nicht beweisen, dass r2 (Rest 2) < b/2, sondern, dass r2 (Rest 2) < 1/2* r1. Mit deinem oben genannten Beweis wird bewiesen, dass r2 kleiner als b/2 ist. Tut mir leid, wenn ich mich blöd anstelle, aber ich bin der Meinung das entscheidende fehlt noch in deiner Erklärung, damit ich darauf komme, warum r2 < 1/2*r1 sein muss.
Ich habe es jetzt verstanden :)!
Du hättest in deiner Erklärung einfach von der zweiten Zeile ausgehen sollen und nicht von der ersten, dann hätte ich es sofort verstanden ;)!
Trotzdem vielen Dank für die Hilfe, ich wundere mich, dass mir überhaupt jemand geantwortet hat^^! Und dann auch noch so schnell...
Wüsste ich, wie und wo ich deine Antwort als beste Antwort auszeichnen kann würde ich das tun. :)
Ich habe es jetzt verstanden :)!
Du hättest in deiner Erklärung einfach von der zweiten Zeile ausgehen sollen und nicht von der ersten, dann hätte ich es sofort verstanden ;)!
Trotzdem vielen Dank für die Hilfe, ich wundere mich, dass mir überhaupt jemand geantwortet hat^^! Und dann auch noch so schnell...
Wüsste ich, wie und wo ich deine Antwort als beste Antwort auszeichnen kann würde ich das tun. :)
Super, vielen Dank für die Antwort!
Aber eines musst du mir noch erklären; Warum wissen wir, dass der zweite Rest kleiner als die hälfte des ersten Restes ist, wenn wir wissen, dass der zweite Rest kleiner als b/2 ist? Ich meine bei b handelt es sich ja nicht um den Rest, richtig?
Mfg KGaru21