Übungsblatt 7 Name: Joe User Tutor: ???? ========== AUFGABE 7.1 (Fibonacci-Effizienz) ========== Skript: import time from matplotlib.pylab import * def fib1(n): if n <= 1: return 1 return fib1(n-1)+fib1(n-2) def fib2(n, a=1, b=1): if n == 0: return a elif n == 1: return b else: return fib2(n-1, b, a+b) t1 = [] for i in range(1,18): before = time.clock() for r in range(10000): fib1(i) after = time.clock() t1.append((after-before)/10000) print "n=%d t1=%e" % (i, t1[-1]) t2 = [] for i in range(1,40): before = time.clock() for r in range(100000): fib2(i) after = time.clock() t2.append((after-before)/100000) print "n=%d t2=%e" % (i, t2[-1]) subplot(2,2,1) plot(t1, 'o-', t2, 'x-') subplot(2,2,2) semilogx(t1, 'o-', t2, 'x-') subplot(2,2,3) semilogy(t1, 'o-', t2, 'x-') subplot(2,2,4) loglog(t1, 'o-', t2, 'x-') show() ========== 7.1.2 Welchen asymptotischen Aufwand zeigt fib1(n)? exponentiell O(2**n) Welchen asymptotischen Aufwand zeigt fib2(n) linear O(n) ========== AUFGABE 7.3 (Numerische Integration) ========== Skript: from pylab import * import random, math # MC integration 1 def compute_pi1(N): step = 0 sum = 0 while step < N: x = random.random() y = random.random() if x*x + y*y < 1.0: sum += 1 step += 1 return (4.0 * sum) / N # MC integration 2 def compute_pi2(N): step = 0 sum = 0.0 while step < N: x = random.random() sum += (1.0 - x*x) ** 0.5 step += 1 return 4.0 * sum / N # Numerical integration 3 def compute_pi3(N): x = 0.0 sum = 0.0 while x < 1.0: sum += (1.0 - x*x) ** 0.5 x += 1.0/N return 4.0 * sum / N N = [] err1s = [] err2s = [] err3s = [] n_trial = 10 for i in range(21): n = 2**i N.append(n) print "i=%d N=%d" % (i, n) err1 = err2 = err3 = 0 for j in range(n_trial): pi1 = compute_pi1(n) err1 += abs(math.pi - pi1) pi2 = compute_pi2(n) err2 += abs(math.pi - pi2) pi3 = compute_pi3(n) err3 += abs(math.pi - pi3) err1s.append(err1/n_trial) err2s.append(err2/n_trial) err3s.append(err3/n_trial) print "pi1=%e pi2=%e pi3=%e" % (pi1, pi2, pi3) loglog(N, err1s, 'o-', N, err2s, 'x-', N, err3s, '*-') show() Welche asymptotische Genauigkeit zeigt compute_pi1(N)? O(N**(-0.5)) Welche asymptotische Genauigkeit zeigt compute_pi2(N)? O(N**(-0.5)) Welche asymptotische Genauigkeit zeigt compute_pi3(N)? O(N**-1) ========== AUFGABE 7.3 (Fliesskommaarithmetik) ========== 7.3.1 32bit-IEEE-Hexadezimaldarstellung von PI: 40490FDA Rechenweg: 1. Bias: 2^(8-1) -1 = 127 2. Dez -> Bin: 3.14159265358979323846 = 11,00100100001111110110101010001000100001011010001100001... 3. Normalisieren: 11,00100100001111110110101010001000100001011010001100001... * 2^0 = 1,100100100001111110110101010001000100001011010001100001... * 2^1 4. Exponent berechnen: 1 + 127 = 128 = 10000000 (Exponent Normalisierung) (Bias) 5. Vorzeichen: positiv -> 0 6. Ergebnis: 0 10000000 10010010000111111011010 (1Bit Vorzeichen) (8Bit Exponent) (23 Bit Mantisse (ohne Vorkomma Eins)) 32bit-IEEE-Hexadezimaldarstellung von 22/7: 40492492 Rechenweg: 1. Bias: 2^(8-1) -1 = 127 2. Dez -> Bin: 3.1428571428571428 = 11,00100100100100100100100100100100100100100100100100100... 3. Normalisieren: 11,00100100100100100100100100100100100100100100100100100... * 2^0 = 1,100100100100100100100100100100100100100100100100100100... * 2^1 4. Exponent berechnen: 1 + 127 = 128 = 10000000 (Exponent Normalisierung) (Bias) 5. Vorzeichen: positiv -> 0 6. Ergebnis: 0 10000000 10010010010010010010010 (1Bit Vorzeichen) (8Bit Exponent) (23 Bit Mantisse (ohne Vorkomma Eins)) ========== 7.3.2 Wieviele Dezimalstellen Genauigkeit haben diese Darstellungen? 7 Stellen Genauigkeit ========== 7.3.3 32-bit-IEEE-Hexadezimaldarstellung von 22/7-PI: 3AA5C000 Rechenweg: 0 10000000 10010010010010010010010 - 0 10000000 10010010000111111011010 1. Mantisse verschieben bis gleicher Exponent: (hier unnötig) 2. Subtraktion der Mantissen: 1.10010010010010010010010 - 1.10010010000111111011010 = 0.00000000001010010111000 3. Exponent anpassen: um 11 Stellen verschieben. -> Neuer Exponent 1-11=-10 -10 + 127 = 117 = 01110101 4. Ergebnis: 0 01110101 01001011100000000000000 bzw. 0x3aa5c000 Genauigkeit: 4 Dezimalstellen