close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

1 Vorab: die Zahlenlänge wird hier mit n und nicht wie ursprünglich

EinbettenHerunterladen
1
Vorab: die Zahlenlänge wird hier mit n und nicht wie ursprünglich in
der Vorlesung mit k bezeichnet.
B EMERKUNG . Für jede reelle Zahl u gilt: u ≤ u < u + 1.
A LGORITHMUS . Stellendarstellung.
Eingabe: b, x ∈ N, b ≥ 2.
Ausgabe: b-adische Darstellung an−1 , . . . , a0 von x.
1. Berechne b0 = 1, b1 = b, b2 , b3 , . . . bis bn > x. [Also n = 0 falls x = 0,
und andernfalls bn−1 ≤ x < bn .] yn = x.
2. For i = n − 1, n − 2, . . ., 0 do 3–4
yi+1
3.
ai =
,
bi
4.
yi = yi+1 − ai bi .
S ATZ . Der Algorithmus arbeitet richtig wie spezifiziert.
B EWEIS .
Zu zeigen ist: ∀i < n
0 ≤ ai < b,
ai b i .
x = (an−1 , . . . , a0 )b =
0≤i<n
Wir zeigen mit Induktion nach n − i für 0 ≤ i ≤ n:
(*)
0 ≤ aj < b für i ≤ j < n,
(**)
0 ≤ yi < b i ,
(***)
ai b j + y i .
x=
i≤j<n
Induktionsanfang: n − i = 0, also i = n.
(*) Es gibt keine j mit n ≤ j < n, also wird in (*) für kein j etwas
behauptet. Das ist wahr.
(**) x = yn < bn .
(***) x = 0 + yn = x.
Induktionsschritt:
(*) Nach Induktionsvoraussetzung gilt (*) für i + 1, also 0 ≤ aj < b für alle
j mit i + 1 ≤ j < n. Es ist nur noch zu zeigen: 0 ≤ ai < b.
2
i+1
< b bi = b.
Dies gilt wegen 0 ≤ ai = yi+1
bi
Wir haben (**) für i + 1 in “<” benutzt.
(**) 0 ≤ yi < bi ?
Schritt 3:
yi+1
ai ≤ i < ai + 1,
b
nach der Bemerkung am Anfang,
ai bi ≤ yi+1 < ai bi + bi ,
0 ≤ yi = yi+1 − ai bi < bi .
(***)
?
aj b j + y i =
x =
i≤j<n
aj b j + ai b i + y i
i+1≤j<n
i
= x − yi+1 + ai b + yi = x.
Bei der dritten Gleichung haben wir die Induktionsvoraussetzung (***) für
i + 1 benutzt, und bei der letzten die Gleichung aus Schritt 4. Damit sind
(*), (**), (***) für alle i mit 0 ≤ i ≤ n bewiesen. Für i = 0 sind (*) und (***)
genau die Behauptungen am Anfang des Beweises, die zu zeigen waren.
Damit ist der Satz bewiesen.
Insbesondere ist 0 ≤ y0 < b0 = 1, also y0 = 0.
Wir wollen die Kosten des Algorithmus angeben, das heißt, die Anzahl
arithmetische Operationen, wobei wir als Operationen benutzen:
◦ abgerundete Division (oder Division mit Rest),
◦ Multiplikation,
◦ Addition oder Subtraktion.
Wir ignorieren dabei die Tests “x < bi ”, die in Schritt 1 für jedes i ≤ n
gemacht werden.
S ATZ 1. Seien x und b Eingaben des Algorithmus.
(i) Es ist n = logb x + 1 ≈ logb x.
(ii) Der Algorithmus benötigt 4n − 1 Operationen, wobei jeder Operand
eine Zahl ≤ bn ist.
3
B EWEIS .
(i) Sei l = logb x + 1. Dann ist
bl−1 = b
bl = b
logb x
logb x
≤ blogb x = x,
+1
> blogb x = x,
nach der Bemerkung am Anfang. Die Ungleichungen bn−1 ≤ x < bn
gelten also für n und l. Da dieser Exponent eindeutig bestimmt ist,
gilt l = n.
(ii) Schritt 0: n − 1 Operationen.
Schritte 3 + 4: je 3 Operationen pro Schleifendurchlauf. Die Schleife
wird n Mal durchlaufen, also gibt es insgesamt 3 · n Operationen.
Total n − 1 + 3n = 4n − 1 Operationen.
Document
Kategorie
Internet
Seitenansichten
5
Dateigröße
81 KB
Tags
1/--Seiten
melden