Uebungsblatt 7 Name: Joe User Tutor: ???? Email: juser@icp.uni-stuttgart.de ========== AUFGABE 7.1 (Fliesskommaarithmetik) ========== 7.1.1 32bit-IEEE-Hexadezimaldarstellung von PI: 0x40490fda Rechenweg: Genauigkeit: 7 Stellen Genauigkeit 32bit-IEEE-Hexadezimaldarstellung von 22/7: 0x40492492 Rechenweg: Genauigkeit: 7 Stellen Genauigkeit ========== 7.1.2 32-bit-IEEE-Hexadezimaldarstellung von 22/7-PI: 0x3aa5bd38 Rechenweg: Genauigkeit: 4 Stellen Genauigkeit ========== AUFGABE 7.2 (Fibonacci-Effizienz) ========== Skript: import time, math 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(4,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(4,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() 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: import random, math, time import pylab as plt # 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 = [] t1 = [] t2 = [] t3 = [] err1 = [] err2 = [] err3 = [] for i in range(21): n = 2**i N.append(n) print "i=%d N=%d" % (i, n) before = time.clock() pi1 = compute_pi1(n) after = time.clock() t1.append(after-before) err1.append(abs(math.pi - pi1)) before = time.clock() pi2 = compute_pi2(n) after = time.clock() t2.append(after-before) err2.append(abs(math.pi - pi2)) before = time.clock() pi3 = compute_pi3(n) after = time.clock() t3.append(after-before) err3.append(abs(math.pi - pi3)) print "pi1=%e pi2=%e pi3=%e" % (pi1, pi2, pi3) plt.subplot(2,2,1) plt.plot(N, t1, 'o-', N, t2, 'x-', N, t3, '*-') plt.subplot(2,2,2) plt.loglog(N, err1, 'o-', N, err2, 'x-', N, err3, '*-') plt.subplot(2,2,3) plt.loglog(t1, err1, 'o-', t2, err2, 'x-', t3, err3, '*-') plt.subplot(2,2,4) plt.semilogy(t1, err1, 'o-', t2, err2, 'x-', t3, err3, '*-') plt.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)