שיטת "הכפל היפני"

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

כפל_מקלות

והנה גם סרטון שמסביר את השיטה:

אנסה להסביר בקיצור בעצמי מה הולך כאן. הרעיון הוא לקחת את אחד המספרים שאנחנו כופלים ולכתוב את ספרותיו בתור קבוצות (עם רווחים ביניהן) של קווים אלכסוניים (נאמר, שפונים לכיוון למטה-שמאלה). כך למשל את $latex 324$ מייצגים בתור קבוצה של 3 קווים, רווח, קבוצה של שני קווים, רווח, קבוצה של 4 קווים. עכשיו לוקחים את המספר השני שאותו כופלים ועושים לו אותו דבר, רק עם אלכסונים בכיוון ההפוך (למעלה-שמאלה). בשני המקרים ככל שהקבוצה שמאלית יותר כך היא מייצגת ספרה "גבוהה" יותר.

אם ציירנו את הקבוצות בצורה מדויקת מספיק, אפשר לזהות נקודות מובחנות של חיתוכים בין שתי קבוצות של קווים שהן בערך באותו קו רוחב. הרעיון הוא כעת כזה: כמות נקודות החיתוך בקבוצה הימנית ביותר היא ספרת האחדות בתוצאה; כמות נקודות החיתוך בקבוצות בקו הרוחב הבא היא ספרת העשרות, וכן הלאה. אם קיבלנו שיש, נאמר, 24 נקודות חיתוך עבור קו רוחב מסויים אנחנו כותבים את הספרה 4 ומחברים את 2 לתוצאה של הספירה עבור קו הרוחב הבא. בסופו של דבר אנחנו מקבלים את תוצאת הכפל הנכונה.

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

התגובות לשיטה הזו ברחבי האינטרנט משתפכות למדי – הביטוי "Mind blown" מופרח פה ושם, ובאתר 9GAG אפשר למצוא המחשה נאה (ומטופשת למדי) לאופן שבו מתייחסים בחלק מהמקומות לדבר הזה:

6066420_700b

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

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

בואו נתחיל בהבנה של הבסיס שעליו שתי השיטות בנויות – ייצוג עשרוני. המספר "ארבע מאות ושבע-עשרה" מסומן בשיטה העשרונית בתור 417. הסימון הזה הוא קיצור לביטוי הבא: $latex 4\times100+1\times10+7\times1$, כלומר ארבע כפול מאה, ועוד אחד כפול עשר, ועוד שבע כפול 1. באופן כללי, מספר בייצוג עשרוני מייצג סכום של חזקות של 10, כאשר כל חזקה כזו מוכפלת בספרה שנמצאת במקום המתאים במספר. גם התוצאה נרשמת בצורה דומה – סכום של חזקות של 10.

עכשיו בואו ניקח דוגמת צעצוע ונראה מה עולה בגורלה – המכפלה של המספר $latex a_{1}a_{0}$ (שהוא הדרך לכתוב בבסיס עשרוני את $latex a_{1}\cdot10^{1}+a_{0}\cdot10^{0}$) במספר $latex b_{1}b_{0}$. אנחנו הולכים לפתוח את הסוגריים במכפלה באמצעות חוג הפילוג ("דיסטריביוטיביות"):

$latex \left(a_{1}\cdot10^{1}+a_{0}\cdot10^{0}\right)\left(b_{1}\cdot10^{1}+b_{0}\cdot10^{0}\right)=$

$latex =a_{1}b_{1}\cdot10^{2}+a_{1}b_{0}\cdot10^{1}+a_{0}b_{1}\cdot10^{1}+a_{0}b_{0}\cdot10^{0}$

קיבלנו סכום של ארבע מכפלות. כל אחת מהן היא מכפלה של ספרה מכל אחד מהמספרים, כפול חזקה כלשהי של 10. איזו חזקה? ובכן, הסכום של החזקות שכל אחת מהספרות הוכפלו בהן מלכתחילה: זה נובע מהתכונה הידועה של חזקות, שמתקיים $latex 10^{n}\cdot10^{k}=10^{n+k}$.

באופן כללי, אם יש לנו שני מספרים $latex a_{n}\cdots a_{1}a_{0}$ ו-$latex b_{n}\cdots b_{1}b_{0}$ שאניח לצורך פשטות שהם מאותו אורך (תמיד אפשר להוסיף ספרות 0 בסוף המספר הקצר יותר), אם מכפילים אותם מקבלים את הדבר הבא (אני משתמש כאן בסימן הסכימה – $latex \Sigma$ – לא להיבהל, הוא אומר בדיוק את מה שאתם חושבים שהוא אומר):

$latex \left(\sum_{i=0}^{n}a_{i}10^{i}\right)\left(\sum_{j=0}^{n}b_{j}10^{j}\right)=\sum_{i,j=0}^{n}a_{i}b_{j}10^{i+j}$

כלומר, המכפלה נותנת לנו סכום של $latex \left(n+1\right)^{2}$ מחוברים מהצורה $latex a_{i}b_{j}10^{i+j}$ כאשר $latex i,j$ הם מספרים כלשהם בין 0 ו-$latex n$ (יש $latex n+1$ מספרים שכאלו – מכאן הגיע הפלוס 1).

עכשיו, בכפל "רגיל" מבצעים קיבוץ איברים בצורה הבאה:

$latex \sum_{i,j=0}^{n}a_{i}b_{j}10^{i+j}=\sum_{j=0}^{n}b_{j}\left(\sum_{i=0}^{n}a_{i}10^{i}\right)\cdot10^{j}$

כלומר, אנחנו מקבלים $latex n+1$ מספרים, שכל אחד מהם הוא התוצאה של הכפלת $latex b_{j}$ (מספר בין 0 ל-9) ב-$latex a_{n}\cdots a_{1}a_{0}$ (המספר הראשון כולו), כשאת התוצאה הזו כופלים ב-$latex 10^{j}$, כלומר "מזיזים $latex j$ מקומות שמאלה".

השלב המאתגר כאן הוא לכפול את $latex a_{n}\cdots a_{1}a_{0}$ במספר $latex b_{j}$. התוצאה היא פשוט $latex \sum_{i=0}^{n}a_{i}b_{j}10^{i}$, אבל כשרוצים לכתוב את זה בתור מספר עשרוני צריך להיזהר כי $latex a_{i}b_{j}$ עשוי להיות גדול יותר מ-9, ולכן כבר לא ספרה לכשעצמו. מה כן אפשר לומר עליו בודאות? מכיוון ש-$latex a_{i}\le9$ וגם $latex b_{j}\le9$ הרי ש-$latex a_{i}b_{j}\le81$ ולכן המכפלה של שני המספרים הללו היא לכל היותר בת 2 ספרות. לכן אפשר לפצל אותה לשניים: ספרת האחדות היא מה שייכתב בפועל, ואילו ספרת האחדות הופכת ל"נשא" (Carry) שיחובר אל האיבר הבא בתור, $latex a_{i+1}b_{j}$ (ואם $latex i=n$, אז הוא פשוט ייכתב משמאל לספרה הנוכחית). שימו לב שגם אם מחברים ל-$latex a_{i}b_{j}$ נשא של 9 אנחנו לא יכולים להגיע ל-100 אלא לכל היותר לספרת עשרות של 9, ולכן השיטה עובדת.

כל מה שנותר הוא להסביר איך אנחנו יודעים לחשב את מכפלת שתי ספרות, $latex a_{i}b_{j}$. התשובה היא שאין כאן פתרונות קסם. מה שעושים בדרך כלל הוא לשנן בעל פה את המכפלה של כל המספרים מ-1 עד 9 אלו באלו. זה מה שנקרא "לוח הכפל". זה אחד מהדברים הבודדים במתמטיקה שלדעתי אכן הכרחי לשנן. יש כמה תעלולים שמקלים על הזכרון עבור חלק מהמקרים (למשל, הכפולות של 9 הן מהצורה $latex ab$ כך ש-$latex a+b=9$ וזה בהחלט מקל על השינון) אבל בשורה התחתונה – כאן אכן צריך לשנן.

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

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

$latex \sum_{i,j=0}^{n}a_{i}b_{j}10^{i+j}$

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

$latex \sum_{i,j=0}^{n}a_{i}b_{j}10^{i+j}=\sum_{k=0}^{n}\left(\sum_{i=0}^{k}a_{i}b_{k-i}\right)10^{k}$

וכדי שלא יהיה יותר מדי מבלבל, בואו נראה דוגמה קונקרטית למקרה של המספרים $latex a_{1}a_{0},b_{1}b_{0}$:

$latex a_{0}b_{0}\cdot10^{0}+\left(a_{1}b_{0}+a_{1}b_{0}\right)\cdot10^{1}+a_{1}b_{1}\cdot10^{2}$

כאן $latex a_{0}b_{0}$ הוא מספר החיתוכים של שתי קבוצות הקווים בקו הרוחב הימני ביותר, $latex a_{1}b_{0}+a_{1}b_{0}$ הוא מספר החיתוכים של קבוצות הקווים בקו הרוחב ה"אמצעי" (שכולל, כפי שאפשר לראות בתמונה, שתי קבוצות מובחנות שונות של חיתוכים) ו-$latex a_{1}b_{1}$ מתאים לקו הרוחב השמאלי. החזקות של 10 שמוכפלות באיברים הללו מצדיקות את הטענה המקורית שלי שהקבוצה הימנית ביותר מתאימה לספרת האחדות, זו שאחריה לספרת העשרות וכן הלאה.

כפל_מקלות

אם יש לנו שתי סדרות, $latex a_{0},a_{1},\dots,a_{n}$ ו-$latex b_{0},b_{1},\dots,b_{n}$ אז ביטוי מהצורה $latex \sum_{i=0}^{k}a_{i}b_{k-i}$ נקרא קונבולוציה של שתי הסדרות – הקונבולוציה ה-$latex k$-ית. דרך ציורית חזקה מאוד להדגמת הרעיון בקונבולוציה היא זו: ראשית כתבו את הסדרה הראשונה. כעת כתבו מתחתיה את הסדרה השניה כשהיא הפוכה ומוזזת כך שהאיבר ה-$latex k$ בה נמצא בדיוק מתחת לאיבר $latex a_{0}$ של הסדרה הראשונה. כעת כפלו כל זוג איברים של הסדרות שנמצאים האחד מעל השני, וסכמו. כל הקונבולוציות האפשריות של שתי הסדרות מתקבלים כשלוקחים את הסדרה התחתונה ובכל שלב מזיזים אותה צעד אחד שמאלה, ומחשבים את הקונבולציה שהתקבלה הפעם.

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

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

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

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

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

נתחיל בכפל רגיל. נניח שאנחנו כופלים שני מספרים, בני $latex n$ ו-$latex k$ ספרות, כך ש-$latex k<n$. ראשית אנחנו כותבים את שני המספרים כשהגדול מעל הקטן – זה דורש $latex n+k$ צעדי כתיבה. עכשיו, לכל אחת מהספרות של המספר הקטן אנחנו כופלים אותה בכל אחת מספרות המספר הגדול ואולי גם מוסיפים את הנשא מהכפל עם הספרה הקודמת של המספר הגדול. סך הכל $latex n\cdot k$ פעולות כפל ו(בערך) $latex n\cdot k$ פעולות חיבור. כעת קיבלנו $latex k$ מספרים שיש לחבר (המספרים שמתקבלים מכפל כל ספרה במספר הקטן במספר הגדול). האורך של כל אחד מהם הוא (בערך) $latex n$ ולכן אנחנו מבצעים (בערך) $latex n\cdot k$ פעולות חיבור בסיסיות. הפלט עצמו כולל (בערך) $latex n+k$ ספרות והיו לנו (בערך) $latex n\cdot k$ ספרות ביניים שכתבנו, כך שסך הכל ביצענו $latex 2\left(n+k\right)+nk$ צעדי כתיבה, $latex 2n\cdot k$ צעדי חיבור ו-$latex n\cdot k$ צעדי כפל. החלק ה"כבד" ביותר כאן הוא ביצוע פעולות הכפל; אנחנו מניחים שמי שמבצע את האלגוריתם זוכר בעל פה את לוח הכפל ולכן הצעדים הללו קלים לו יחסית – לא יותר קשים מאשר צעדי החיבור.

בכפל יפני הסיפור שונה כי הפעולות שאנחנו מבצעים הן בעיקרן שונות. ראשית כל אנחנו צריכים לצייר קווים. כמה קווים? ובכן, $latex n+k$ קבוצות של קווים, אבל מספר הקווים בקבוצה הוא בין 1 ל-9, כתלות בספרות של המספרים שאנחנו כופלים. זו תכונה שלא קיימת בשיטה הרגילה – בהינתן שאנחנו זוכרים את לוח הכפל בעל פה, לא ממש משנה לנו מה הספרות שיש במספרים שכופלים, בעוד שבשיטה היפנית ספרות גדולות דורשות יותר עבודה (וזה לא ממש מפתיע שבדוגמאות שיש בתמונות ובסרטונים רוב הספרות קטנות).

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

כעת מגיע האקשן – ההכפלה. יש לנו $latex n\cdot k$ איזורי חיתוך שונים בין קבוצות הישרים, ואנחנו צריכים לספור את כולם. בכל אחד כזה צריך לספור את נקודות החיתוך – והמספר שלהן תלוי לגמרי בגודל הקבוצות שנחתכות, כלומר בגודל הספרות שמכפילים. אם כופלים את 2 ב-2 יהיו לנו רק 4 נקודות חיתוך; אם כופלים את 7 ב-9 יהיו לנו 63 נקודות חיתוך. האם זה סביר לספור את כולן "בעיניים"? לא נראה לי. די בבירור יש כאן מקום לאופטימיזציה כלשהי, אבל על כך נדבר בהמשך.

אחרי שמסכמים את כל הנקודות בקו רוחב מסויים כותבים את הסכום. גם כאן יכול להיות נשא, ויהיה צורך לזכור אותו היכן שהוא כי אחר כך מתחילים לסכום קבוצה חדשה ומי יכול לזכור את הנשא לכל אורך המניה הזה (זכרו – אלגוריתמים מבוצעים על ידי אנשים כמוני, שהם ממש גרועים בחישוב; איש הגשם לא צריך את השטויות הללו, כנראה). כדאי לשים לב שכאן הנשא יכול בהחלט להיות בן כמה ספרות – אם למשל בקו הרוחב יש 5 איזורי חיתוך ובכל אחד יש בערך 50 חיתוכים קיבלנו כבר סכום של 250, ולכן נשא של 25. בקיצור – יש $latex n+k$ קווי רוחב שונים (בערך) ולכן נכתוב (בערך) $latex n+k$ ספרות ונבצע $latex n+k$ פעולות חיבור. סך הכל ביצענו $latex n+k$ פעולות של כתיבת ספרות ו-$latex n+k$ פעולות של חיבור, אבל גם $latex n+k$פעולות של שרטוט קבוצות קווים ו-$latex n\cdot k$ פעולות של מניית חיתוכים.

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

בואו ננסה לרגע להבין האם אפשר לשפר את עניין ספירת החיתוכים. אפשר, למשל, לא לצייר קבוצות של קווים, אלא פשוט לצייר קו עם מספר לידו שאומר כמה קווים "אמורים" להיות בקבוצה. כל מה שנותר הוא לזהות נקודות חיתוך ולחשב בראש את הסכום עבור כל קו רוחב. בשיטה הראשונה אנחנו ממש סופרים את הנקודות שמהוות את הקונבולוציה $latex \sum_{i=0}^{k}a_{i}b_{k-i}$, ואילו בשיטה השניה אנחנו רואים את הזוגות $latex a_{i},b_{k-i}$ בעיניים ומחשבים את המכפלות-וסכומים שלהם בראש. לדעתי זה מאתגר קצת יותר מאשר ביצוע הכפל-וחיבור-נשא של השיטה הרגילה, ובכל מקרה זה מצריך לזכור את לוח הכפל. אנחנו רואים שאין מנוס מכך – אם לא רוצים לספור חיתוכים פיזית, צריך לזכור את לוח הכפל.

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

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

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

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

14 תגובות על הפוסט “שיטת "הכפל היפני"

  1. אני רוצה לראות ילד יפני שכופל 789 ב987 בשיטה הזו….. חראקירי!
    בסופו של דבר השיטה הזו די דומה לספירה בבסיס אונארי. לא מבין בכלל איך אפשר להשוות. לא מבחינת היעילות ולא מבחינה תיאורטית. עם כל הכבוד לקונבולציה, לFFT מגיעים ברמות די מתקדמות. לעומת זאת הרעיון שמאחורי כפל ארוך הוא יותר בסיסי וכדאי להנחילו מגיל צעיר. אותו רעיון שנמצא גם מאחורי חילוק ארוך (איך בדיוק היפנים עושים את זה??? דה-קונבולוציה??)

    בקיצור הדבר הזה הוא עוד הדגמה לבורות מרצון כלפי מתמטיקה

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

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

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

  4. לא אמרת את זה אבל בגלל ש k-i (בקונבולנציה) גדול מאפס אבל קטן מ k וסדר הסכימה לא משנה בעצם סוכמים את כל הזוגות ש i ו- ( j או k-i ) כלומר כל הזוגות של a,b כך ש a,b קטנים ממספר הספרות אבל גדולים מאפס בסכום.

  5. שיהיה ברור לא סוכמים את הזוגות עצמם, אלא סוכמים את ההצבות שלהם בנוסחה.

  6. טוב קראתי את התגובות שלי מחדש וראיתי שהן ממש לא ברורות.

    התכוונתי שבעצם שתי השיטות סוכמות את אותם איברים, רק בסדר אחר:
    אם a,b הם סיפרות, ו c,d הן המיקום שלהן במספר בהתאמה אז סוכמים את המספר
    a*10^c*b*10^d .
    את ההבחנה הזאת אפשר להבין ככה: שני הסכומים עוברים על אותה קבוצה של קלטים ולכל קלט מוסיפים איבר כלשהו (כלומר לכל זוג a,b קטן מ-n מוסיפים איבר כלשהו בשני הסכומים). אבל אם שני הסכומים עוברים על אותם זוגות של מספרים אפשר גם להסביר בקלות למה האיברים של כל זוג שווים בשני הסכומים (ע"י מחיקה של סימני הסכום ופשוט לדבר על כל a,b בנפרד).

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

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

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

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

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

    אבל רגע; בעצם מתי הזוג i,j  = n נכנס לנוסחת הכפל היפני? הרי  i+j=k אבל המקסימום של k הוא n, ולא 2n. עוד דרך לראות את הבעיה הזאת היא שבגלל ההזחה של הסכום היא 10^k (אוף עברית ואנגלית ביחד!) ולכן האורך המקסימלי האפשרי הוא n+1 למרות שהוא 2n בפועל. אני חושב שמשהו בנוסחה לא נכון. אני משער שהחסם העליון על k לא אמור להיות n.
    (הערה: כשאני אומר j בשיטה היפנית הכוונה כמובן ל k-i. בגלל שאלה אותם זוגות (אמורים להיות) זה יותר נוח לי לכתוב ככה)

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

  10. בפיסקה שמתחילה ב: "השלב המאתגר כאן הוא לכפול את….."
    כתבת בטעות: ספרת האחדות היא מה שייכתב בפועל, ואילו ספרת האחדות הופכת ל"נשא" (Carry) שיחובר אל האיבר הבא בתור…..

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

  12. סליחה שאני קטנוני – אבל איפה שכתבת "קו רוחב" התכוונת ל"קו אורך" –
    החיתוכים שמייצגים את אותה חזקה של 10 נמצאים באותו "קו אורך".

כתיבת תגובה

האימייל לא יוצג באתר.