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

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

אלגוריתם גאוס-לז'נדר הוא אלגוריתם לחישוב הספרות של π .

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

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

1. ערכים התחלתיים:

$a_{0}=1,b_{0}=1/{\sqrt {2}},t_{0}=1/4,p_{0}=1$

2. חזור על ההוראות הבאות עד שההפרש בין $a_{n},b_{n}$ הוא בדייקנות רצויה.

$a_{n+1}=(a_{n}+b_{n})/2$ הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "http://localhost:6011/he.wikipedia.org/v1/":): {\displaystyle \b_{n+1} = {a_n\cdot b_n}^2} $t_{n+1}=t_{n}-p_{n}(a_{n}-a_{n+1})^{2}$

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

3. π ניתן לחישוב על ידי $a_{n},b_{n},t_{n}$ כך:

הפענוח נכשל (שגיאת תחביר): {\displaystyle \π approx (a_n + b_n)^2/4t_n}

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

                                            3.140 = π   
                                       3.14159264 = π
                                 3.1415926358979 = π