מנוע הפרשים

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

רקע[עריכת קוד מקור | עריכה]

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

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

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

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

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

קירוב פונקציות אנליטיות בעזרת פולינומים[עריכת קוד מקור | עריכה]

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

חישוב ערכי פולינומים בעזרת סדרת פעולות חיבור[עריכת קוד מקור | עריכה]

מנוע ההפרשים הוא למעשה מכונה לחישוב פולינומים. המנוע מנצל תכונה מעניינת של פולינומים: אם ידוע ערכו של פולינום ממעלה $N$ בנקודה $X_{0}$ , אפשר לחשב את ערך הפולינום בנקודה $X_{0}+\delta$ בעזרת חישוב פולינום שני, ממעלה $N-1$ , באותה נקודה, וחיבור התוצאה לערך הפולינום הראשון בנקודה. מקדמי הפולינום השני תלויים בפולינום המקורי, ובגודל הצעד. על ידי חזרה על הפעולה (כלומר חישוב הפולינום השני בעזרת פולינום שלישי, ממעלה $N-2$ וביצוע פעולת חיבור, השלישי בעזרת רביעי, וכך הלאה, עד לפולינום ממעלה 1, שהוא למעשה מספר קבוע), ניתן למעשה, לחשב את ערך הפולינום המקורי בעוד ועוד נקודות, בעזרת חזרה על סדרת פעולות חיבור בלבד, תוך שמירת תוצאות הביניים של כל פעולה, כך שישמשו בפעולות הבאות. הנושא מוסבר חלקית בהפרש חזקות, וביתר פירוט בסעיפים הבאים.

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

מנוע הפרשים הוא מכונה שמנצלת עובדה זו, כדי לחשב ערכים של פולינום ממעלה N בסדרת נקודות בהפרשים קבועים ביניהם, בעזרת פעולות חיבור בלבד. כדי לעשות זאת יש להחליט בתחילה על הנקודה הראשונה בה רוצים להתחיל לחשב, ואת גודל הצעד של הלוח: בעזרת הפולינום הראשון וגודל הצעד, ניתן לחשב את מקדמי הפולינום השני (ממעלה נמוכה ב-1 ממעלת הפולינום המקורי), בעזרת השני וגודל הצעד מחשבים את מקדמי הפולינום השלישי, וכן הלאה, עד לפולינום ממעלה 1, כלומר קבוע. כעת, מחשבים את ערכי כל הפולינומים הללו בנקודת ההתחלה, ומתחילים "להצעיד" את המנוע, כשבכל צעד מחושבים ערכי כל הפולינומים בנקודה הבאה, חוץ, כמובן, מהפולינום הראשון, ממעלה 0, שערכו הוא קבוע (ערך זה תלוי במקדמי הפולינום המקורי ובגודל הצעד שנבחר). ערכו של כל פולינום בנקודה $X_{0}+\delta$ שווה לסכום של ערכו בנקודה $X_{0}$ , עם ערך הפולינום הנמוך ממנו באותה נקודה.

הדגמת חישוב פולינום ממעלה 3 בעזרת תוצאה קודמת ופולינום ממעלה 2
נתון פולינום ממעלה 3: $P(X)=aX^{3}+bX^{2}+cX+d$ נחשב (ידנית) את ערך הפולינום בנקודה $X_{0}$ , ונקרא לערך זה $P_{0}$ . זו היא ה"תוצאה הקודמת". ערך הפולינום בנקודה $X_{0}+\delta$ הוא: $P(X_{0}+\delta )=a(X_{0}+\delta )^{3}+b(X_{0}+\delta )^{2}+c(X_{0}+\delta )+d$ נפתח את הסוגריים, ונקבל $p(X_{0}+\delta )=aX_{0}^{3}+3aX_{0}^{2}\delta +3aX_{0}\delta ^{2}+\delta ^{3}+bX_{0}^{2}+2bX_{0}\delta +b\delta ^{2}+cX_{0}+c\delta +d$ כשמחסרים מביטוי זה את הפולינום המקורי בנקודה $X_{0}$ ,כלומר $P_{0}$ , מתקבל: $p(X_{0}+\delta )=P_{0}+3a\delta X_{0}^{2}+3aX_{0}\delta ^{2}+\delta ^{3}+2bX_{0}\delta +b\delta ^{2}+c\delta$ כינוס איברים משאיר $p(X_{0}+\delta )=P_{0}+(3a\delta )X_{0}^{2}+(3a\delta ^{2}+2b\delta )X_{0}+(a\delta ^{3}+b\delta ^{2}+c\delta )$ הערכים של $a,b,c,\delta$ הם מספרים קבועים, ולכן, כאשר ידוע ערך הפולינום המקורי בנקודה $X_{0}$ , אפשר לחשב את ערכו ב $X_{0}+\delta$ , בעזרת חיבור הערך הקודם לערכו של פולינום ידוע ממעלה 2 בנקודה $X_{0}$ . מקדמי הפולינום השני תלויים במקדמי הפולינום המקורי, ובגודל הצעד. באופן דומה מפיקים פולינום שלישי, ממעלה 1, ופולינום רביעי, ממעלה 0 (כלומר מספר קבוע). מחשבים את ערכי כל הפולינומים הללו בנקודה $X_{0}$ , וכעת, ערכו של אחד מהם בנקודה $X_{0}+\delta$ הוא חיבור ערכו ב $X_{0}$ , עם ערך הפולינום הקודם ב $X_{0}$ . כל ערך, פרט לראשון (הקבוע) והאחרון (הפולינום בדרגה הגבוהה ביותר, בו אנו מעוניינים), משמש בשני חישובים: חישוב הערך הבא (כלומר בנקודה $X_{0}+\delta$ ) של אותו פולינום, וחישוב הערך הבא של הפולינום בדרגה הבאה. באופן דומה אפשר לחשב ערכו של פולינום ממעלה כלשהי בנקודה $X_{0}+\delta$ בעזרת תוצאה קודמת, וחישוב פולינום שני ממעלה פחותה ב-1.

שגיאת חישוב

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

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

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

היסטוריה[עריכת קוד מקור | עריכה]

בבג' - מנוע הפרשים מספר 1 ו-2[עריכת קוד מקור | עריכה]

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

סרטון של מנוע הפרשים מספר 2 בפעולה

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

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

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

תוך כדי ביצוע הפרויקט, בבג' המשיך לשכלל את רעיונותיו ולהמציא חדשים, ואחרי שהפרויקט הסתיים בלי תוצאה ממשית, בין 1847 ל-1855 בבג' תכנן ושרטט גרסה חדשה - "מנוע הפרשים מספר 2", מכונה שבזכות שכלולים שונים נזקקה לפחות חלקים, והייתה קטנה ופשוטה יותר לייצור, אם כי עדיין שקלה מספר טונות. בשלב זה הממשלה הבריטית סירבה לממן פרויקט נוסף, ומנוע ההפרשים מספר 2 נותר על הנייר, עד שנת 1989: מוזאון המדע בלונדון, כהכנה לציון 200 שנים להולדת בבג' ב-1991, החליט לנסות לבנות את מנוע הפרשים מספר 2. טקסטים היסטוריים רבים מכילים את הטענה שמנוע ההפרשים לא היה ניתן למימוש בטכנולוגיות ובחומרים שהיו זמינים לבבג', ועד לפרויקט הזה, זו הייתה הדעה המקובלת. ואחת ממטרות הפרויקט הייתה לבדוק, ואם אפשר להפריך, את הטענה הזו, ולכן המבצעים הגבילו עצמם לשימוש בחומרים ובאפיצויות (כלומר מידת הדיוק של החלקים המיוצרים) שהיו זמינים ב-1850. הפרויקט הסתיים בהצלחה ב-1991, ובכך הדגים שטכנית, ניתן היה לייצר את המנוע כבר במחצית המאה ה-19. הדגם שבנייתו הסתיימה ב-1991, בשינויים קלים בלבד, עדיין חסר את המדפסת. בשנת 2000 הסתיימה בניית המדפסת, ודגם מנוע ההפרשים מספר 2, מוצג ופעולתו מודגמת במוזאון (דגם שני נבנה עבור אספן פרטי, שבתמורה מימן את בניית המדפסת).

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

פר גאורג שוץ ומרטין ויברג[עריכת קוד מקור | עריכה]

היזם והממציא השוודי, פר גאורג שוץ, בהשראת עבודתו של בבג', תכנן ובנה סדרת מנועי הפרשים. המנוע הראשון נבנה בין 1837 ל-1843 בעזרת בנו, אדוורד שוץ. מנוע נוסף נבנה ב-1853^[1], והוצג בתערוכה העולמית של פריז ב-1855. שוץ המשיך לשכלל וליצור דגמים נוספים. אחד מהם, שנבנה ב-1859, נמכר שנה מאוחר יותר לממשלת בריטניה. לעומת מנוע ההפרשים של בבג', שהיה בגודל של קטר קטן, מכונתו של שוץ תוארה כ"בגודל דומה לפסנתר".

המנועים של שוץ לא היו מושלמים, ולא יכלו לייצר טבלאות שלמות. שוודי נוסף, בשם מרטין ויברג, תכנן את המכונה מחדש באופן שפתר את הבעיות, וב-1875 מנוע ההפרשים של ויברג היה מסוגל ליצור לוחות מתמטיים (למעשה, סדרת ערכים של פולינומים ידועים בנקודות ידועות, אך מבחינה מעשית היו אלו לוחות מתמטיים לכל דבר). מכונתו של ויברג הייתה קטנה יותר ממכונותיו של שוץ, וגודלה דומה לגודלה של מכונת תפירה^[2]. ויברג לא מצא קונה למכונתו, וגם לא הצליח למכור את הלוחות שהמכונה ייצרה, בגלל פגמים גרפיים. המכונה מוצגת היום במוזאון השוודי הלאומי למדע וטכנולוגיה בסטוקהולם.