ב-Online
 
 
 
 
 
 
 
לפרק את הבייט 
לפרק את הפיי 
 
לפרק את הבייט |
 

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

 
 
 
 
 
 
 
 
 
 
 

אתמול ציינו חובבי המתמטיקה בכל העולם את יום הפיי – הארבעה-עשר במרץ, שנכתב בפורמט האמריקני 3.14 כמו תחילתו של המספר המפורסם. אין ספק שבעוד חמש שנים החגיגות יהיו סוערות במיוחד (בכל זאת, 3.14.15), אך בינתיים, הנה עובדה מעניינת באדיבות ויקיפדיה: נכון להיום, החישוב המדויק ביותר של פיי מגיע לכמעט 2.7 טריליון ספרות אחרי הנקודה. רק כדי לשים דברים בפרופורציה, אם קובץ עם כל הספרות הללו היה מוצע להורדה בפורמט טקסט פשוט והייתם מורידים אותו בקצב מלא של 1.5 מגהביט לשניה, היו נדרשים לכם כמעט 167 ימים כדי להשלים את ההורדה (בהתחשב בכך שבפיי אין שום מחזוריות, מישהו רוצה להעריך כמה זמן היה נדרש להורדת הגרסה המכווצת?).

 

64 ביט זה כלום

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

חיבור

 

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

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

 

חיסור

 

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

נניח שאנו רוצים להפחית שני מספרים חיוביים בעלי ארבע ספרות האחד מהשני. נקרא לראשון AAAA ולשני BBBB. תוצאת החישוב הרצויה היא AAAA – BBBB. אם נוסיף בתוך התרגיל הפשוט הזה עשרת אלפים ולאחר מכן נסלק אותם, לא יקרה כלום, נכון? אז הנה, AAAA + 10000 – BBBB – 10000, או בניסוח אחר AAAA + (10000 – BBBB) – 10000, או בניסוח עוד יותר אחר AAAA + (9999 – BBBB + 1) – 10000. הסרבול המשונה הזה נותן לנו שני דברים. ראשית, קל מאד לחשב את 9999 מינוס BBBB: צריך רק להפחית כל ספרה B מהספרה 9. כך 0 תהפוך ל-9, הספרה 3 תהפוך ל-6 וכו'. גם את זה, כמובן, קל מאד לבצע בעזרת טבלה מוכנה מראש ולחסוך את פעולות החיסור הבסיסיות. שנית, קל גם לחסר את עשרת האלפים בסיום, מכיוון שאם התוצאה היא בת חמש ספרות פשוט מקצצים את הראשונה, ואם לא – הופכים את הסימן. לסיכום, התרגיל המקורי שלנו הופך לפעולה שמורכבת משתי פעולות חיבור ושתי פונקציות עיבוד פשוטות שאינן חיסור, ומיותר לציין שאין מגבלה של ארבע ספרות דווקא – זה היה לצורך הדוגמה בלבד.

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

 

כפל

 

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

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

 

חילוק

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

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

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

כל הזכויות שמורות 2011 © נענע 10 בע"מ
 
 
 
 
כל הזכויות שמורות © Nana10 בע"מ
Video powered by