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

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

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

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

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

ב-1800, חקירותיו של גאוס על הממוצע האריתמטי גאומטרי הובילו אותו לגלות את הנוסחה הנפלאה:

$\sum _{k=0}^{\infty }2^{k}(b_{k}^{2}-a_{k}^{2})=1-{\frac {2M^{2}}{\pi }}$

כאשר $a_{0}={\frac {1}{\sqrt {2}}},b_{0}=1$ ו-$M$ הוא הממוצע האריתמטי-גאומטרי של $a_{0},b_{0}$.

תיאור אלגוריתם בראנט סלאמין

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

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

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

${\begin{aligned}a_{n+1}={\sqrt {a_{n}b_{n}}}\\b_{n+1}={\frac {a_{n}+b_{n}}{2}}\\t_{n+1}=t_{n}-p_{n}(b_{n}-b_{n+1})^{2}\\p_{n+1}=2p_{n}\end{aligned}}$

בתום השלב האיטרטיבי מחושב הקירוב ל-$\pi$ בעזרת הפרמטרים $a_{n},b_{n},t_{n}$ לעיל, על ידי הנוסחה:

$\pi \approx {\frac {(a_{n}+b_{n})^{2}}{4t_{n}}}$

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

${\begin{aligned}&3.14\ldots \\&3.1415926\ldots \\&3.141592653589793238\ldots \\&3.1415926535897932384626433832795028841971\ldots \end{aligned}}$

לקריאה נוספת

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

קישורים חיצוניים

• אלגוריתם גאוס-לז'נדר, באתר MathWorld (באנגלית)