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

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

לא מכירים?

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

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

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

***

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

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

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

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

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

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

תמונה 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