שפת מכונה | טור 11

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

על אלגוריתם מצרי עתיק ועל למה חשוב להרגיז מתמטיקאים

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

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

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

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

בפעולות מחשב הנוגעות לקריפטוגרפיה, למשל, המספרים הנכפלים עשויים להיות עצומים. אם נכפיל שני מספרים בני עשר ספרות בשיטת הכפל הארוך, נידרש בעצם למאה פעולות הכפלה (אנו מכפילים הרי עשר ספרות בעשר ספרות); "אלגוריתם קרצובה" יעשה זאת ב-38 פעולות בלבד. שיפור משמעותי של 62%, שילך ויגדל ככל שמספר הספרות יעלה. כיצד מחולל "אלגוריתם קרצובה" את הקסם הזה? באמצעות "הפרד ומשול", כפי שמכונים אלגוריתמים מסוגו. קרצובה הבין כי ניתן להפריד את כל אחד משני גורמי המכפלה למעין חלקיקי יסוד, ואז להכפיל אותם ביניהם תוך דילוג על פעולות מיותרות רבות. עבור בני אנוש זוהי דרך מסורבלת ביותר, אך עבור המחשב, האדיש לסרבול – כל עוד ההוראות שהוא מקבל הן ברורות – "אלגוריתם קרצובה" יחסוך מספר משמעותי של פעולות ביניים, וכך יגיע אל התוצאה מהר יותר מאלגוריתם הכפל הארוך, בהינתן אותה חומרה.

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

מתמטיקאי שלישי, יאקוב טרכטנברג, מצא את עצמו כלוא במשך שנים במחנות אסירים מבלי שיהיו לו אפילו עפרון ופיסת נייר שישמשו אותו באופן קבוע. כדי לשמור על שפיות הוא בנה לעצמו עולם מתמטי משל עצמו, ובו ערך חישובים אריתמטיים קשים, שכללו בין השאר הכפלה של מספרים בעלי ספרות רבות. לשם כך פיתח טכניקות שאינן דורשות דבר, מלבד זיכרון אנושי. כמו קולמוגורוב וקרצובה, גם לו היה בסיס איתן: הוא נולד באודסה ב-1888, סיים את לימודיו בסנקט פטרסבורג בהצטיינות יתרה ומונה בגיל צעיר למנהל במספנות העיר. מהפכת אוקטובר גדעה את נבטי הקריירה שלו, ובשל העובדה שהיה מן הפעילים הבולטים באגודה התנדבותית שפרחה בעידוד הצאר, נאלץ להימלט לגרמניה. הוא יצר לעצמו שֵׁם בקהילת הגולים של ברלין, פיתח טכניקות להוראת שפות וערך כתב עת, אלא שגם שם, בהיותו פציפיסט, הפך עם עליית הנאצים לדמות בלתי רצויה. הוא נטש את ברלין לטובת וינה, וכשאוסטריה סופחה התגלגל הלאה ליוגוסלביה, שם נלכד. עד 1944 היה אסיר במחנות השונים של הרייך, ורק אז נחלץ בעור שיניו.

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

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

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

פורסם במקור ב-23.04.2020

בועז לביא הוא תסריטאי, יוצר קומיקס ומרצה על אלגוריתמים כותבים.

#עלייתהמכונות #שפתמכונה #בועזלביא #קורונה