Manfred Börgens Mathematische Probleme # 87 |
Liste aller Probleme mit Lösungen voriges Problem nächstes Problem |
zur Leitseite |
Münzwurf statt Würfeln
Die Lösung steht im unteren Teil der Seite.
Die Kernfrage dieses Problems lautet:
Wie kann man das Würfeln (mit einem gewöhnlichen 6-seitigen Würfel) durch eine Folge von Münzwürfen möglichst effizient ersetzen?
Über diese Frage kann man nachdenken, ohne die folgenden Ausführungen gelesen zu haben. Wer jedoch erst die Details kennenlernen möchte, die in der Kernfrage stecken, sollte weiterlesen.
Durch wiederholtes Werfen einer Münze kann man zufällige Folgen von 0 und 1 erzeugen. Durch Werfen eines Würfels erhält man zufällige Folgen von Zahlen aus {1,2,3,4,5,6}. Wenn man einen Würfel braucht, aber keinen hat, kann man die Augenzahlen durch 3 Münzwürfe erzeugen, z.B. so:
000 → 1
001 → 2
010 → 3
011 → 4
100 → 5
101 → 6
110 → nochmal 3 Münzwürfe
111 → nochmal 3 Münzwürfe
Man braucht also im Durchschnitt mehr als 3 Münzwürfe, da man von den 8 möglichen Wurffolgen nur 6 verwenden kann. Das ist eine ungünstige Situation, die für bestimmte anders geformte "Würfel" nicht gilt. Hat der "Würfel" z.B. 4 Seiten (Tetraeder), benötigt man 2 Münzwürfe, bei einem 8-seitigen "Würfel" (Oktaeder) benötigt man 3 Münzwürfe, allgemein bei einem 2n-seitigen "Würfel" n Münzwürfe. Im Prinzip lassen sich alle s-seitigen "Würfel" mit s ≥ 2 herstellen ( s = 2 → Münze; s ∈ {4,6,8,12,20} → platonische Körper; sonst prismenförmige Kreisel, siehe Bild).
"Würfel" mit s = 4, s = 8, s = 16 Seiten
Somit braucht man zur Erzeugung der Augenzahlen eines gewöhnlichen Würfels mehr Münzwürfe als bei einem 8-seitigen Würfel. Offenbar benötigt man das Minimum von log2 s Münzwürfen für s Würfelseiten genau dann, wenn s eine Zweierpotenz ist.
Ab hier wollen wir uns nur noch mit gewöhnlichen Würfeln mit 6 Seiten beschäftigen.
Aufgabe 1
Wie viele Münzwürfe braucht man im Durchschnitt, wenn man eine Münze in 3er-Folgen solange wirft, bis man eine Augenzahl zwischen 1 und 6 erzeugt hat?
Wir haben oben gesehen, dass 110 und 111 nicht brauchbar sind und zu erneutem Werfen der Münze führen. Aber das weiß man schon nach den beiden ersten Münzwürfen 11x , so dass man danach abbrechen und eine neue Serie starten kann. Also könnten z.B. die ersten drei erzeugten Augenzahlen 2, 4, 1 so zustande kommen:
11 001 → 2
011 → 4
11 11 000 → 1
Hier hätte man also für 3 Augenzahlen 15 Münzwürfe benötigt; ohne Abbruch wären es 18 gewesen.
Aufgabe 2
Wie viele Münzwürfe braucht man im Durchschnitt zur Erzeugung einer Augenzahl zwischen 1 und 6 , wenn man bei den nicht brauchbaren Würfen rechtzeitig abbricht?
Mit oder ohne Abbruch: Im Vergleich zum 8-seitigen "Würfel" (oder anderen 2n-seitigen "Würfeln") ist der Münzwurf als Ersatz zum normalen Würfeln umständlich. Für s = 2n sind lediglich log2 s Münzwürfe erforderlich; dieser Wert würde theoretisch für s = 6 nur log2 6 ≈ 2,58496 betragen - tatsächlich braucht man deutlich mehr als 3 Münzwürfe, wie die Fragen 1 und 2 gezeigt haben.
Es gibt aber eine Möglichkeit, näher an den theoretischen Wert log2 6 heranzukommen - sogar beliebig nahe. In der Regel wird man ja mehrere (oder viele) Augenzahlen erzeugen wollen, etwa für ein Gesellschaftsspiel. Dann möchte man also eine lange Folge von Augenzahlen zwischen 1 und 6 durch eine Folge von 0 und 1 darstellen. Nun kommt die gute Idee, wie man dies möglichst effektiv durchführt: Man erzeugt die Augenzahlen nicht einzeln (also durch jeweils 3 Münzwürfe), sondern man verkettet die Folge der Münzwürfe zu einer langen Binärzahl. Diese wird dann insgesamt (d.h. nicht abschnittsweise) transformiert in ebenfalls verkettete Augenzahlen. Also liegt es nahe, statt der Augenzahlen 1 bis 6 die Zahlen 0 bis 5 zu nehmen, um in der Basis 6 rechnen zu können, also in Hexalzahlen. Um es kurz zusammenzufassen:
Man rechnet eine Zahl zur Basis 2 in eine Zahl zur Basis 6 um. Die erste entspricht einer Folge von Münzwürfen, die zweite einer Folge von Augenzahlen beim Würfel.
Beispiel: Wir werfen 13-mal die Münze und erhalten damit die Binärzahl 00001011001102 . Transformation in die Hexalzahl ergibt: 00001011001102 = 013546 (entspricht den Augenzahlen 1, 2, 4, 6, 5 ). Die führende 0 in der Hexalzahl ist wichtig, denn wir erhalten mit diesem Verfahren immer genau 5 Augenzahlen: Mit 13 Münzwürfen kann man 213 = 8192 Zufallszahlen im Bereich 00000000000002 bis 11111111111112 erzeugen. Wegen 11111111111112 = 1015316 decken also die binären Zufallszahlen alle 5-stelligen Hexalzahlen 000006 bis 555556 ab. Die Binärzahlen 11110011000002 bis 11111111111112 können nicht verwertet werden, sie entsprechen nämlich den (sechsstelligen) Hexalzahlen von 1000006 bis 1015316 . Wir werden noch sehen, dass wir damit dem theoretischen Minimalwert für das Verhältnis Münzwürfe/Augenzahlen schon erheblich nähergekommen sind.
Im Folgenden soll m die Anzahl der Augenzahlen beim Würfeln sein, die man erzeugen möchte; n = n(m) sei die dafür erforderliche Anzahl von Münzwürfen.
Aufgabe 3
Berechnen Sie n aus m .
Setzen Sie am = n/m . Berechnen Sie das theoretische Minimum a der am .
Aufgabe 4
Es sind nicht alle erzeugten binären Zufallszahlen verwertbar. Analog zu Aufgabe 1 stellt sich also die Frage:
Wie viele Münzwürfe d1 braucht man im Durchschnitt, wenn man eine Münze in Folgen der Länge n solange wirft, bis man eine Hexalzahl der Länge m erzeugt hat?
Dafür ist es wie bei den Aufgaben 1 und 2 hilfreich, die Wahrscheinlichkeit p für die zufällige Erzeugung einer n-stelligen Binärzahl zu berechnen, die einer m-stelligen Hexalzahl entspricht.
Auch hier kann man bei den nicht verwendeten binären Zufallszahlen vorzeitig abbrechen. Man berechnet die größte verwertbare Binärzahl v (diese entspricht 55...56 ). Dann wirft man wiederholt die Münze für die binäre Zufallszahl, beginnend bei der vordersten Stelle (also bei der höchsten 2er- Potenz). Abbruch erfolgt, sobald eine Ziffer der Zufallszahl größer als die entsprechende Ziffer in v ist.
Aufgabe 5
Analog zu Aufgabe 2 stellt sich also die Frage: Wie viele Münzwürfe d2 braucht man im Durchschnitt zur Erzeugung einer Hexalzahl der Länge m , wenn man bei den nicht brauchbaren Würfen rechtzeitig abbricht?
Welche Werte von m sind besonders günstig? Das sind offenbar diejenigen, bei denen von den 2n möglichen Wurffolgen nur wenige unbrauchbar sind. Also sucht man m mit 6m ≈ 2n (dabei ist 6m ≤ 2n wegen der Wahl von n gewährleistet).
Aufgabe 6
Machen Sie eine Tabelle für 1 ≤ m ≤ 50 , die folgende Werte enthält:
- m
- n (siehe Aufgabe 3)
- p (Anteil der brauchbaren binären Zufallszahlen)
- d1 (durchschnittliche Anzahl insgesamt benötigter Münzwürfe bei nicht-abbrechendem Verfahren, siehe Aufgabe 4)
- v1 = (d1/m)/a (Verhältnis der durchschnittlichen Anzahl benötigter Münzwürfe für einzelne Augenzahlen zum theoretischen Minimum bei nicht-abbrechendem Verfahren)
- d2 (durchschnittliche Anzahl insgesamt benötigter Münzwürfe bei abbrechendem Verfahren, siehe Aufgabe 5)
- v2 = (d2/m)/a (Verhältnis der durchschnittlichen Anzahl benötigter Münzwürfe für einzelne Augenzahlen zum theoretischen Minimum bei abbrechendem Verfahren)
Berechnen Sie überschlägig (d.h. in ungefährer Näherung) für große n , was sich für die di und die vi in den extremen Fällen p ≈ 1 bzw. p ≈ 0,5 ergibt. Insbesondere ist dabei das folgende Ergebnis interessant:
p ≈ 0,5 ⇒ d2 ≈ n + 3
Die Tabelle zeigt große Unterschiede in der Effizienz der Münzwürfe für die Erzeugung von Würfel-Augenzahlen. Einen einzigen Würfelwurf oder zwei solche Würfe durch Münzwürfe zu ersetzen, erfordert einen unverhältnismäßig großen Aufwand. Aber m = 5 oder m = 41 erbringen sehr gute Ergebnisse mit d1/m und d2/m nahe bei a . Ist das Zufall oder gibt es eine Gesetzmäßigkeit für die "guten" m ? Dafür gibt es einen Ansatz:
Es gilt n ≈ a·m ( a kommt in der Lösung von Aufgabe 3 vor). Aussichtsreiche Kandidaten für m , die ein effizientes Verfahren erlauben, kann man also durch Näherungsbrüche b/c ≈ a finden; dann kann man m = c wählen und somit n = b .
Damit kommen wir zur abschließenden Aufgabe. Der Faktor a aus Aufgabe 3 soll in hoher Genauigkeit als Bruch approximiert werden. Dafür gibt es das Verfahren der Kettenbrüche. Man benutzt am besten ein Programm, das die Kettenbruch-Folge bi/ci ≈ a berechnet. Die Theorie der Kettenbrüche stellt sicher, dass lim i→∞ bi/ci = a . Dabei sind die bi/ci abwechselnd > a und < a .
Aufgabe 7
Bestimmen Sie mit Hilfe der Kettenbruchentwicklung, welche m sich besonders gut für eine effiziente Ersetzung von Hexalzahlen durch Binärzahlen eignen.
Aufgabe 1
Wie viele Münzwürfe braucht man im Durchschnitt, wenn man eine Münze in 3er-Folgen solange wirft, bis man eine Augenzahl zwischen 1 und 6 erzeugt hat?
p sei die Wahrscheinlichkeit, mit einem dreifachen Münzwurf eine der sechs Augenzahlen zu erzeugen. Nur 110 und 111 sind "Fehlversuche", also ist p = 6/8 = 0,75 .
Bei k Fehlversuchen benötigt man 3 Münzwürfe für den erfolgreichen letzten Versuch und 3·k Münzwürfe für die Fehlversuche. Die Wahrscheinlichkeit für genau k Fehlversuche, gefolgt vom ersten Erfolg, ist (1-p)k·p (k ∈ No) . Also ist der Erwartungswert d1 für die Gesamtanzahl der Münzwürfe:
d1 = 3 + 3·Σk≥0 k·(1-p)k·p
Bei der Berechnung der letzten Summe könnten wir es uns einfach machen: Das ist nämlich der Erwartungswert der geometrischen Verteilung und lässt sich leicht einer Formelsammlung entnehmen. Es sollen aber hier zwei mögliche Rechenwege angegeben werden. Wir setzen q = 1 - p :
Σk≥0 k·qk = Σk≥0 (k+1)·qk - Σk≥0 qk = Σk≥1 k·qk-1 - 1/(1-q) = (1/q)·Σk≥0 k·qk - 1/(1-q)
⇒ Σk≥0 k·qk = q/(1-q)2
Das kann man auch mit der Ableitung der geometrischen Reihe beweisen:
Σk≥0 qk = 1/(1-q) (|q| < 1)   (ableiten) ⇒ Σk≥1 k·qk-1 = 1/(1-q)2 ⇒ Σk≥0 k·qk = q/(1-q)2
(1) Also ist der Erwartungswert für die Anzahl der Fehlversuche Σk≥0 k·(1-p)k·p = (1-p)/p
Es folgt: d1 = 3 + 3·(1-p)/p = 4
Das bedeutet: Man benötigt genauso viele Münzwürfe wie beim 16-seitigen Würfel !
Aufgabe 2
Wie viele Münzwürfe braucht man im Durchschnitt zur Erzeugung einer Augenzahl zwischen 1 und 6 , wenn man bei den nicht brauchbaren Würfen rechtzeitig abbricht?
Alle notwendigen Rechnungen sind schon bei Aufgabe 1 erfolgt. Die einzige Änderung betrifft die Anzahl der Münzwürfe bei den Fehlversuchen ( 2 statt 3 ). Die durchschnittliche Anzahl von Münzwürfen nennen wir d2 :
d2 = 3 + 2·(1-p)/p = 32/3 ≈ 3,66667
Im Folgenden soll m die Anzahl der Augenzahlen beim Würfeln sein, die man erzeugen möchte; n = n(m) sei die dafür erforderliche Anzahl von Münzwürfen.
Aufgabe 3
Berechnen Sie n aus m .
Setzen Sie am = n/m . Berechnen Sie das theoretische Minimum a der am .
Damit man mit n Münzwürfen alle 6m möglichen Folgen von Augenzahlen erzeugen kann, muss 6m ≤ 2n gelten. Um nicht unnötig viele Münzwürfe durchzuführen, wählt man n als kleinste natürliche Zahl mit 6m ≤ 2n . Somit gilt:
2n-1 < 6m ≤ 2n ⇒ n-1 < m log2 6 ≤ n ⇒ n = ⌈m log2 6⌉ ( ⌈·⌉ steht für ganzzahlige Aufrundung)
n = ⌈m log2 6⌉ bedeutet m log2 6 ≤ n < m log2 6 + 1 ⇒ log2 6 ≤ am < log2 6 + 1/m
Also ist a = log2 6 ≈ 2,58496 . a ist uns schon aus der Problemstellung (hinter Aufgabe 2) bekannt, und wie eben bewiesen wurde, ist n = ⌈a·m⌉ ≈ a·m (ganzzahlige Aufrundung).
Aufgabe 4
Wie viele Münzwürfe d1 braucht man im Durchschnitt, wenn man eine Münze in Folgen der Länge n solange wirft, bis man eine Hexalzahl der Länge m erzeugt hat?
Lösung analog Aufgabe 1; (1) ist die zentrale Formel für die weiteren Rechnungen.
p sei die Wahrscheinlichkeit für die zufällige Erzeugung einer n-stelligen Binärzahl, die einer m-stelligen Hexalzahl entspricht.
p = 6m/2n ⇒ d1 = n + n·(1-p)/p
Aufgabe 5
Wie viele Münzwürfe d2 braucht man im Durchschnitt zur Erzeugung einer Hexalzahl der Länge m , wenn man bei den nicht brauchbaren Würfen rechtzeitig abbricht?
n1 sei die durchschnittliche Anzahl von Münzwürfen für diejenigen Binärzahlen, die nicht benötigt werden, also (in Dezimaldarstellung) von 6m bis 2n-1 . Bei Aufgabe 2 war n1 = 2 . Hat man n1 berechnet, ergibt sich d2 analog zu den Aufgaben 1, 2 und 4:
d2 = n + n1·(1-p)/p
In der Berechnung von n1 liegt die eigentliche Herausforderung. n1 kommt nur zum Tragen, wenn die Münzwürfe eine größere Zahl als 6m - 1 ergeben. Schreibt man beide Zahlen als Binärzahlen u > v , so gilt diese Ungleichung genau dann, falls von links einige Ziffern übereinstimmen und in der nächsten Ziffer bei u eine 1 , bei v eine 0 steht. (Man beachte, dass dies nur funktioniert, wenn man die Binärzahl durch Münzwürfe von vorn aufbaut, also beginnend bei der höchsten Potenz.)
Das soll zunächst am Beispiel m = 2 ( ⇒ n = 6) verdeutlicht werden. In der folgenden Tabelle stehen links die Binär- und rechts die Hexalzahlen:
000000 00
000001 01
000010 02
000011 03
000100 04
000101 05
000110 10
000111 11
001000 12
001001 13
001010 14
001011 15
001100 20
001101 21
001110 22
001111 23
010000 24
010001 25
010010 30
010011 31
010100 32
010101 33
010110 34
010111 35
011000 40
011001 41
011010 42
011011 43
011100 44
011101 45
011110 50
011111 51
100000 52
100001 53
100010 54
100011 55 v
100100 Abbruch an 4. Stelle hier fangen die u an
100101 Abbruch an 4. Stelle
100110 Abbruch an 4. Stelle
100111 Abbruch an 4. Stelle
101000 Abbruch an 3. Stelle
101001 Abbruch an 3. Stelle
101010 Abbruch an 3. Stelle
101011 Abbruch an 3. Stelle
101100 Abbruch an 3. Stelle
101101 Abbruch an 3. Stelle
101110 Abbruch an 3. Stelle
101111 Abbruch an 3. Stelle
110000 Abbruch an 2. Stelle
110001 Abbruch an 2. Stelle
110010 Abbruch an 2. Stelle
110011 Abbruch an 2. Stelle
110100 Abbruch an 2. Stelle
110101 Abbruch an 2. Stelle
110110 Abbruch an 2. Stelle
110111 Abbruch an 2. Stelle
111000 Abbruch an 2. Stelle
111001 Abbruch an 2. Stelle
111010 Abbruch an 2. Stelle
111011 Abbruch an 2. Stelle
111100 Abbruch an 2. Stelle
111101 Abbruch an 2. Stelle
111110 Abbruch an 2. Stelle
111111 Abbruch an 2. Stelle
28 der Binärzahlen führen auf einen Abbruch, davon 4 an der 4. Stelle, 8 an der 3. Stelle und 16 an der 2. Stelle. Damit können wir n1 berechnen:
n1 = (4·4 + 3·8 + 2·16)/28 = 18/7 ≈ 2,57143
Für die "erfolgreichen" Folgen von Münzwürfen benötigt man also n = 6 Würfe, für die "nicht-erfolgreichen" im Schnitt lediglich ca. 2,57 Würfe.
Hier ist dann wegen p = 36/64 :
d2 = 6 + (18/7)·(7/9) = 8
Das kann man nun verallgemeinern. Wir bezeichnen die k-te Stelle (von vorn) von v mit vk . Ist vk = 0 , so gibt es unter den 2n - 6m Binärzahlen u , die größer als v sind, genau 2n-k , die an den ersten k-1 Stellen mit v übereinstimmen und an der k-ten Stelle gleich 1 sind - diese Binärzahlen u stehen für einen Abbruch nach k Münzwürfen. Damit erhalten wir:
(2) n1 = (Σvk=0 k·2n-k)/(2n-6m) = (Σvk=0 k/2k)/(1-6m/2n) = (Σvk=0 k/2k)/(1-p)
Aufgabe 6
Legende zur Tabelle:
m Anzahl Würfe mit Würfel
n Anzahl Würfe mit Münze
p Anteil der brauchbaren binären Zufallszahlen
d1 durchschnittliche Anzahl insgesamt benötigter Münzwürfe bei nicht-abbrechendem Verfahren
v1 Verhältnis der durchschnittlichen Anzahl benötigter Münzwürfe für einzelne Augenzahlen zum theoretischen Minimum bei nicht-abbrechendem Verfahren
d2 durchschnittliche Anzahl insgesamt benötigter Münzwürfe bei abbrechendem Verfahren
v2 Verhältnis der durchschnittlichen Anzahl benötigter Münzwürfe für einzelne Augenzahlen zum theoretischen Minimum bei abbrechendem Verfahren
Die Tabelle wird der Übersichtlichkeit halber nur in Auszügen dargestellt.
m n p d1 v1 d2 v2
1 3 .750 4.00 1.547 3.67 1.418
2 6 .563 10.67 2.063 8.00 1.547
3 8 .844 9.48 1.223 8.63 1.113
4 11 .633 17.38 1.681 12.67 1.225
5 13 .949 13.70 1.060 13.30 1.029
6 16 .712 22.47 1.449 17.00 1.096
··
11 29 .676 42.91 1.509 30.24 1.063
12 32 .507 63.14 2.035 34.84 1.123
13 34 .760 44.72 1.331 35.21 1.048
··
40 104 .659 157.80 1.526 105.43 1.020
41 106 .989 107.22 1.012 106.09 1.001
42 109 .741 147.01 1.354 109.76 1.011
··
50 130 .594 218.92 1.694 131.84 1.020
Man erkennt, dass die Wahl von m die Effizienz des Verfahrens erheblich beeinflusst. So ist z.B. m = 2 besonders ungünstig, aber auch z.B. m = 4 und m = 12 schneiden ziemlich schlecht ab.
Interessant sind die großen Unterschiede zwischen d1 und d2 (bzw. zwischen v1 und v2 ), wenn p nahe 0,5 liegt. Das wird plausibel werden, wenn wir die Fälle p ≈ 1 und p ≈ 0,5 genauer betrachten. Wir erhalten überschlägig für große n (da die n schnell wachsen, ist das keine bedeutende Einschränkung):
p ≈ 1 ⇒ 6m ≈ 2n n ≈ a·m d1 ≈ d2 ≈ n v1 ≈ v2 ≈ 1 (siehe in der Tabelle z.B. m = 41 )
p ≈ 0,5 ⇒ 6m ≈ 2n-1 n - 1 ≈ a·m d1 ≈ 2·n v1 ≈ 2 d2 ≈ n + 3 v2 ≈ 1 (siehe in der Tabelle z.B. m = 12 )
Diese Näherungswerte folgen aus den Definitionen, die in den Aufgaben 3 bis 5 gegeben wurden. Nur d2 ≈ n + 3 für p ≈ 0,5 bedarf einer Erklärung:
p ≈ 0,5 bedeutet v = 10000...2 mit vielen Nullen hinter der führenden 1 ( n groß). Daraus folgt n1 ≈ (Σk≥2 k/2k)/(1-p) = (2 - 1/2)·2 = 3 nach (2) und der Herleitung von (1).
Aufgabe 7
Bestimmen Sie mit Hilfe der Kettenbruchentwicklung, welche m sich besonders gut für eine effiziente Ersetzung von Hexalzahlen durch Binärzahlen eignen.
In der Tabelle zu Aufgabe 6 sind zwei Zeilen grün markiert worden, weil sie besonders effiziente Ergebnisse erzielen ( m = 5, m = 41 ). Diese Zahlen kommen als Nenner c in der Folge der Näherungsbrüche vor, die man mit Hilfe der Kettenbrüche ( a ≈ b/c ) erhält:
log2 6 ≈ 2/1
≈ 3/1
≈ 5/2
≈ 13/5
≈ 31/12
≈ 106/41
≈ 137/53
...
Die Theorie der Kettenbrüche stellt die Konvergenz der Brüche gegen a sicher:
(3) |b/c - a| < c-2 (da die Folge der Nenner c streng monoton wächst, folgt die Konvergenz)
In der Aufgabenstellung wurde schon festgestellt, dass m = c und n = b als Kandidaten für effiziente Approximationen in Frage kommen.
Man beachte, dass der 1., 3., 5. usw. Näherungsbruch kleiner als log2 6 ist, der 2., 4., 6. usw. dagegen größer. Wir werden zeigen, dass für unser Problem nur die größeren Näherungsbrüche in Frage kommen:
1. Fall a ≈ b/c und a < b/c
a = b/c - ε mit ε < c-2 nach (3). Aus m = c, n = b folgt a·m = n - ε·m > n - 1/m ≥ n-1 ⇒ n = ⌈a·m⌉
Also erfüllt diese Wahl von n, m die Anforderung aus Aufgabe 3.
Wir erhalten damit zwei Folgen mi = 1, 5, 41, ... und ni = 3, 13, 106, ... mit lim i→∞ ni/mi = a = log2 6 und wegen (3) ni < a·mi + 1/mi . Daraus folgt, dass die zugehörigen pi = 6mi/2ni den Grenzwert 1 haben:
p = 6m/2n = 6m/6n/a = 6m-n/a ⇒ pi > 6-1/mi → 1
⇒ d1/n → 1 und d2/n → 1
Also ist auch die Effizienz gezeigt.
2. Fall a ≈ b/c und a > b/c
Dann gilt: a = b/c + ε ⇒ a·m > n ⇒ ⌈a·m⌉ ≠ n
Also erfüllen die Brüche aus der Kettenbruchentwicklung, die kleiner als log2 6 sind, nicht die Anforderung aus Aufgabe 3. Wegen d2 ≈ n + 3 und v2 ≈ 1 sind die zugehörigen m aber beim abbrechenden Verfahren durchaus geeignet (dann ist n = b + 1 ).
Die folgenden beiden Tabellen für die beiden Fälle (aufgebaut wie in Aufgabe 6) machen die Ergebnisse deutlich. Es werden nur die m = c aus der Kettenbruchentwicklung aufgeführt:
m n p d1 v1 d2 v2
1 3 .750 4.00 1.547 3.67 1.418
5 13 .949 13.70 1.060 13.30 1.029
41 106 .989 107.22 1.012 106.09 1.001
306 791 .999 791.81 1.001 791.01 1.00002
m n p d1 v1 d2 v2
1 3 .750 4.00 1.547 3.67 1.418
2 6 .563 10.67 2.063 8.00 1.547
12 32 .507 63.14 2.035 34.84 1.123
53 138 .501 275.42 2.010 140.97 1.029
Kategorie: Zahlen und Zahlsysteme, Berechnung von π
Publiziert 2014-06-15 Stand 2013-08-29
voriges Problem | Liste aller Probleme mit Lösungen | nächstes Problem