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

אלגוריתם גאוס-לז'נדר הוא אלגוריתם מהיר לחישוב הספרות של הקבוע המתמטי $\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.