כאשר רוצים לראות מהירות של אלגוריתם או תוכנה, יש שתי דרכים למדוד זאת. הדרך הראשונה (האינטואיטיבית יותר) היא לראות כמה מחזורי שעון הפעולה לוקחת: למחשב יש שעון פנימי שכל פעילות המחשב מתוזמנת לפיו. מחזור אחד של השעון הוא היחידה הבסיסית של זמן של המחשב. המעבד (CPU) הוא יחידת החישוב הבסיסית של המחשב, שיכולה לבצע פעולות כמו הפעולות האריתמטיות של חיבור, חיסור כפל, חילוק ועוד, כאשר כל פעולה אחרת של המחשב מתורגמת לפעולות פשוטות שהמעבד יודע לחשב. כאשר מתארים מהירות של מעבד (בג'יגה הרץ בימינו) מתארים, בעצם, כמה מחזורים של שעון המעבד יכול לבצע בשנייה. מכיוון שכפל וחילוק הם מהפעולות הבסיסיות של המעבד, הם מבוצעות בצורה מהירה במיוחד (כ-4 מחזורי שעון) ובזמן דומה.
הדרך שהמעבד מבצע כפל וחילוק לא שונה מבחינה מהותית מכפל וחילוק ארוך שלומדים בביה"ס.
ניקח לדוגמא את הכפל:
דוגמא לפעולת כפל, התמונה לקוחה מויקיפדיה.
כמו שרואים, אנחנו בעצם מכפילים כל ספרה של המספר הראשון בכל סיפרה של המספר השני ואז מחברים. אם מספר הספרות בכל מספר הוא n אזי יש n2 מכפלות. מכיוון שכל המכפלות יכולות להתבצע במקביל חלק זה מתבצע במהירות, ורוב העבודה על פיתוח מכפלות מהירות בעצם מנסה למזער את מספר פעולות החיבור הנדרשות.
יש שתי בעיות עם הגישה הזאת למדידת מהירות - ראשית, המהירות תלויה בסוג המחשב והמעבד, ושנית, היא מוגבלת למספרים בגודל שהמעבד יכול לקבל. כיום מעבדים מוגבלים בדר"כ ל-32 או 64 ביט, כלומר מספרים עם 32 או 64 ספרות. לרוב השימושים זה די והותר, אך יש שימושים גם למספרים עם מספר ספרות גדול יותר. בהצפנה מודרנית, למשל, יש שימוש נרחב במספרים ראשוניים גדולים ככל שניתן (המספר הראשוני הגדול ביותר שנמצא עד היום מכיל כ13 מיליון ספרות). על מנת למצוא מספרים ראשוניים גדולים כאלה, יש צורך בלהיות מסוגלים להכפיל ולחלק מספרים באמצעות תוכנה ולא ישירות מהמעבד.
את המהירות של התוכנה אנו נמדוד בעזרת התנהגות אסימפטוטית. יש פרמטר n שקובע את הגודל של הבעיה (במקרה של כפל וחילוק זהו מספר הספרות), אנחנו נשאל "כמו מה גדל הזמן של הריצה כתלות בn?". במקרה של כפל וחילוק בשיטה שהוצגה קודם, זה גדל כמו n2 ויכול לקחת המון זמן למספר ספרות גדול. ישנם אלגוריתמים יותר מתוחכמים שמשפרים משמעותית את מהירות הכפל (גדל אסימפטוטית כמו nlog(n)log(log(n)) שלמרות שנראה מאיים, גדל הרבה יותר לאט) על ידי ייצוג של המספרים בצורה שונה שם הכפל מהיר בהרבה (רוב זמן החישוב מתבצע בתרגום המספר לייצוג החדש ובחזרה, אבל אם המספר מספיק גדול זה משתלם משמעותית).
האלגוריתם המהיר ביותר לחילוק A/B כיום, קודם כל הופך את B לאחד חלקי B ואז מחשב מכפלה, ולכן כמובן הוא איטי יותר מכפל.
איתן פתיה
דוקטורנט, המחלקה למדעי המחשב ומתמטיקה שימושית
מכון ויצמן למדע
הערה לגולשים
אם אתם חושבים שההסברים אינם ברורים מספיק או אם יש לכם שאלות הקשורות לנושא, אתם מוזמנים לכתוב על כך בפורום. אנו נתייחס להערותיכם. הצעות לשיפור וביקורת בונה יתקבלו תמיד בברכה.
