דונלד קנוט הוא מדען מחשבים שכל כך אכפת לו מהדיוק של ספריו שהוא מציע דולר משושה אחד ($2,56, 0x$1,00) עבור כל "שגיאה" שנמצאה, כאשר שגיאה מוגדרת כל דבר שהוא "שגוי טכנית, היסטורית, טיפוגרפית או פוליטית". מאוד רציתי לקבל צ'ק מקנוט, אז החלטתי לחפש שגיאות במגנום אופוס שלו "אמנות התכנות" (TAOCP). הצלחנו למצוא שלושה. נאמן לדבריו, קנוט שלח צ'ק עבור 0x$3,00.

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

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

שגיאת הקלדה מס' 1

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

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

אגב, אם אי פעם חשבת לקרוא את TAOCP, נסה את זה. רבים יאמרו שזהו ספר, לא מיועד לקריאה ישירה, אבל זה לא נכון. למחבר יש נקודת מבט ברורה וסגנון ייחודי. הדבר היחיד שמפריע לקריאה הוא המורכבות של המתמטיקה. עם זאת, יש פתרון פשוט: קרא עד שאתה מגיע למתמטיקה שאתה לא מבין, דלג עליה ועבור לסעיף הבא שאתה יכול להבין. כשאני קורא ככה, אני מתגעגע לפחות ל-80% מהספר, אבל שאר ה-20% נהדרים!

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

1. בדוק אם האלמנט הנוכחי הוא הרכיב הרצוי. אם כן, אנו מחזירים אותו; אחרת
2. בדוק אם המצביע נמצא מחוץ לגבול המערך. אם כן, החזר שגיאה; אחרת
3. התקרב והמשך.

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

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

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

"חפש, חפש
כל כך ארוך
חפש, חפש
רק רציתי לרקוד"
- לותר ונדרוס, "החיפוש" (1980)

שגיאת הקלדה מס' 2

שגיאת ההקלדה השנייה היא בכרך 4A, אלגוריתמים קומבינטוריים, חלק 1. עמוד 60 מתאר בעיה הכרוכה בתזמון של קומיקאים להופיע בבתי קזינו שונים. כמה קומיקאים מהחיים האמיתיים מובאים כדוגמאות, כולל לילי טומלין, ווירד אל ינקוביץ' ורובין וויליאמס, שעדיין הייתה בחיים כשהספר פורסם. קנוט תמיד מפרט שמות מלאים באינדקס, ולכן וויליאמס מופיע בעמוד 882 בתור "ויליאם, רובין מקלורים". אבל שמו האמצעי מסתיים ב-"n" ולא ב-"m", כלומר, מקלאורין.

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

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

טעות היסטורית

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

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

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

אלגוריתם זה מתואר בעמוד 295 של כרך XNUMX, אלגוריתמים למחצה נומריים. שם קנוט כותב: "זה מוזר שהרעיון הזה התגלה רק ב 1962 שנה", כאשר פורסם מאמר המתאר את האלגוריתם של קרצובה. אבל! בשנת 1995, קראטסובה פרסם מאמר על "מורכבות חישובית", שאומר מספר דברים: 1) בסביבות 1956, קולמוגורוב הציע שאי אפשר לעשות כפל בפחות מ- צעדים; 2) ב 1960 שנה קראטסובה השתתף בסמינר שבו הציג קולמוגורוב את השערתו n². 3) "בעוד שבוע בדיוק", קראטסובה פיתח את אלגוריתם "הפרד ומשול"; 4) בשנת 1962, קולמוגורוב כתב ופרסם מאמר מטעם קראצובה עם תיאור האלגוריתם. "נודע לי על המאמר הזה רק אחרי שהוא פורסם מחדש."

אז השגיאה היא שבמקום 1962 יש לציין 1960 שָׁנָה. זה הכל.

ניתוח של

איתור שגיאות לא דרש מיומנות מיוחדת.

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

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

עובדות פיננסיות:

• בסך הכל, התרומה שלי ל-TAOCP מורכבת משלוש דמויות בלבד: תוספת אחת s, החלפה m על n и 2 על 0. במחיר של 2,56 דולר, אלה כמה סמלים די משתלמים; אם היו משלמים לך כסף מהסוג הזה, מאמר של 1000 מילים (בממוצע של ארבע תווים) היה מרוויח לך עשר אלף.
• עם שלושה דולרים הקסדצימליים, אני, יחד עם 29 אזרחים נוספים, במקום ה-69 ברשימת המפקידים העשירים ביותר של בנק סן סריף (נכון ל-1 במאי 2019).

דיונים אחרים על צ'קים מקנוט

• איך לקבל צ'ק מקנוט

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

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

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

• צ'קים של אשוטוש מהרה

  Ashutosh Mehra הוא המשקיע השלישי העשיר ביותר בסן סריף עם שווי נקי עצום של 0x$207.f0 ב-BoSS.

• בדוק אם יש באגים שאינם פונקציונליים בקוד TeX אמיתי
• שונות: #1 #2 #3 #4 #5 #6

מקור: www.habr.com