כפל מספרים גדולים ביעילות

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

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

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

כפל בשיטת בית הספר והשערת קולמוגורוב

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

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

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

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

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

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

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

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

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

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

שבירת הפרדיגמה ואלגוריתם קראצובה

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

אלגוריתם קאראצובה הוא שיטה לביצוע כפל של שני מספרים גדולים באופן יעיל יותר מהשיטה הסטנדרטית. הרעיון המרכזי הוא פירוק מספרים גדולים לתתי-מספרים קטנים יותר וצמצום מספר פעולות הכפל שנדרשות באמצעות זהות אלגברית. התהליך מתחיל בהגדרת שני מספרים, x ו-y, בעלי n ספרות בבסיס B. נבחר מספר m השווה למחצית n (מעוגל מעלה) ונחלק כל מספר לשני חלקים: החלק העליון (הספרות המשמעותיות) והחלק התחתון (הספרות הפחות משמעותיות).

הייצוג המתמטי של המספרים לאחר הפירוק נראה כך:

x = x₁ ⋅ Bᵐ + x₀

y = y₁ ⋅ Bᵐ + y₀

ייצוג הגורמים באלגוריתם קאראצובה

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

x ⋅ y = (x₁ ⋅ y₁) ⋅ B²ᵐ + (x₁ ⋅ y₀ + x₀ ⋅ y₁) ⋅ Bᵐ + (x₀ ⋅ y₀)

כדי לחשב את התוצאה הזו באופן מסורתי, עלינו לבצע ארבע פעולות כפל: x₁⋅y₁, x₁⋅y₀, x₀⋅y₁ ו-x₀⋅y₀. קאראצובה זיהה שניתן לחשב את הסכום של שתי המכפלות האמצעיות באמצעות מכפלה אחת בלבד, ובכך להוריד את סך המכפלות ל-3.

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

z₂ = x₁ ⋅ y₁

המשתנה השני הוא z₀, שמחושב כמכפלת החלקים התחתונים:

z₀ = x₀ ⋅ y₀

המשתנה השלישי הוא z₁, והוא מהווה את לב האלגוריתם. במקום לכפול את החלקים המעורבים, אנו סוכמים את חלקי המספרים וכופלים את הסכומים זה בזה:

z₁ = (x₁ + x₀) ⋅ (y₁ + y₀) - z₂ - z₀

הסיבה לכך שפעולה זו עובדת נעוצה בפיתוח האלגברי של המכפלה (x₁ + x₀) ⋅ (y₁ + y₀). פתיחת הסוגריים נותנת את התוצאה הבאה:

x₁ ⋅ y₁ + x₁ ⋅ y₀ + x₀ ⋅ y₁ + x₀ ⋅ y₀

ניתן לראות שביטוי זה מכיל בתוכו את z₂ (שהוא x₁⋅y₁) ואת z₀ (שהוא x₀⋅y₀). כאשר אנו מחסירים את z₂ ואת z₀ ממכפלת הסכומים, אנו נותרים בדיוק עם הביטוי שדרוש לנו עבור האיבר האמצעי בנוסחת הכפל המקורית:

x₁ ⋅ y₀ + x₀ ⋅ y₁

בשלב הסופי, לאחר שהשגנו את שלושת הערכים z₂, z₁ ו-z₀ באמצעות שלוש פעולות כפל בלבד (בתוספת מספר פעולות חיבור וחיסור פשוטות), אנו מרכיבים את התוצאה הסופית של המכפלה המקורית לפי הנוסחה:

x ⋅ y = z₂ ⋅ B²ᵐ + z₁ ⋅ Bᵐ + z₀

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

תרשים לתיאור אלגוריתם קאראצובה

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

הביטוי המתמטי לתנאי עצירה בסיסי זה הוא:

n ≤ 1

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

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

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

הביטוי המתמטי לסף יעילות מעשי הוא:

n < C

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

Result = x ⋅ y (Traditional)

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

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

ייצוג פולינומי, קונבולוציה והתמרת פורייה

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

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

P(x) = aₖ xᵏ +... + a₁ x¹ + a₀

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

דוגמה לקונבולוציה של שני פולינומים

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

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

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

מהפכת התמרת פורייה ואלגוריתם שונהאגה-שטראסן

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

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

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

Fₙ = 2^(2ⁿ) + 1

בחירה זו מאפשרת שימוש בשורשי יחידה שהם מספרים שלמים, המהווים חזקות של 2.

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

תהליך האלגוריתם מורכב מהשלבים הבאים:

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

עבור קלטים באורך של N ביטים, סיבוכיות זמן הריצה מוגדרת כ-

O(N · log N · log log N)

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

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

O(N · log N)

השערה זו נותרה כסוגיה פתוחה ומרכזית בתחום המורכבות החישובית במשך עשרות שנים.

עידן הקיפאון, מרטין פירר ו-אלגוריתם גלקטי

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

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

פונקציה זו מציינת את מספר הפעמים שיש להפעיל את הלוגריתם ברצף על ערך נתון, עד קבלת תוצאה שקטנה מ-1. הסיבוכיות של אלגוריתם פירר היא O(n · log n · 2ᴼ⁽ˡᵒᵍ* ⁿ⁾).

קצב הגידול של הלוגריתם החוזר הוא איטי. עבור קלט כגון 2²⁵⁰ הפונקציה מחזירה ערך שקטן מ-6, כך שהגורם המעריכי מתנהג בפועל כקבוע. בעקבות פירר, פורסמו מחקרים נוספים, ביניהם עבודות של דייוויד הארווי ויוריס ואן דר הוון בין השנים 2014 ל-2018, אשר צמצמו את הקבועים בביטוי.

פיתוחים אלו מוגדרים כאלגוריתמים גלקטיים, מונח שטבעו ריצ'רד ליפטון וקן ריגן. המושג מתאר אלגוריתמים בעלי יתרון אסימפטוטי תיאורטי שאינם ישימים בפועל. חוסר הישימות נובע מקבועים נסתרים גדולים ומנקודת חיתוך גבוהה. נקודת החיתוך היא גודל הקלט n שעבורו האלגוריתם הופך למהיר יותר משיטות קודמות. אלגוריתם פירר מהיר מאלגוריתם שונהאגה-שטראסן רק עבור מספרים הגדולים מ- 10^(10¹⁸).

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

למרות השיפור שהציג פירר, השערתם המקורית של שונהאגה ושטראסן משנת 1971, לפיה החסם התחתון לבעיה עומד על O(n · log n) נותרה בעיה פתוחה עד לשנת 2019.

הארווי וואן דר הוון והשגת החסם האופטימלי

במרץ 2019 פרסמו דייוויד הארווי ויוריס ואן דר הוון אלגוריתם שמשיג את החסם התחתון המשוער לכפל מספרים שלמים. סיבוכיות הזמן של האלגוריתם מוגדרת כ O(n · log n).

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

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

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

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

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

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

אלגוריתם גלקטי

שלבי האבולוציה המרכזיים של אלגוריתמי הכפל וסיבוכיותם

הגישה האלגוריתמית	סיבוכיות הזמן	המתמטיקאי / חוקר המפתח	האלגוריתם
חלוקה לספרות וכפל נאיבי ישיר	O(N²)	מגוון בהיסטוריה	כפל בית ספר
הפרד ומשול אלגברי בשלוש פעולות במקום ארבע	O(N¹⸱⁵⁸)	אנטולי קראצובה	אלגוריתם קראצובה (1960)
מעבר לפולינומים והתמרת פורייה בשדה סופי (NTT)	O(N · log N · log log N)	ארנולד שונהאגה, פולקר שטראסן	שונהאגה-שטראסן (1971)
מיטוב אסימפטוטי באמצעות לוגריתם מדורג	סדר גודל שמשלב לוגריתם חוזר	מרטין פירר	אלגוריתם פירר (2007)
התמרת פורייה רב-ממדית (1729 ממדים) ודגימה גאוסיינית	O(N · log N)	דייוויד הארווי, יוריס ואן דר הוון	הארווי וואן דר הוון (2019)

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

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

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

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

כפל מספרים גדולים ביעילות