פיתון/חישוב נומרי בשפת פייתון/שבוע 2

הרצאה 3:

הערות להרצאה בנקודה צפה

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

1

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

1457 ≜ 1000 + 400 + 50 + 7 = 1 ∗ 103+ 4 ∗ 102+ 5 ∗ 101+ 7 ∗ 100.

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

2 ∗ 101+ 3 ∗ 100 4 ∗ 51+ 3 ∗ 50 = 435 2310 = 2 ∗ 32+ 1 ∗ 31+ 2 ∗ 30
=2123
1 ∗ 24+ 0 ∗ 23+ 1 ∗ 22+ 1 ∗ 21+ 1 ∗ 20 = 101112. נציין שבסיס המיקום 2, מערכות מספר 3 ו-10 נקראות בהתאמה בינארי, טרינרי ועשרוני.

1.2 הערות היסטוריות קצרות על מערכות מספרים*

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

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

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

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

2	מערכת נקודות צפה
2.1	הגדרת FPS

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

2

משפט 2.1 (הרחבה עשרונית). עבור כל מספר ממשי לא שלילי x, קיים k ∈ N ורצף dn ∈ {0' ', 1, . . . , 9} כזה ש

x = k +

∞	dn(10)−n.
n=1

בנוסף, או שהרצף dn הוא ייחודי, או שקיים רצף שמסתיים במחרוזת אינסופית של 0 ורצף המסתיים במחרוזת אינסופית של 9' ס.

להוכחה נגישה לתוצאה זו, עיין בסעיף 2.16 של היסודי של קנת רוס

ניתוח: Theory of Calculus (משאב אלקטרוני זמין דרך אתר ספריית סטנפורד). נציין שהבחירה בבסיס 10 במשפט 2.1 היא שרירותית: תוצאות אנלוגיות מתקיימות עבור כל בסיס שלם β > 1. (בבסיס β, כל ספרה dn שייכת לקבוצה {0, 1, . . . , β − 1}).

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

מתוך מחשבה על משפט 2.1, אנו מתקנים בסיס β ומספרים שלמים p, m ו-M, ומגדירים את ה-FPS כקבוצה של כל הצירופים של הצורה.

±

פ n=1

dnβ−n

× βe,

עם dn ∈ {0, 1, . . . , β − 1}, ו-m ≤ e ≤ M. נציין כי ניתן לבטא לחילופין את השילובים הניתנים על ידי הסכום לעיל

±(0.d1d2 . . .dp)β × βe. (1)

אנו מדגישים שה-FPS מוגדר על ידי (β, p, m, M). אנו מתייחסים לאפשרויות הנפוצות בסעיף 2.4. לצורך המחשה, ניקח β = 10.

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

0.1234 × 10−2=.001234

0.1234 × 101=1.234

0.1234 × 104=1234.

0.1234 × 108=12, 340, 000.

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

2.2 קירוב סופי!

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

3

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

הערך הספציפי של הדיוק p של FPS עשוי להשתנות מיישום למימוש ותלוי בחומרת המכונה. אנו מתייחסים להתפתחות ההיסטורית ולבחירות הסטנדרטיות הנוכחיות של p בסעיף 2.4.

בכל מקרה, p הוא תמיד סופי וזה במידה רבה מסביר את השגיאה בקירוב המציאות √7 או לפי מצופים. קחו למשל את המספר הרציונלי 1/3 (שלא לדבר על אי-רציונלי כמו π כמו π). לפי משפט 2.1, ההתרחבות העשרונית הייחודית שלו היא

1
3 =

∞	3(10)−n,
n=1

או שווה ערך, 1/3 = 0.¯3, כאשר סרגל המעבר מציין שכל ספרה בהרחבה היא 3. עבור any בחירת p , יש לנו

∞	3(10)−n−
n=1

פ n=1

3(10)−n= ϵ > 0.

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

שנית, כל FPS הוא סופי. לכל FPS יש את האלמנט הקטן והגדול ביותר. באופן מיוחד,

0.1β × β−m≤ p−1 dnβ−n × βe ≤ 0.(' 'β − 1)(β − 1) · · · (β − 1)β × βM,n=1 שכן לפי הגדרה כל צף ±(0.d1d2 . . .dp)β × βeמספק m ≤ e ≤ M ו-1 ≤ dn ≤ β − 1. לעומת זאת, הממשיים אינם מוגבלים: עבור כל מספר ממשי, קיים ממשי קטן יותר ויותר.

הערכים הספציפיים של m ו-M עשויים להשתנות מיישום למימוש ותלויים בחומרת המכונה. אנו מתייחסים לבחירות הסטנדרטיות הנוכחיות בסעיף 2.4.

בכל מקרה, הגבולות m ו-M ב-exponenent e הם סופיים וזה משלים את ההסבר של השגיאה בקירוב המציאות על ידי מצופים. הסופיות של m גורמת לאזור של תתת זרימה, הרווח שבין אפס לציפה הגדולה הבאה. הסופיות של M מולידה את אזור הגלישה, החלק של הקו האמיתי מימין לציפה הגדולה ביותר.

לדוגמה, שקול FPS F עם β = 10, m = −4 ו-M = 8. הקבוע של פלאנק, h ≈' ' 6.63 × 10-34J · s, ואורך הגל של אור כחול, ≈ 7 × 10- 7m, שוכבים באזור התת-תת של F ויש להעריך אותם ב-0 או 10-5. באופן דומה, F לא יכול לייצג את העושר של ביל גייטס, ≈ $8.91 × 1010, שלא לדבר על המספר של Avogadro, ≈ 6. 02 × 1023mol-1. ערכים כה גדולים, באזור הגלישה של F, יהיו משוערים ב-108.

2.3 אזהרה: שגיאת קירוב מאייתת אסון*

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

4

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

כמה שנים מאוחר יותר, הצפה גרמה לעולם לפחד משחר ה-1 בינואר, 2000. רוב המחשבים ששמרו על רישומים שנתיים השתמשו ב-FPS עם שתי ספרות של דיוק (1985, למשל, תועד כ-85). שנת 2000 הייתה מעבר לקיבולת של מערכות כאלה, שכן 00 מייצגת 1900. אזעקה בינלאומית הפכה לנפוצה מכיוון שמערכות כאלה - בשימוש בבנקים וממשלות - היו צפויות לקרוס והתפתחו מאמצי שדרוג קדחתניים. אנציקלופדיה בריטניקה מעריכה שיותר מ-300 מיליארד דולר הושקעו בחיסול מה שנודע כ"באג Y2K". קוראים המעוניינים עשויים למצוא עוד ב: ו.

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

2.4 סטנדרטים*

אנו מתחילים את החלק הזה בהנעת הבסיס 2 ברוב המכריע של יישומי FPS מעשיים.

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

(בשל מגבלות פיזיות והשפעות של הפרעות קוונטיות, הטכנולוגיות הנוכחיות מאפשרות רק תצורה אמינה של טרנזיסטורים דו-מצביים. זכור שמעבדים חדישים מיוצרים בתהליכים של 14 ננומטר ושאפילו מעבדי סמארטפונים מכילים מיליארדי טרנזיסטורים! ) עם זאת בחשבון, כדאי להציג את המושגים של bit ובייט. bit הוא ספרה בינארית יחידה: 0 בודד או 1 במחרוזת בינארית. byte הוא מחרוזת של 8 סיביות. אולי אתה מכיר את המושג מגה- (MB) או ג'יגה-בייט (GB). מבחינה טכנית, 1MB = 106B, ו-B מייצג בייט.

לאחר ששקלנו את הבחירה הסטנדרטית של הבסיס, אנו פונים לתצורות סטנדרטיות של p, m, M ביישומים מעשיים של FPS. הסטנדרטים הללו שרירותיים במידה מסוימת במובן שהם הרבה יותר תוצאה של התפתחות היסטורית מאשר של אופטימיות תיאורטית או מגבלה פיזית. אכן, היו הרבה חוסר עקביות וויכוחים במהלך שנות ה-70 ותחילת שנות ה-80 לגבי התצורה ה"נכונה" של ה-FPS המתהווה. יצרנים שונים השתמשו בדייקנות שונים והקצו כמויות שונות של זיכרון לאחסון של מספרי נקודה צפה, מה שהוביל לאי תאימות בין פלטפורמות ולתוצאות שונות לאותו חישוב (בשל ההבדל בשגיאות הקירוב המוענקות על ידי ה-FPS המשתנים). המאמצים לסטנדרטיזציה של יישומי FPS הגיעו לשיאם במאמר היסודי IEEE-754 בשנת 1985. ערכת הסטנדרטים התקבלה בינלאומית y בשנת 1989.

כעת אנו מסתכלים מקרוב על התקנים שהוגדרו על ידי IEEE-754. זכור את ביטוי 1, אשר המעריך e. אם אנחנו רוצים לייצג כל צף במספר קבוע N של ביטים, עלינו להחליט כיצד לקבוע שלכל רכיב של FPS יש שלושה חלקים: סימן s, סימן ד 1d2 · · · dp, וכן הקצאת ה-N ביטים בין שלושת המרכיבים שלו.

התכתבות עם 0 ו-1. ברור שיש צורך בסיביות p כדי לקודד את המובהק. ברגע שנתקן p, או s = 1 או s = -1, כך שניתן לקודד s בסיבית אחת: אנו מציבים את המצבים ±1 ב-bective עשוי להשתמש בסיביות הנותרות N − p − 1 כדי לקודד את המעריך. שים לב שתכנון ה-FPS בצורה זו מגדיר באופן מרומז את הגבולות m ו-M על המעריך כמספרים השלמים הקטנים והגדולים ביותר המיוצגים ב-N − p − 1 סיביות.

5

ה-IEEE-754 הגדיר את המושגים של דיוק יחיד וכפול על ידי הצגת שני דגמי FPS שתוכננו כך. ה-FPS דיוק יחיד משתמש ב-32 סיביות כדי לייצג את האלמנטים שלו וה-דיוק הכפול FPS משתמש ב-2 × 32 = 64 סיביות. בשני המקרים, הסימן מקודד בסיבית הראשונה, המובהק בסיביות הp הבאות, והמעריך בסיביות הנותרות. ל-FPS דיוק יחיד יש 23 ספרות בינאריות של דיוק, והוא משתמש ב-8 סיביות עבור המעריך. כך, למשל, M = 127 במקרה זה.

למערכת הדיוק הכפול יש 52 ספרות של דיוק, והיא משתמשת ב-11 ספרות עבור המעריך.

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

דיוק. תקן 1985 עודכן כך שיכלול דיוק מרובע (128 סיביות) FPS ומערכות סיביות גבוהות אף יותר, שעליהן לא נדון כאן. לבסוף, אנו מזכירים שמלבד צפים, או סוגי נקודה צפה, ה-IEEE-754 הגדיר גם סוגי נתונים מיוחדים אחרים. לדוגמה, הוא הגדיר את סוגי int8, int32 ו-int64. כפי ששמותיהם מרמזים, ניתן להשתמש בסוגי נתונים אלו אך ורק לאחסון מספרים שלמים, והם מספקים בהתאמה 8, 32 ו-64 סיביות לייצוג שלמים. כך, למשל, סוג int8 הוא המתאים ביותר כאשר רק מספרים שלמים קטנים הם. קוראים מעוניינים יכולים לוודא שה-FPS המשמש את MATLAB במכונות שלהם עומד בקנה אחד עם הנדרש (בטווח -128 עד 127).

תקני IEEE על ידי הפעלת הקוד הבא:

1% ברמת דיוק, יש לנו

2 log2 ( eps ( ' s i n g l e ' ) )

3% נתונים בינאריים של נתונים.

4

5%בדיוק כפול, יש לנו

6 log2 ( eps ("כפול"))

7% דגים בינאריים של דרכי מידע.

3 מאפיינים ודקויות של FPS

3.1 אחסון אמיתי: שגיאת סיבוב

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

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

קיצוץ (או חיתוך) מורכב מאחסון רק את הספרות p הראשונות בהרחבה העשרונית של מספר. עיגול, כפי ששמו מרמז, מורכב מעיגול ההרחבה העשרונית לp ספרות משמעותיות. נסמן מקבילת נקודה צפה קצוצה של x ב-flchop(x) ואת המקבילה המעוגלת ב-round(x). לדוגמה, אם p = 7,

מאז√2 ≈ 1.41421356 . . ..

chop(√2) =0.1414213 × 101

round(√2) =0.1414214 × 101,

6

1. מצא מקבילות לנקודה צפה ˜x = fl(x) ו-˜y = fl(y).

2. חשב z = ˜x@˜y בחשבון מדויק.

3. מצא שווה ערך לנקודה צפה ˜z = fl(z) ופלט.

לדוגמה, שקול תוספת דיוק סופית. במקרה זה נחליף את @ בדיון לעיל ב-+. למען הפשטות, שקול בסיס של 10 FPS עם ארבע ספרות של דיוק ונניח שx = 0.01234431 ו-y = 98.76321. אנו מוצאים במהירות ש-˜x = fl(x) = 0.1234 × 10−1ו-˜y = ( y) = 0.9876 × 102. לאחר מכן, נבצע את החיבור ˜x + ˜y בחשבון מדויק. יישור ˜x ו-˜y אנכית ביחס לנקודה העשרונית ולאחר מכן הוספת עמודות אחר עמודות תשואות

.01234
+ 98.76

98.77234

לבסוף, אנו מחשבים (98.77234) = 0.9877 × 102 ומוציאים אותו כתוצאה.

נקבל תחילה ˜x = (x) ו-˜y = (y). לאחר מכן אנו מיישרים את הספרות בצורה אנכית ומכפילים כרגיל. כפל דיוק סופי מתבצע באופן דומה, ואולי הוא פשוט יותר. בהינתן x, y ∈ R, בשלב הבא נוסיף את המעריכים (באמצעות ההליך המתואר לעיל). לבסוף, אנו מעגלים את המוצר והפלט. עם x ו-y כמו בדוגמה של התוספת למעלה, יש לנו
0.1218 × 101,12.186984 × 10-1 עם חיתוך (0.1234 × 10-1) ∗ (0 .9876 × 102) =  = 0.1219 × 101, עם עיגול.

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

((x + y) + z) ̸= fl(x + (y + z))) .

כדי להמחיש נקודה זו אנו רואים למען הפשטות בסיס של 10 FPS עם ארבע ספרות של דיוק המשתמש בקיצוץ. תן x = −1.234, y = 1.234, z = .0009999. ואז ((x + y) + z) = (0 + z) = 0.9999×10 −3. עם זאת, אם נוסיף תחילה y+z, נראה כי (y+z) = (0.1234× 101+0.9999×10−'3) = (1.2349) = 0.1234 × 101, מאז ל-FPS יש 4 ספרות של דיוק. לָכֵן,

((x + y) + z) = 0.9999 × 10−3= 0 = fl(x + (y + z)).

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

1% אובדן של דוגמה

2 ( −1.0 + 1.0) + 2ˆ(−53)
3 ( −1.0) + (1.0 + 2ˆ(−53) )

למרות ששני הקווים מבטאים את אותה פעולה מתמטית, רק אחד מהם מחזיר 0!

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

9

4.2 השלמה של שניים*

בחלק זה אנו מציגים רעיון מעניין קריטי לפיתוח ה-FPS. הרעיון של המשלים של שניים ממיס את הצורך ליישם חיסור בנפרד מהחיבור. אנו מדגים רעיון זה באמצעות כמה דוגמאות באמצעות הסוג int8, לשם הפשטות (זכור את סוגי הנתונים החלופיים שהוזכרו בסוף סעיף 2.4). למען השלמות, נציין שוב שסוג int8 יכול לייצג רק מספרים שלמים בטווח -128 עד 127. בסעיף 2.4 הזכרנו שסימן של מספר מקודד בסיבית המובילה או הסיבית המשמעותית ביותר (MSB) של הייצוג שלה. בהקשר של int8, זה אומר שמספרים שלמים חיוביים (עם MSB = 0) תופסים את הטווח 0 עד 127 בייצוג, בעוד שמספרים שלמים שליליים (עם MSB = 1) ממלאים את הטווח 128 עד 255. השלמה של שניים מציע שנסדר את המספרים השלמים השליליים בסדר הפוך: -1 לוקח את הייצוג של 255, -2 את זה של 254, וכן הלאה, עד -128. ליתר דיוק, תוך שימוש בהשלמה של שתיים, המספר המיוצג על ידי d1d2 . . . ל-d8 יש את הערך

8
dn2n− d127.

n=2

לדוגמה, int8(−1) = 11111111, int8(−2) = 11111110, ו-int8(−128) = 1000000. עם הסידור החכם הזה, אנחנו יכולים ליישם חיסור באמצעות מנגנון החיבור שתיארנו בסעיף 4.1. בעצם, אנו מחשבים הבדל באמצעות בעיה מקבילה: x − y ≜x + (−y). לדוגמה, 1 − 1 הופך

00000001 +11111111 100000000

.

אנו מקבלים את התשובה הנכונה, 0, על ידי התעלמות מה-MSB. באופן דומה, אנו מחשבים 4-3 באמצעות התוספת

00000100	.
+ 11111101
100000001

שוב התעלמות מה-MSB נותנת 1, התשובה הנכונה.

4.3 יישום מעשי**

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

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

הנוכחות של זרם מייצגת 1 והיעדרו 0. המפתח לסעיף זה טמון בהשוואה ל-1 למצב "מופעל" ול-T הבוליאני, ולהשוות 0 למצב "כבוי" ו-F בוליאני .

אנחנו יכולים לארגן טרנזיסטורים כדי לבנות שערים לוגיים, אשר מיישמים פיזית יחסים לוגיים כמו ∧, ⊕ ו-¬. בדומה ליחסים ∧, ⊕ ו-¬, השערים הלוגיים המתאימים מקבלים שני אותות קלט ומשלבים אותם לפלט יחיד לפי כלל מוגדר. למשל, שער ה-AND מיישם את היחס ∧ והוא מוציא זרם רק אם שני מסופי הכניסה שלו מקבלים זרם. היישום משקף את היחס A ∧ B = T רק אם A = B = T. באופן דומה, ה

10

שער XOR (בלעדי OR) מיישם את היחס ⊕ והוא מוציאזרם כאשר בדיוק אחד ממסופי הכניסה שלו מקבל זרם. זה משקף את העובדה שA⊕B = T רק אם A = T ∧B = F או A = F ∧ B = T. אנחנו יכולים גם לארגן שערים לוגיים לבניית מעגלים מורכבים יותר. בפרט, נוכל לשלב שער XOR עם שער AND כדי לבנות חצי adder, אשר מיישם פיזית תוספת סיביות בודדת.

חצי האפעה בנוי באופן הבא. תן A ו-B לסמן את שני סיביות הקלט. פיזית, כל אחד מיוצג על ידי חוט. כפי שתואר לעיל, החוט המייצג את A נושא זרם רק אם A = 1, ובדומה לחוט השני. במוסיף החצי אנו מחברים גם A וגם B למסופי הקלט של שערי XOR ו-AND. אנו אומרים שהפלט S של שער ה-XOR הוא סיבית ה-sum והפלט C של שער ה-AND הוא סיבית ה-carry (שימו לב שהסכום של שני סיביות בודדות עשוי לתפוס למעלה לשתי ביטים). איור 1 מציג את סכימת המעגל.

קובץ:Vertopal 811a6a975eb941cfa597972e380f96d2/media/image1.png

איור 1: סכימה של מעגל חצי מוסיף. הסמל העליון מציין את שער XOR. מקור: .

פירוש CS כמחרוזת בינארית מניב את הסכום A + B. בואו נבחן את כל ארבעת המקרים האפשריים. אם A = 0 ∧ B = 0, אז A + B = 00. מכיוון ששער AND מוציא זרם רק אם שתי הכניסות פועלות, C = 0. מכיוון ששער ה-XOR מוציא זרם רק אם קלט אחד בדיוק "פועל", יש לנו S = 0. לכן A + B = 00 = CS' '. המקרים A = 1 ∧ B = 0 ו-A = 0 ∧ B = 1 זהים בבירור ואנו מתייחסים רק לראשונים. במקרה זה A + B = 01. מכיוון שB הוא "כבוי", C = 0 ומכיוון שקלט אחד בדיוק הוא "מופעל", S = 1. לכן A + B = 01 = CS. לבסוף, אם A = 1 ∧ B = 1 אז A + B = 10. מכיוון ששתי הכניסות הן "מופעלות", C = 1 ו-' 'S = 0, נותן A + B = 10 = CS.

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

5	למה שיהיה אכפת לך?
5.1	סדר פעולות

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

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

11

מקבילות הנקודה הצפה שלהם ˜aij = (aij), כמתואר בסעיף 3.1. לכן, הקלט לכל שיטה מספרית שנועדה לפתור Ax = 0 הוא למעשה ˜A, ולא A! אנו אומרים ששיטה מספרית היא יציבה אם היא מוציאה פתרון ˜x∗קרוב לפתרון האמיתי x∗. במקרים רבים עיצוב אלגוריתם הוא המפתח ליציבות. כפי שממחיש הדוגמאות בסעיף 5.2, פשוט סדר מחדש של חישובים יכול להביא יציבות לשיטה.

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

5.2 דוגמאות/איורים

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

אנו מפרטים תופעה חשובה שאנו נתקלים בה לעתים קרובות. קחו בחשבון שני מצופים ˜x ו-˜y ששווים בתוך הספרה האחרונה שלהם. ההבדל שלהם ˜z = (˜x− ˜y) = ˜x− ˜y תהיה בעלת ספרה משמעותית אחת בלבד למרות שאין שגיאת סיבוב יופק בחיסור. שימוש ב-˜z בחישובים הבאים יגביל בדרך כלל את התוצאה שלהם לספרה אחת נכונה. יש אובדן בלתי הפיך של מידע ואנחנו קוראים לזה ביטול קטסטרופלי. ביטול קטסטרופלי מוביל בדרך כלל לאי יציבות מספרית ואנו שואפים להימנע מכך על ידי סידור מחדשמכניסים את סדר הפעולות.

דוגמה 5.1 (הערכת פונקציות, נלקחה מבריידי). בדוגמה זו, אנו מעריכים את הפונקציה f(x) = ex- cos x − x בערכים קרובים ל-x = 0. מכיוון ש-exו-cos x שניהם נוטים ל-1 בתור x →, עשויות לפעול 0 שיטות מספריות תמימות לביטול קטסטרופלי.

לפני שאנחנו באמת מחשבים את הערכים, אנחנו משתמשים בכלים מניתוח בסיסי כדי לקבוע למה אנחנו צריכים לצפות. בתור התחלה, שים לב שf הוא חלק מאוד מכיוון שהוא ניתן להבדלה אינסופית. לאחר מכן, שים לב שf(0) = 1 − 1 − 0 = 0. מכיוון שf(x) = ex+ sin x − 1 > 0 עבור x ∈ I = (0, π) כי ex> 1 ו-sin x > 0 ב-I, אנו יודעים ש-f עולה ב-I. בנוסף, מכיוון שex< 1 ו-sin x < 0 עבור משמאל לאפס ומתגבר מימין לו, אנו מסיקים שx = 0 הוא השורש היחיד של f ב-x ∈ I'= (−π, 0) יש לנו את ה-f′(x) < 0 ולכן 'f פוחת ב-I. מכיוון שf הוא מרווח פוחת (π, pi). לבסוף, אנו רואים שf′′(x) = ex+ cos x > 0 קרוב לאפס, כך ש-f הוא קעור. נקודות ברמת דיוק כפולה בתקן IEEE. המגמה הכוללת בגרף עולה בקנה אחד עם איור 2 שלנו מחשב ישירות ערכים של f במרווח [−5, 5] × 10- 8, ב-1001 ניתוח ברווח אחיד, אך ברור שהפרטים העדינים (החלקות) אינם.

אנו מציעים חישוב חלופי שיניב תוצאות טובות יותר בדיוק סופי. תחילה אנו מעריכים את f לפי פולינום מקלאורין באופן אנליטי, ולאחר מכן אנו מעריכים את פולינום הקירוב באופן מספרי. מזכירים את סדרת Maclaurin עבור תשואות ex ו- cos x

f(x) =ex- cos x − x = 1 + x +x22 + x36 + x424 + O(x5) − 1 ' '−x22 + x424 + O(x6) =x2+x36 + O( x5) = x2(1 + x6 ) + O(x5). − x

− x

12

קובץ:Vertopal 811a6a975eb941cfa597972e380f96d2/media/image2.png

איור 2: גרף של הפונקציה f(x) = ex-cos x-x מחושבת בדייקנות כפולה בתקן IEEE.

הקורא המתעניין עשוי להראות שהשגיאה היחסית בשימוש בפולינום האחרון כדי להעריך את f ב-[−5, 5] × 10- 8הוא פחות מ-10-24. לכן, הפולינום מקרוב את f לדיוק המכונה בדייקנות כפולה בתקן IEEE (ראה סעיף 2.4). העלילה באיור 3 מאשרת הערכה זו.

דוגמה 5.2 (סדר פעולות בהערכות פונקציות). במקרה זה אנו מעריכים את הפולינום pc(x) = (x− 10)9ליד x = 10. זכור את הערך ושימו לב שהוא מבטיח את השוויון

pe(x) = x9- 90x8+ 3600x7− 84000x 6+ 1, 260, 000x5- 12, 600, 000x4

+ 84, 000, 000x3− 360, 000, 000x2+ 900,' ' 000, 000x − 1, 000, 000, 000

= (x − 10)9.

ברמת דיוק כפולה סטנדרטית על ידי הערכה ישירה ב-1001 נקודות ברווח שווה. אנו שמים לב שבאיור 4 מוצגת עלילה של השגיאה היחסית |pe(x)−pc(x)|/|pe( x)| על פני המרווח [9, 11] אריתמטיקה מדויקת מחושבת, השגיאה היחסית צריכה להיות אפס בכל המרווח (למעט ב-x = 10 שבו היא לא מוגדרת) . שימו לב לסולם הלוגריתמי על הציר האנכי, המציין שהחישוב של pe מדויק עד אפס ספרות כאשר x קרוב מאוד ל-10. נציין שכאשר x קרוב ל-10 הערכה ישירה של הפולינום המורחב pe מציגה ביטול קטסטרופלי מזיק במיוחד, שכן היא כוללת חיסור של מספרים גדולים (בסדר גודל של 1011) הקרובים מאוד זה לזה בגודלם. ההערכה של הצורה הקומפקטית pc אינה כרוכה בפעולות כאלה, ולכן היא הרבה יותר יציבה.

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

13

קובץ:Vertopal 811a6a975eb941cfa597972e380f96d2/media/image3.png

איור 3: גרף של הקירוב f(x) ≈ p(x) = x2+x 36מחושב בתקן IEEE דיוק כפול.

שקול את העלילות הבאות. איור 5 מציג את התרשים של הפונקציה

f(x) = log(1 + x) x − 1

על פני המרווח J = [−8u, 8u] מחושב בדייקנות כפולה על ידי הערכה ישירה ב-1001 נקודות ברווח שווה, כאשר u מציין תקן מכונת דיוק כפולה אפסילון. איור 6 מציג את התרשים של הפונקציה
g(x) = log(1 + x)
(1 + x) − 1− 1
על אותו מרווח ומחושב באותו אופן. למרות שf ≡ g מתמטית, העלילות די שונות. בפרט, הערכים המוצגים באיור 5 הם בסדר גודל של 1 ואילו אלה באיור 6 הם בסדר גודל של 10-15!

הכמה הראשוניםמונחים של סדרת Maclaurin של log(1 + x) מציעים שהעלילה באיור 6 ממחישה טוב יותר את ההתנהגות של f קרוב לאפס:

log(1 + x)	− 1 = −x2 + O(x2).
איקס

דוגמה זו ממחישה ביטול "קסום". כדי להעריך f ו-g, נוסיף תחילה 1+x. מכיוון שכל x ∈ J קטן בהשוואה ל-1, החיבור בעצם מעגל את x, וגורם לאובדן דיוק רב (כ-8 ספרות בדייקנות כפולה). הערכת הלוגריתם מוגבלת ל-8 ספרות לכל היותר של דיוק. מכיוון ש-x עדיין מכיל את כל 16 הספרות של דיוק, הערכת המנה יומן (1 + x)/x מובילה לסטייה גדולה מהערך התיאורטי בגלל ההבדל בדיוק של המונה והמכנה. זה מסביר את השגיאה העצומה באיור 5.

14

קובץ:Vertopal 811a6a975eb941cfa597972e380f96d2/media/image4.png

איור 4: גרף של שגיאה יחסית |pe(x)−pc(x)|/|pe(x) | מחושב בדייקנות כפולה סטנדרטית של IEEE.

למכנה המעובד יש דיוק זהה למונה ולכן המנה יכולה. הערכת g נמנעת שגיאה זו על ידי הפחתת הדיוק ב-x באמצעות הפעולות (1+x )−1. להיות מוערך במדויק.

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

דוגמה 5.4. (בעיה דטרמיננטית*) שקול את הבעיה של חישוב הקובע של מטריצה ​​A. נניח שהכניסות של A מדויקות לשלוש ספרות של דיוק. למען הקונקרטיות, תן A = 101 −89.3 ..001
100 15.8 12.9
אנו יכולים להראות ישירות מההגדרה שהדטרמיננטה של ​​מטריצה ​​משולשת עליונה נתונה על ידי מכפלת הערכים האלכסוניים שלה (קוראים המתקדמים יותר באלגברה לינארית עשויים להיזכר שהקביעה של מטריצה ​​היא מכפלה של הערכים העצמיים שלה ושהערכים העצמיים של מטריצה ​​משולשת עליונה שוכבת על האלכסון שלה). בכל מקרה, יש לנו det A = 11.

עכשיו שקול את המטריצה ​​המופרעת
Ap = 101 −89.3 ,.002
100 15.8 12.9
שזהה ל-A למעט ההפרעה הקטנה ביותר האפשרית של הכניסה האלכסונית התחתונה. בנימוק כאמור לעיל, אנו מוצאים ש-det Ap = 22.

15

קובץ:Vertopal 811a6a975eb941cfa597972e380f96d2/media/image5.png

איור 5: גרף של f(x) =log(1+x)x − 1 מחושב בדייקנות כפולה בתקן IEEE.

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

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

דוגמה 5.5. (Permuted LU) בדוגמה זו אנו בוחנים מחדש את חישובי LU שבוצעו בהרצאות האחרונות וטוענים לנחיצותו של אלגוריתם LU המותמר. לשם הפשטות, נשקול דוגמה של 2 × 2. נניח
ϵ A = , 1 π
1
עם ϵ קטן. לצורך הקונקרטיות, נוכל לקחת ϵ = 10-14.

ביצוע פירוק LU נאיבי באמצעות חיסול גאוסי ישיר (ללא החלפת שורות, כך שכל עמודה בוטלה בתורה) מניב, בחשבון מדויק,
L = , ו-U = , ϵ−1 1 π − ϵ−1
1 ϵ 1
מכיוון שאנו מבטלים את העמודה הראשונה של A על ידי הוספה לשורה השנייה שלו −ϵ−1 פעמים השורה הראשונה שלו. הזנת L ו-U לתוך MATLAB וביצוע הכפל LU בתשואות דיוק כפולות סטנדרטיות
LU = , 1 3.140625 ϵ
1

16

קובץ:Vertopal 811a6a975eb941cfa597972e380f96d2/media/image6.png

איור 6: גרף של g(x) =log(1+x)(1+x)−1− 1 מחושב בתקן IEEE דיוק כפול.

והאלכסון התחתון ניתן בדיוק המלא המחושב על ידי MATLAB. שים לב שהמוצר משחזר π = 3.1415923565897932 . . . לשלוש ספרות בלבד של דיוק!

הקורא המעוניין צריך לאמת את החישובים שלנו על ידי הפעלת הקוד הבא:

1% חישוב LU כמעט יחיד

2 %דוגמה קטנה

3 ep sil on = 10ˆ(−14) ;

4 B = [ אפסילון 1; 1 פאי ]

5% אכזרי למען LU:

6 ל' = [ 1 . 0 . ; 1/ ep sil on 1 . ]

7 U = [ אפסילון 1 . ; 0 pi − 1/ ep silon ]
8 L∗U

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

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

שוב, הקורא המעוניין צריך לאמת את השחזור על ידי חישוב הפעולות הבאות ב-MATLAB (פונקציית lu מחילה אוטומטית אלגוריתם LU ממוחזר בעת הצורך):

1 % LU מאופקת

2	[ L perm , U perm ] = lu (B)
3	L perm∗U perm

17