AG von zur Gathen - Algorithmische Mathematik

Sommersemester 2000

Seminar Computeralgebra

Gesucht: 200 000 000 000 Dezimalstellen von $\pi$
oder die 40 000 000 000 000-ste Binärziffer von $\pi$

Die ältesten Methoden zur beliebig genauen Berechnung von $\pi$ gehen wohl auf Archimedes (um 250 v.Chr.) zurück. Er bestimmte $\pi$erstmals auf zwei Nachkommastellen genau, und zwar indem er den Umfang in einen Kreis ein- und umbeschriebener regelmäßiger Vielecke ermittelte. Im Laufe der Jahrhunderte wurde $\pi$ immer genauer berechnet. Heute sind 206 158 430 000 Dezimalen bekannt. (Würde man dies vorlesen wollen, so bräuchte man bei einer Geschwindigkeit von 3 Ziffern pro Sekunde etwa 2178 Jahre.)

1995 fanden Rabinowitz & Wagon einen ,,Zapfhahn``-Algorithmus, der ,,tröpfchenweise`` eine Ziffer nach der anderen ausgibt und nicht (wie die obigen) alle auf einmal. Nie jedoch konnte jemand eine Ziffer berechnen, ohne auch alle Ziffern bis dorthin gleich mit zu berechnen, bis 1997 Bailey, Borwein & Plouffe eine Formel entdeckten, mit der man eine einzelne Ziffer der Binärdarstellung von $\pi$ direkt berechnen kann:

\begin{displaymath}\pi = \sum_{i=0}^{\infty} \frac1{16^{i}} \left( \frac4{8i+1}-\frac2{8i+4} -\frac1{8i+5} -\frac1{8i+6} \right).\end{displaymath}
Wie entstehen solche Formeln? Wie gewinnt man daraus schnelle Algorithmen? Welche Methoden braucht man für die Umsetzung? ... Unter anderem mit diesen Fragen wollen wir uns in diesem Seminar befassen.

Organisatorisches

Zeit und Ort: Mittwoch 16-18 Uhr, D3.344.
Vorbesprechung: 12. April 2000, 1615 Uhr.
Studiengänge: LS II (Medienschein möglich), Mathematik Diplom, Informatik Diplom.
Scheinerwerb: Vortrag und Ausarbeitung.
Qualifizierter SN: Ja.

Themen

Links und Literatur


Author: Michael Nüsken, last change: