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

שגיאות פרמטריות בתבנית:לשכתב
פרמטרי חובה [ נושא ] חסרים

פרק זה טעון שכתוב. אנא תרמו לוויקיפדיה ועזרו לשכתב אותו. ייתכן שתמצאו פירוט בדף השיחה.

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

האלגוריתם מבוסס על שילוב עבודותיהם של קרל פרידריך גאוס (1855-1777) ושל אדריאן-מארי לז'נדר (1833-1752), יחד עם אלגוריתמים מודרניים לכפל והוצאת שורש ריבועי. האלגוריתם הינו איטרטיבי מטבעו ומבוסס על החלפה חוזרת של שני מספרים בממוצעים האריתמטי והגאומטרי שלהם, כדי לבצע חישוב מקורב של הממוצע האריתמטי-גאומטרי שלהם.

הגרסה שמוצגת כאן ידועה כאלגוריתם בראנט-סלאמין, בשל העובדה שהאלגוריתם נתגלה מחדש, באופן בלתי תלוי, על ידי מדען המחשבים ריצ'רד בראנט והמתמטיקאי יוג'ין סלאמין ב-1975. בתאריכים 18 עד 20 בספטמבר בשנת 1999, נעשה שימוש באלגוריתם לחישוב 206,158,430,000 הספרות העשרוניות הראשונות של $\pi$.

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

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

$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