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

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

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

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

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

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

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

כאשר ו- הוא הממוצע האריתמטי-גאומטרי של ו-.

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

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

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

בתום השלב האיטרטיבי מחושב הקירוב ל-π בעזרת הפרמטרים לעיל, על ידי הנוסחה:


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

...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.