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

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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