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

מתוך ויקיפדיה, האנציקלופדיה החופשית
תוכן שנמחק תוכן שנוסף
SieBot (שיחה | תרומות)
מ בוט מוסיף: nl:Algoritme van Gauss-Legendre
Alexbot (שיחה | תרומות)
מ בוט משנה: en:Gauss–Legendre algorithm
שורה 35: שורה 35:
[[קטגוריה:אלגוריתמים]]
[[קטגוריה:אלגוריתמים]]


[[en:Gauss-Legendre algorithm]]
[[en:Gauss–Legendre algorithm]]
[[es:Algoritmo de Gauss-Legendre]]
[[es:Algoritmo de Gauss-Legendre]]
[[ja:ガウス=ルジャンドルのアルゴリズム]]
[[ja:ガウス=ルジャンドルのアルゴリズム]]

גרסה מ־11:43, 28 ביוני 2008

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

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

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

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

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

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

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


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

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