Kurs Algorithmenkonstruktion: Modul 9

Jede Bruchzahl

; (1)

läßt sich in der Form

(2)

notieren. Hierbei ist

(3)

der ganzzahlige Anteil von ,
(4)

die Systembruchdarstellung [1, 2] von zur Basis
(5)

mit den Ziffernwerten

; i= 1, 2, 3, ... . (6)

Die Systembruchdarstellung Gl. (4) ist endlich (abbrechend), wenn b als Primteiler nur die Primteiler der Basis B enthält, andernfalls unendlich und reinperiodisch oder gemischtperiodisch.

Die Berechnung der A_i (Systembruchentwicklung von ) erfolgt sequentiell in der Reihenfolge A₀, A₁, A₂, A₃, ... mittels des nachstehend in Struktogrammform [3] notierten Algorithmus (A1) (vgl. [2, 4, 5]), im nichtabbrechenden Fall ist die Anzahl n der zu berechnenden Ziffern vorzugeben.

Bereits ausgegebene Ziffern werden dabei nicht mehr in die Berechnung einbezogen (Spigot-Ausgabe [6]).

Algorithmus (A1): Systembruchentwicklung von

9.1.

Verifizieren Sie den Algorithmus (A1) (vgl. [2,4]).

9.2.

Für B=2 bzw. B=10 liefert (A1) die Binär- bzw. Dezimalbruchentwicklung von

.
Untersuchen Sie die Fälle

B = 2^k ;	(7)
B= 10^k ;	(8)

9.3.

Verallgemeinern Sie den Algorithmus (A1) zu einem

Algorithmus (A2) zur Systembruchentwicklung eines geschachtelten Bruches (nested expression [6])

(9)
; ; (10)

Algorithmus (A3) zur Systembruchentwicklung eines Kettenbruches (continued fraction [7, 8])

	(11)
; .	(12)

9.4.

Untersuchen Sie die Leistungsfähigkeit der in 9.3. erhaltenen Algorithmen experimentell:

Benutzen Sie hierzu Beispiele für geschachtelte Brüche bzw. für Kettenbrüche aus Tabelle 1 bzw. 2 (vgl. [9])

unter Zugrundelegung der Basen

B=10	(13)
B=10^k ; k=2, 3, 4, ... .	(14)

Diskutieren Sie die dabei auftretenden "Übertragsprobleme"

, (15)
und geben Sie Algorithmen zu ihrer Beseitigung ("Nachbearbeitung", vgl. [9], Abschn. 3.4) an.
Integrieren Sie diese Nachbearbeitungsalgorithmen gegebenenfalls in die Algorithmen (A2) bzw. (A3).

Vergleichen Sie
die über den Berechnungsgang

mit anschließender Nachbearbeitung erhaltenen Systembrüche mit den via

Umformung des gegebenen in eine Bruchzahl (Tabelle 3), danach
Systembruchentwicklung von mittels (A1)

berechneten Systembrüchen.
Diskutieren Sie dabei zu beobachtende Genauigkeitsunterschiede.

a_i	b_i	c_i
2i-1	4i	1
(n-1) (2i-1)	2ni	1
3i-2	6i	1
?	?	?
fib (2(i-2))	fib (2i) ^*)	1
1	i	1	e
n	i	1
i	2i+1	2 (1)
i (2i-1)	3 (3i+1) (3i+2)	3+5i
i²	(2i+1) (2i+2)	9	²
(2i-1)³	(8i)³	42i+5	16^-1
2i-1	9 (2i+1)	1
2i-1	n² (2i+1)	1

Tabelle 1:

Beispiele für geschachtelte Brüche, die für m

(infinitely nested expression) mathematische Konstanten bzw. Funktionswerte elementarer einstelliger Funktionen darstellen

*)	fib (i) - Fibonacci-Zahl: fib (i+2) = fib (i+1) + fib (i) fib (-2) = 1, fib (-1) = 0, fib (0) = fib (1) = 1

c₀ a₁ a_i; i=2,3,... b₁ b_i; i=2,3,...

1 1 2

1 2 2

1 1 1

a

2

2 i+1 i+1 e

2 1 i-1 i e

2 i 1 i-1 2,5

0 i i

0 1 (i-1)² 2i-1

0 2i-1 1 (i-1)² 0,40668965... = ?

1 i² 2i+1

1 i⁴ 2i+1

0 i² 1

0 2i+1 2i+1 0.779306397... = ?

1

1

1

1

1

Tabelle 2: Beispiele für Kettenbrüche, die für m (unendliche Kettenbrüche) mathematische Konstanten bzw. Funktionswerte elementarer einstelliger Funktionen darstellen

Berechnung mittels Definitionsgleichung

(9) (11)

Zugeordnete Determinantendarstellung (vgl. Modul 7, Gl. (10))

Zugeordnetes Matrizenprodukt (vgl. Modul 7, Gl. (9))

Tabelle 3: Umwandlung eines in eine Bruchzahl

9.5.

Die in Tabelle

zusammengestellten Beispiele für

stellen bei m

die in den Tabellen ebenfalls angegebenen mathematischen Konstanten bzw. Funktionswerte elementarer einstelliger Funktionen dar und nähern diese für endliche m mit unterschiedlichen Genauigkeiten an.

So erhält man für den m-gliedrigen geschachtelten Bruch

(16)

(Tabelle 1, Zeile 8) bei

B= 10 (17)

n= m (18)

mittels (A2) und Nachbearbeitung (A4) eine m-stellige Dezimalbruchdarstellung

, (19)

die mit noch zu untersuchender Genauigkeit annähert:

. (20)

Tabelle 4 zeigt die so berechneten p_m - Werte in Abhängigkeit von m.

m	p_m
1	2.	6
2	2.	9	3
3	3.	0	4	7
4	3.	0	9	8	3
5	3.	1	2	1	4	9
6	3.	1	3	2	1	5	6
7	3.	1	3	7	1	2	9	4
8	3.	1	3	9	4	6	9	6	7
9	3.	1	4	0	5	7	8	1	6	9
10	3.	1	4	1	1	0	6	0	2	1	5
11	3.	1	4	1	3	5	8	4	7	2	5	1
12	3.	1	4	1	4	7	9	6	4	8	9	6	0
13	3.	1	4	1	5	3	7	9	9	3	1	7	3	4
14	3.	1	4	1	5	6	6	1	5	9	3	4	4	9	4
15	3.	1	4	1	5	7	9	7	8	8	1	3	7	5	9	5
16	3.	1	4	1	5	8	6	3	9	5	0	3	7	0	6	1	4
17	3.	1	4	1	5	8	9	6	0	5	5	8	8	2	3	0	4	6
18	3.	1	4	1	5	9	1	1	6	6	9	9	1	4	0	1	8	7	8
19	3.	1	4	1	5	9	1	9	2	7	6	7	5	1	4	6	9	2	6	3
20	3.	1	4	1	5	9	2	2	9	8	7	4	0	3	3	9	6	3	2	6	9
21	3.	1	4	1	5	9	2	4	7	9	9	5	8	2	2	4	4	4	2	7	5	4
22	3.	1	4	1	5	9	2	5	6	8	5	5	3	6	3	4	7	9	4	3	3	6	8
23	3.	1	4	1	5	9	2	6	1	1	9	0	8	8	3	5	6	0	4	6	8	5	4	1
24	3.	1	4	1	5	9	2	6	3	3	1	4	3	0	3	5	9	0	1	5	9	0	7	8	6
25	3.	1	4	1	5	9	2	6	4	3	5	5	3	4	4	7	9	6	0	8	5	8	1	2	6	0
26	3.	1	4	1	5	9	2	6	4	8	6	5	9	9	5	1	9	4	0	8	7	6	0	6	5	9	4

Tabelle 4: Wertetabelle der

-Approximation p_m(m)

Aus Tabelle 4 entnimmt man:

im Mittel sind nur die ersten div(m, 3) Ziffern von p_m zugleich gültige Ziffern von ; p_m liefert also nur eine relativ schlechte Näherung für (vgl. [9], Abschn. 3.4.3.)
der Differenzenquotient von p_m läuft gegen 2:
, (21)
die darauf basierende lineare Korrektur (vgl. Modul 1, Gln. (9) - (13))

(22)

ergibt z. B. für m=24 und m=25 die verbesserten Werte

m p1_m

24 3.141592653|9638...

25 3.141592653|7664...

(23)

und damit einen Zugewinn von zwei gültigen Ziffern.

Konstruieren Sie auf diesen experimentellen Ergebnissen fußend in Analogie zu Modul 1 und Modul 6 einen effizienten Korrekturalgorithmus (A5), der aus den "verrauschten" Basiswerten p_m durch lineare Mittelung rechtsbündig möglichst viele weitere gültige Ziffern extrahiert.

Erproben Sie den Verbund (A2) - (A4) - (A5) experimentell für andere geschachtelte Brüche aus Tabelle 1. Integrieren Sie, wenn möglich, diesen Verbund zu einem Kompaktalgorithmus. Übertragen Sie, wenn möglich, diese Lösung auf den Verbund (A3) - (A4) - (A5).

9.6.

Geschachtelter Bruch Gl. (9) und Kettenbruch Gl. (11) lassen sich gemäß Bild 1 als zueinander spiegelbildliche "Kettenstrukturen" auffassen.

Bild 1: -"Kettenstruktur" und -"Kettenstruktur"

Es soll nun anhand einer Faktensammlung untersucht werden, ob diese vom morphologischen Befund der Gln. (9) und (11) her plausiblen Begriffsbildungen auch eine konstruktive Bedeutung besitzen.

Zunächst erhält man das folgende erstaunliche Ergebnis

	(24)
,	(25)

d.h., e wird durch beide Kettenstrukturen bei gleicher Wertebelegung dargestellt.

Zum Vergleich:

	(26)
	(27)
	(28)
	(29)
	(30)
	(31)
	(32)
	(33)

Untersuchen Sie das Konvergenzverhalten der Kettenstrukturen Gl. (24) - (33).

Die Kettenstrukturen mit konstanten Elementen liefern:
(34)
. (35)

Untersuchen Sie experimentell die Konvergenz von Gl. (35) für repräsentative Werte von a, b und c.

Für die Darstellung bzw. Approximation einer positiven reellen Zahl r durch einen regelmäßigen Kettenbruch

(36)

("Kettenbruchentwicklung") läßt sich aufgrund der geforderten Ganzzahligkeit der Kettenbruchelemente leicht ein Algorithmus angeben:

Algorithmus (A5): Kettenbruchentwicklung von

(A5) terminiert nach der Berechnung einer vorgegebenen Anzahl m von Kettenbruchelementen (n = m) oder zuvor bei Erfüllung der datenabhängigen Haltbedingung x = int(x) (n m).

Im ersten Falle

läßt sich entweder bei genügend groß gewähltem m ein Bildungsgesetz für die b_i und damit die vollständige Kettenbruchdarstellung Gl. (36) erkennen (die dann natürlich noch verifiziert werden muß), oder
man erhält für r eine Kettenbruchapproximation mit der Genauigkeit von m Elementen, wobei ein Bildungsgesetz für die b_i nicht erkennbar ist.

Der zweite Fall tritt ein, wenn r eine rationale Zahl ist; er tritt dann immer ein, wenn m beliebig groß gewählt wird.

Beispiele:

(37)

- Bildungsgesetz erkennbar: ''Triaden''
(vgl. [7] (38)

- Bildungsgesetz erkennbar: rein periodisch mit Periode
(39)

- Bildungsgesetz nicht erkennbar, Halt bei ,
Kettenbruchapproximation für
(40)

Erfüllung der datenabhängigen Haltbedingung bei

Konstruieren Sie in analoger Weise Algorithmen für die Entwicklung einer positiven reellen Zahl in die Kettenstrukturen
(41)

und
(42)

und geben Sie repräsentative Beispiele hierfür an.

Vergleichen Sie das Konvergenzverhalten der Kettenstrukturentwicklungen

Gl. (36), (A5)
Gl. (41), (A6)
Gl. (42), (A7).

Zu jeder konvergierenden unendlichen Kettenstruktur läßt sich eine unendliche Kettenstruktur angeben, die gegen denselben Wert konvergiert:

- Euler-Transformation [10]
(43)

- Kompressionstransformation (vgl. [9], Abschn. 3.5.2)
(44)

mit
(45)

(46)

Vergleichen Sie anhand repräsentativer Beispiele das Konvergenzverhalten der linken und rechten Kettenstrukturen Gl. (43) und Gl. (44).

Aufgaben | Lösungen | Literatur | Korrespondenz
Die Module

Modul 9

Aufgaben

Darstellung einer Bruchzahl im Zahlensystem mit der Basis B, Verallgemeinerungen

Zahlentheoretische Algorithmen