Prof. Dr. Franz Schweiggert und Dr. Johannes Mayer Abt. Angewandte Informationsverarbeitung
Ralph Guderlei Blatt 1 - 28. April 2006


[c]



Software Engineering Praxis (SS 2006)


Abgabetermin: 05. Mai 2006

1 Näherungsweise Bestimmung von $\pi $ (7 Punkte)

Schon seit der Antike gibt es Verfahren um die Kreiszahl $\pi $ näherungsweise zu bestimmen. Ein klassischer Ansatz ist die Flächenformel.

1.1 Flächenformel

Bei der Flächenformel wird ausgenutzt, dass $\pi $ nur zur Berechnung der Kreisfläche, aber nicht zur Berechnung der Fläche des den Kreis einschließenden Quadrats benötigt wird. Sei $r$ nun der Radius eines Kreises, dann ergibt sich

$\textstyle \parbox{5cm}{ \begin{displaymath}A_{\mbox{Kreis}} = \pi r^2\end{disp... ...playmath}\pi = 4 \frac{A_{\mbox{Kreis}}}{A_{\mbox{Quadrat}}}.\end{displaymath}}$
\includegraphics[width=6cm]{Flaechenformel}

Die Fläche des Quadrats kann direkt berechnet werden, die Fläche des Kreises kann näherungsweise durch Auszählen der Punkte $(x,y)$ bestimmt werden, die im Kreis liegen. Um diese Punkte zu zählen kann man ein Koordinatensystem mit $0 \ge x \ge 2r$ und $0 \ge y \ge 2r$ konstruieren, dessen Mitte in $(r,r)$ liegt. Für alle Punkte im Kreis gilt dann $(x-r)^2 + (y-r)^2\le r^2$.

Um ein brauchbares Ergebnis zu erhalten sollte $r \ge 10000$ gewählt werden.

1.2 Bailey-Borwein-Plouffe-Formel

Die Bailey-Borwein-Plouffe-Formel ist eine relativ neue Darstellung von $\pi $ als Reihe:

\begin{displaymath} \pi = \sum_{k=0}^{\infty} \frac{1}{16^k}\left( \frac{4}{8k ... ...\frac{2}{8k + 4} - \frac{1}{8k + 5} - \frac{1}{8k + 6} \right) \end{displaymath}

Mit dieser Formel können beliebige Stellen von $\pi $ bestimmt werden, ohne die vorhergehenden Stellen berechnen zu müssen. Die Zahl $\pi $ kann durch Abbrechen der Reihe nach $n$ Summationen näherungsweise berechnet werden.


Implementieren Sie beide Methoden zur näherungsweisen Berechung von $\pi $. Vergleichen die Ergebnisse der beiden Methoden mit der in Java vorgehaltenene Konstante Math.PI. Welche Aussage können Sie über die Laufzeit der beiden Methoden machen?

2 Größter gemeinsamer Teiler (3 Punkte)

Um den ggT zweier Integer-Werte a, b zu bestimmen, wird häufig der Euklidsche Algorithmus verwendet. Eine Variante ist der sog. ''binäre Euklidsche Algorithmus'':

  1. setze m = a, n = b
  2. dividiere m und n durch 2 solange, bis eine der beiden Zahlen ungerade ist. Die Zahl der notwendigen Divisionsschritte sei k. Falls n gerade ist, vertausche m und n.
  3. dividiere m durch 2, bis m ungerade ist
  4. ist m<n, so vertausche diese Zahlen
  5. setze m = m - n
  6. ist m $\ne$ 0, dann fahre fort mit Schritt 3.
  7. ggT(a,b) = n $\cdot 2^k$

Implementieren Sie den binären Euklidschen Algorithmus in Java.

Quellen und Hinweise

Viel Erfolg!


Ralph Guderlei 2006-04-28