אלגוריתם גאוס-לז'נדר

אלגוריתם גאוס-לז'נדר הוא אלגוריתם מהיר לחישוב הספרות של הקבוע המתמטי $\pi$, המבוסס על הממוצע האריתמטי-גאומטרי של שני מספרים. מספר הספרות המדויקות בהערכת הקבוע מוכפל בכל צעד, ובעזרת מחשב מודרני האלגוריתם מאפשר לחשב מיליארדי ספרות, ואף יותר.

אלגוריתם זה, ודומים לו, נחקרו על-ידי קרל פרידריך גאוס ואדריאן-מארי לז'נדר בראשית המאה ה-19. האלגוריתם הינו איטרטיבי מטבעו, ומבוסס על החלפה חוזרת של שני מספרים בממוצעים האריתמטי והגאומטרי שלהם.

הגרסה המוצגת כאן ידועה כ"אלגוריתם בראנט-סלאמין", בשל העובדה שהאלגוריתם נתגלה מחדש, באופן בלתי תלוי, על ידי מדען המחשבים ריצ'רד בראנט והמתמטיקאי יוג'ין סלאמין ב-1975.

תיאור האלגוריתם

אתחול האלגוריתם מתבצע על ידי מתן הערכים ההתחלתיים

$a_{0}=1\qquad b_{0}={\frac {1}{\sqrt {2}}}\qquad t_{0}={\frac {1}{4}}\qquad p_{0}=1$

השלב האיטרטיבי, בו חוזרים ומעדכנים את ערכי הפרמטרים בנוסחאות הבאות עד השגת מספר הספרות הרצוי:
(עד שההפרש בין $\ a_{n},b_{n}$ קטן מערך רצוי)

$a_{n+1}={\frac {a_{n}+b_{n}}{2}}\,$

$b_{n+1}={\sqrt {a_{n}b_{n}}}\,$

$t_{n+1}=t_{n}-p_{n}(a_{n}-a_{n+1})^{2}\,$

$p_{n+1}=2p_{n}\,$

בתום השלב האיטרטיבי מחושב הקירוב ל-π בעזרת הפרמטרים $\ a_{n},b_{n},t_{n}$ לעיל, על ידי הנוסחה:
$\pi \approx {\frac {(a_{n}+b_{n})^{2}}{4t_{n}}}\,$

ארבע ההצבות הראשונות בנוסחה נותנות:

...3.14
...3.1415926
...3.141592653589793238
...3.1415926535897932384626433832795028841971

מקורות חיצוניים

• ,PI and the AGM: A Study in Analytic Number Theory and Computational Complexity, Jonathan M. Borwein, Peter B. Borwein. 1987.