ראשי > כללי > איך מחשבונים עושים חשבון? על אלגוריתם CORDIC

איך מחשבונים עושים חשבון? על אלגוריתם CORDIC

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

לא מכירים?

אז יצאתי* לבדוק איך מחשבונים עושים חשבון ולא תאמינו מה מצאתי.

*[יצאתי = חיפשתי מידע ברשת]

Casio-fx115ES
תמונה 1: מחשבון מדעי. המקור לתמונה: ויקיפדיה, לשם הועלתה על ידי המשתמש Loadmaster David R. Tribble.

***

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

טור טיילור
קופסא 2: טור טיילור.

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

אם כפל וחילוק נחשבות לפעולות 'מסובכות' על השבב, מהן הפעולות שנחשבות פשוטות ומהירות? מבלי להיכנס לסיבות לכך, אלה הן הפעולות הפשוטות: 1) חיבור וחיסור, 2) השוואת מספרים כדי לבדוק מי יותר גדול, 3) הכנסה והוצאה של מספרים לזיכרון, 4) הזזה של הנקודה הבינארית. לגבי האחרון, היזכרו כמה קל לחשב תוצאת כפל כאשר אחד הכופלים הוא חזקה של עשר. כל שעלינו לעשות הוא להזיז את הנקודה העשרונית מכיוון שאנחנו משתמשים בייצוג עשרוני. באופן דומה, בייצוג בינארי כפל בחזקות של 2 מצריך אך ורק הזזה של הנקודה הבינארית.

את הדרך לחשב את ערכן של הפונקציות הטריגונומטריות באמצעות ארבע הפעולות הפשוטות בלבד הגה ג'ק וולדר (Volder) בשנים 1956-1959 כשעבד בחברת Convair באחד מצוותי הפיתוח של מערכת המטוס B-58, שהיה מפציץ עם יכולת לעבור את מהירות הקול. מכיוון שהיה צורך לשדרג חלקים במערכת הניווט של המטוס ממעגלים אנלוגיים לדיגיטליים, עלתה דרישה לאלגוריתם מהיר לחישוב פונקציות טריגונומטריות בזמן אמת ובכמות מינימלית של חומרה. השם שנתן וולדר לשיטה שהמציא לפתרון הבעיה הוא COordinate Rotation DIgital Computer או בקיצור: CORDIC.

אז איך זה עובד?

Convair_B-58A_Hustler_in_flight
תמונה 3: מטוס מפציץ B-58 כפי שצולם בזמן תעופה ב-1967. המקור לתמונה: ויקיפדיה.

***

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

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

זוויות וסיבובים
קופסא 4: אלגוריתם ה-CORDIC. נבחר זוויות הולכות וקטנות שהטנגנס שלהם הוא חזקה של 2. מיקומי החוגה לאחר כל סיבוב מסומנים באות V. סיבוב ראשון נגד כיוון השעון בזווית הראשונה בסדרה, סיבוב שני נגד כיוון השעון בזווית השניה, סיבוב שלישי עם כיוון השעון בזווית השלישית. הקווים הכחולים מסמנים את ערכי הסינוס והקוסינוס של הזווית לאחר הסיבוב השלישי, לפי ההיטלים על הצירים x ו-y. נוסחאות הסיבוב הדרושות לחישוב ערכי הסינוס והקוסינוס כוללות בתוכן, למרבה הצער, סינוס וקוסינוס.

לאחר כל סיבוב של החוגה יש לחשב את הסינוס והקוסינוס החדשים. דמיינו שאורכו של המחוג שאותו אנחנו מסובבים הוא 1, ולכן קצהו של המחוג נע על מעגל היחידה שרדיוסו 1. מיקום הנקודה בקצה המחוג, כלומר ההיטלים של המחוג על ציר x ו-y, אלו הם ערכי הסינוס והקוסינוס של הזווית החדשה. הבעיה היא שכדי לחשב את מיקום קצה המחוג לאחר כל סיבוב אנחנו צריכים להכפיל בסינוס וקוסינוס (ראו קופסא 4 משמאל למטה). נראה שנכנסנו לבעיה מעגלית!

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

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

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

זהו, עכשיו נותר רק לעשות את החשבון של 40 סיבובים ולהגיע לתוצאה מהירה.

***

ב-1971 פרסם ג'ון וואלתר (Walther) מחברת Hewlett-Packard הרחבה והכללה לשיטה שאפשרו להשתמש בה לחשב פונקציות היפרבוליות, אקספוננטים, לוגריתמים, כפל, חילוק ושורשים. זמן קצר אחר-כך הופיעו מחשבוני הכיס המדעיים הראשונים. והנה אנחנו היום.

——————————————————–

לקריאה נוספת:

CORDIC: how hand calculators calculate, by Alan Sultan

מודעות פרסומת
  1. 10/07/2014 בשעה 9:15 am

    רעיון באמת יפה אבל מה כל כך מסובך בלחשב את עשרת המחוברים הראשונים בטור חזקות במחשבונים של היום?…

  2. 10/07/2014 בשעה 12:09 pm

    לכאורה, אין בעיה. כיום ניתן לייצר שבבים בגודל המתאים ועם כוח חישוב מתאים שיעשו את העבודה. יש כבר הרבה שנים מחשבונים בעלי יכולת מקבילה למחשב עם תוכנת matlab או משהו דומה. אני חושב שעדיין שם המשחק הוא מחיר. להערכתי השבבים של CORDIC יהיו פשוטים וזולים יותר כך שאתה יכול לקנות מחשבון מדעי מלא בשלושים שקלים. לגבי מי מהם עובד מהר יותר, אני לא יודע את התשובה.

  3. אייל מגן
    11/07/2016 בשעה 5:21 pm

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

  4. ערן הירש
    04/12/2016 בשעה 5:01 pm

    אתה יכול להדגים את השיטה ? למשל לחשב טנגנס של זוית מסוימת ?

    • 04/12/2016 בשעה 11:03 pm

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

  1. No trackbacks yet.

כתיבת תגובה

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

הלוגו של WordPress.com

אתה מגיב באמצעות חשבון WordPress.com שלך. לצאת מהמערכת / לשנות )

תמונת Twitter

אתה מגיב באמצעות חשבון Twitter שלך. לצאת מהמערכת / לשנות )

תמונת Facebook

אתה מגיב באמצעות חשבון Facebook שלך. לצאת מהמערכת / לשנות )

תמונת גוגל פלוס

אתה מגיב באמצעות חשבון Google+ שלך. לצאת מהמערכת / לשנות )

מתחבר ל-%s

%d בלוגרים אהבו את זה: