הכפלה ללא הכפלה

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

אני אתחיל מתרגום נאיבי של פעולת כפל לפעולת חיבור.
בעבור שני מספרים a,b תוצאת הכפל a*b שווה לתוצאה של חיבור a לעצמו b פעמים.

לדוגמא –

a = 3 b =4
3*4 = 3+3+3+3 = 12

אם כך, דרך אחת לפתור את הבעיה תהיה באלגוריתם שמחבר את a לעצמו בלולאה בגודל b.

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

def recur_multiply(a,b):
   if b==1:
      return a
   else:
      return a + recur_multiply(b-1)

b=4 recur_multiply(3,4) = 3 + recur_multiply(3,3) = 3 + 3 + recur_multiply(3,2) = 3 + 3 + 3 + recur_multiply(3,1) = 3 + 3 + 3 + 3 = 12

אני אבדוק שהפונקציה עובדת –

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

3*4 = 3 + 3 + 3 + 3

אפשר לחשב –

x = 3 + 3 3*4 = x + x

בדוגמא למעלה במקום לבצע 3 פעולות חיבור ביצענו רק 2.
איך אני יודעת לכמה תת-פעולות כדאי לחלק את החישוב כדי להגיע למינימום פעולות?
אני אנסה לבדוק מספרים קצת גדולים יותר כדי להגיע לתשובה.

a=3 b=16 3*16 = 3 + 3 + 3 + 3 + …. + 3

אני אתחיל מלחלק ל-2

x = 3 + 3 + 3 + 3 + 3 + 3 + 3 + 3 = 48 3*16 = x + x

החלוקה הורידה את מספר הפעולות מ-15 ל-8 (7 פעולות חיבור כדי לייצר את x ועוד פעולה אחת x+x).
האם אפשר להגיע למספר נמוך יותר על ידי עוד חלוקה?

y = 3 + 3 + 3 + 3 = 12 x = y + y = 24 3*16 = x + x = 48

הפעם החלוקה הורידה את מספר הפעולות מ-8 ל-5 (4 פעולות כדי ליצור את y, פעולת אחת כדי ליצור את x ועוד פעולה בשביל לקבל את התוצאה הסופית.
אני כבר רואה תבנית, אבל אני אעשה את החלוקה האחרונה רק כדי להיות בטוחה.

z = 3 + 3 = 6 y = z + z = 12 x = y + y = 24 3*16 = x + x = 48

הפעם החלוקה הורידה את מספר הפעולות מ-5 ל-4.

זה לא מאוד מפתיע שזו התשובה שקיבלתי.
16 הוא חזקה של 2. לכן כל פעם יכולתי פשוט “להכפיל” ב-2 את התוצאה הקודמת כדי לקבל את החזקה הבאה.
אבל מה אני אעשה במקרה שבו המספר המכפיל הוא לא חזקה של 2?

a=3 b = 15

אני אתחיל כמו בפעם הקודמת –

z = 3 + 3 = 6 y = z + z = 12 x = y + y = 24 3*16 = x + x – 3 = 45

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

עוד דוגמא ליתר ביטחון –

a = 3 b = 10 z = 3 + 3 = 6 y = z + z = 12 x = y + y = 24 3*16 = x + 3 + 3 = x + z 3*16

אז אם אני אפרמל את מה שעשיתי פה זה ילך ככה –

אני אתחיל מהחיבור של הספרה המוכפלת עם עצמה כדי לקבל את תוצאה המכפלה ב-2 ואשמור את התוצאה בזיכרון.
לאחר מכן אני אחבר את התוצאה עם עצמה כדי לקבל את תוצאת המכפלה ב-4 ואשמור את התוצאה בזיכרון.
אני אמשיך כך עד שאגיע למכפלה שהיא החזקה של שתיים הכי קרובה למספר המכפיל.
אני אמצא את ההפרש המספרי בין המספר המכפיל לחזקה הקרובה (בדוגמאות למעלה ההפרש בין 15 ו-16 הוא 1, וההפרש בין 10 ו-8 הוא 2) – ואז אשלוף את התוצאות מהזיכרון המתאימות כדי לייצר את ההפרש בין התוצאה שקיבלתי לתוצאה הסופית. אחבר/אחסר, ואחזיר את התוצאה.

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

def recur_multiply(a,b):
   if b not in results_cache:
      if b == 1:
         results_cache[1] = a
      elif b%2 == 0 and b/2 in results_cache:
         results_cache[b] = results_cache[b/2] + results_cache[b/2]
      else:
         tmp = get_closes_power_of_2(b)
         if tmp > b:
            results_cache[b] = recur_multiply(a,tmp) -      recur_multiply(a,tmp-b)
         else:
            results_cache[b] = recur_multiply(a,tmp) + recur_multiply(a,b-tmp)
 
   return results_cache[b]

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

עכשיו אריץ בדיקה על אחת מהדוגמאות למעלה –

a=3
 b=10
 results_cache = {}
 recur_multiply(3,10):
    tmp = get_closes_power_of_2(10) = 8
    tmp > 8 → results_cache[10] = recur_multiply(3,8) + recur_multiply(3,2)
 recur_multiply(3,8)
    tmp = get_closes_power_of_2(b) = 8
    tmp <= 8 → results_cache[8] = recur_multiply(3,8) + recur_multiply(3,0)

אופס, באג, גרמתי לרקורסיה אינסופית.

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

לדוגמא, בעבור b=8 אני ארצה להחזיר את התוצאה של 4 “מוכפלת” ב-2. כמו שהדגמתי למעלה.
אני אשנה את הקוד בהתאם –

def recur_multiply(a,b):
   if b not in results_cache:
      if b == 1:
         results_cache[1] = a
   elif b%2 == 0:
      if b/2 not in results_cache:
         results_cache[b/2] = recur_multiply(a,b/2)
         results_cache[b] = results_cache[b/2] + results_cache[b/2]
      else:
         tmp = get_closes_power_of_2(b)
         if tmp > b:
            results_cache[b] = recur_multiply(a,tmp) - recur_multiply(a,tmp-b)
         else:
            results_cache[b] = recur_multiply(a,tmp) + recur_multiply(a,b-tmp)
 
   return results_cache[b]

עכשיו אפשר להריץ דוגמא מחדש –

a=3
 b=10
 results_cache = {}
 recur_multiply(3,10):
 results_cache[5] = recur_multiply(3,5) 
 recur_multiply(3,5):
    tmp = get_closes_power_of_2(5) = 4
    tmp < 5 → results_cache[5] = recur_multiply(3,4) + recur_multiply(3,1)
 recur_multiply(3,4):
    results_cache[2] = recur_multiply(3,2)
 recur_multiply(3,2):
    results_cache[1] = recur_multiply(3,1)
 recur_multiply(3,1):
    results_cache[1] = 3
 recur_multiply(3,2):
    results_cache[2] = results_cache[1] + results_cache[1] = 6
 recur_multiply(3,4):
    results_cache[4] = results_cache[2] + results_cache[2] = 12
 recur_multiply(3,5):
    results_cache[5]  = results_cache[4] + results_cache[1] = 15
 recur_multiply(3,10):
    results_cache[10] = results_cache[5] + results_cache[5] = 30
 return 30

קיבלתי את התוצאה הנכונה. ווהו!

אני אספור רגע כמה פעולות חיבור/חיסור עשיתי –

results_cache[1] + results_cache[1] results_cache[2] + results_cache[2] results_cache[4] + results_cache[1] results_cache[5] + results_cache[5]

4 פעולות סה”כ – זהה למספר הפעולות שעשיתי בדוגמא – זאת למרות שהפעם המספרים בהם השתמשתי היו שונים, כי התחלתי מלמעלה (10) ולא מלמטה (1).

עכשיו כדאי להריץ כמה דוגמאות על מקרי קיצון.

a=3 b=0 results_cache = {} recur_multiply(3,0): results_cache[0] = recur_multiply(a,0)

אופס, רקורסיה אינסופית. אני אוסיף טיפול למקרה של מכפלה באפס.

מה קורה במצב ההפוך? מה קורה אם a=0?

אם a=0 האלגוריתם לא יכשל, אבל הוא כן יעשה הרבה עבודה מיותרת – הוא יבצע את כל הפעולות הנדרשות לביצוע מכפלה, למרות שהתוצאה ידועה מראש.

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

def recur_multiply(a,b):
   if a == 0:
      return 0
   if b not in results_cache:
      if b == 0:
         result_cache[0] = 0
      elif b == 1:
         results_cache[1] = a
      elif b%2 == 0:
         if b/2 not in results_cache:
            results_cache[b/2] = recur_multiply(a,b/2)
            results_cache[b] = results_cache[b/2] + results_cache[b/2]
     else:
        tmp = get_closes_power_of_2(b)
        if tmp > b:
           results_cache[b] = recur_multiply(a,tmp) - recur_multiply(a,tmp-b)
        else:
           results_cache[b] = recur_multiply(a,tmp) + recur_multiply(a,b-tmp)
 
   return results_cache[b]

נשארת רק השאלה מהי הסיבוכיות של האלגוריתם.

בעבור a,b –
בכל איטרציה בה b זוגי אנחנו חוצים אותו לשניים וקוראים לפונקציה על התוצאה. כאשר b הוא אי זוגי אנחנו קוראים לפונקציה על החזקה של 2 הכי קרובה ועל ההפרש. במקרה זה b לא נחצה לחצי אלא לשני חלקים בגדלים שונים, אבל אחד מהחלקים האלה הוא חזקה של 2, כך שמעתה והלאה הוא יישאר זוגי בכל חציה.
בממוצע הסיבוכיות של תהיה (O(logb.
*זה יותר נפנופי ידיים מאשר חישוב, אני יודעת, אבל כרגע אני רוצה להתקדם, אני אוכל לחזור לזה אחר כך במקרה הצורך.

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

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

האם אני יכולה להיפטר מהחלק הזה של הקוד?

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

results_cache[b] = recur_multiply(a,b-1) + recur_multiply(a,1)

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

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

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

אני הרי יודעת שבקריאה הבאה על המספר הזוגי b-1 אני אקרא לפונקיה על (b-1)/2 ו”אכפיל” את התוצאה, אז אני יכולה לעשות זאת מראש ולדלג על שלב.

results_cache[(b-1)/2] = recur_multiply(a,(b-1)/2) results_cache[b] = results_cache[(b-1)/2] + results_cache[(b-1)/2] + recur_multiply(a,1)

כעת בכל קריאה, על b זוגי או על b אי זוגי, אני מבצעת את הקריאה הבאה על b/2, והסיבוכיות שלי היא )O(logb.

שאלה מאוד מגניבה. אני יכולה ללכת לכתוב קוד ואתם יכולים לראות אותו בגיט!

https://github.com/mgershovitz/maya_solves/blob/master/recur_multiply.py