מה זה לוגריתמים ובשביל מה זה טוב?

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

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

אני מניח שאנחנו מכירים חיבור - זו נקודת התחלה לא רעה. אנחנו יודעים ש-\( 3+5=5+3 \) (זה חוק החילוף). אנחנו יודעים שחיסור הוא פעולה הפוכה לחיבור במובן הבא: \( 3+5-5=3 \). כלומר, אם חיברתי ל-3 ואז חיסרתי ממנו את אותו מספר, אז אני אחזור אל מה שהתחלתי ממנו. אני רוצה טיפה לחדד את זה בצורה שנשמעת פדנטית אבל בהמשך אולי יהיה ברור למה אני מתעקש עליה: הפעולה “לחסר 5” היא הפעולה ההפוכה של “לחבר 5”. כמובן שלא נכון לומר ש”לחסר 5” היא הפעולה ההפוכה של “לחבר 4”, כלומר יש חשיבות לשאלה מה המספר הספציפי שמחסרים.

עכשיו נעבור אל פעולת הכפל. מה זה כפל? סביר שגם אותו אנחנו מכירים: על כפל במספר טבעי אפשר לחשוב בתור הרבה פעולות חיבור. \( 3\times5 \) הוא דרך אחרת לומר \( 3+3+3+3+3 \) - חיברנו את 3 לעצמו 5 פעמים. עכשיו, עבור כפל, קורה אותו הסיפור שקרה עבור חיבור בדיוק: \( 3\times5=5\times3 \) - הנה שוב חוק החילוף בפעולה. והפעולה ההפוכה ל”כפל ב-5” נקראת “חלוקה ב-5” ואני לרוב מסמן אותה ככה: \( 3\times5\times\frac{1}{5}=3 \) (כלומר, אני מגדיר חלוקה ב-5 בתור כפל ב-\( \frac{1}{5} \)). ההבדל היחיד בין חיבור וחיסור ובין כפל וחילוק הוא שבכפל וחילוק, לא קיימת פעולה הפוכה ל”כפל ב-0”. אבל זה סיפור לפעם אחרת.

אחרי כפל, הפעולה הבאה שאפשר לדבר עליה היא חזקה. אם כפל במספר טבעי מוגדר בתור “לחזור על החיבור כמה פעמים”, אז העלאה בחזקת מספר טבעי מוגדרת בתור “לחזור על הכפל כמה פעמים”. כלומר, הסימון \( 3^{5} \) מייצג את \( 3\times3\times3\times3\times3 \) - כופלים את 3 בעצמו 5 פעמים.

וכאן הסיפור מתחיל להסתבך.

בניגוד לחיבור וכפל, חוק החילוף לא מתקיים עבור חזקות. אפשר פשוט לבדוק את זה בעזרת דוגמא: \( 3^{5}=243 \) אבל \( 5^{3}=125 \). המקרה היחיד של שני מספרים שונים זה מזה שעבורם חוק החילוף מתקיים הוא \( 2^{4}=4^{2}=16 \) (ואיכשהו אלו תמיד שני המספרים הראשונים שעולים לי לראש כשאני רוצה לתת דוגמאות לחזקה). גם הכתיב של חזקה מאפשר לנו לראות שאין סימטריה: בביטוי \( 3^{5} \) יש את המספר שכתוב בגדול ואת זה שנמצא בקטן למעלה. למספר הגדול שלמטה, 3 במקרה שלנו, קוראים בסיס החזקה. למספר הקטן שלמעלה, 5 במקרה הנוכחי, קוראים מעריך החזקה. פעולת החזקה פירושה לכפול את בסיס החזקה שוב ושוב בעצמו מספר פעמים ששווה למעריך החזקה.

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

בואו נראה דוגמא קונקרטית. נניח שנקפיא את מעריך החזקה להיות תמיד 2, ונשאל את עצמנו מה קורה עבור בסיסים שונים. נקבל את הפונקציה \( f\left(x\right)=x^{2} \) שאנחנו קוראים לה העלאה בריבוע. הפעולה ה”הפוכה” להעלאה בריבוע היא הוצאת שורש ריבועי: \( g\left(x\right)=\sqrt{x} \). אני כותב “הפוכה” במרכאות כי זה לא מדויק במאה אחוזים: אם אני לוקח את \( -2 \) ומעלה אותו בריבוע אקבל 4, ואחרי הוצאת שורש ריבועי אקבל 2 כי מגדירים את פעולת הוצאת השורש ככזו שמחזירה את השורש החיובי.

באופן דומה אפשר לדבר על העלאה בחזקות גבוהות יותר: \( f\left(x\right)=x^{n} \) עבור \( n \) טבעי כלשהו. הפעולה ההפוכה לזה נקראת “שורש מסדר גבוה” ומסומנת ב-\( g\left(x\right)=\sqrt[n]{x} \). את הפעולות הללו אנחנו מכירים יחסית טוב; למשל, הקפיצה מאורך צלע של קוביה אל הנפח שלה היא העלאה בחזקה שלישית, ולכן הקפיצה חזרה מנפח של קובייה אל אורך הצלע שלה הוא הוצאת שורש שלישי. כמובן, במכולת אנחנו לא זקוקים לפעולות הללו אבל הן יותר נטועות במציאות היומיומית שלנו מאשר מה שאנחנו הולכים לדבר עליו עכשיו.

עכשיו, סוף כל סוף, אנחנו מגיעים אל לוגריתמים.

ראשית, בואו נדבר על הפעולה של העלאה בחזקה כשדווקא הבסיס קבוע. בואו נקבע אותו להיות מספר שרירותי כלשהו, נאמר 10 כי אנחנו אוהבים את 10. אז יש לנו את הפונקציה \( f\left(x\right)=10^{x} \). הפונקציה הזו נקראת פונקציה אקספוננציאלית והיא אחת מהפונקציות שמצטלמות הכי גרוע שאפשר:

לוגריתם הוא ההפך מהפונקציה האקספוננציאלית הזו: \( \log\left(10^{x}\right)=x \). באופן כללי: \( \log \) על קלט \( y \) כלשהו בודק מהו ה-\( x \) שעבורו \( 10^{x}=y \), ואז הוא מחזיר את ה-\( x \) הזה. הוא עונה על השאלה “10 בחזקת איזה מעריך נותן לנו את \( y \)?”

אז כדי לראות כמה דוגמאות: \( \log\left(10\right)=1 \) ו-\( \log\left(1000\right)=3 \) ו-\( \log\left(10000000\right)=7 \) ו-\( \log\left(1\right)=0 \) כי \( 10^{0}=1 \) (כי דברים בחזקת 0 שווים 1). כאן אנחנו רואים משהו חשוב על לוגריתמים: זו פונקציה שגדלה לאט. כדי לקבל ערכים יותר ויותר גדולים של לוגריתם, צריך להזין קלטים הרבה יותר גדולים.

ומה עם \( \log\left(121\right) \), למשל? לכמה זה שווה? אם תבדקו במחשבון הוא יגיד משהו בסגנון \( \log\left(121\right)=2.08278\ldots \). זה קצת מוזר, כי עד עכשיו בפוסט הזה לא דיברנו בכלל על חזקות שהן לא מספר טבעי. מה זה \( 10^{2.08278\ldots} \)? זה לכפול את 10 בעצמו פעמיים ואז… לעשות… מה בעצם?

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

בואו ניקח בסיס חזקה קבוע שהוא מספר חיובי, שאני אסמן באות \( a \) כי אין לי כוח לכתוב \( 10 \) או משהו דומה כל הזמן. בואו ניקח עכשיו שתי חזקות שונות של \( a \): \( a^{x},a^{y} \) ונכפול אותן. מה נקבל? אם \( x,y \) הם מספרים טבעיים ואנחנו הולכים על פי ההגדרה של “חזקה היא ביצוע של אותה פעולת כפל שוב ושוב” קל לראות ש-\( a^{x}\cdot a^{y}=a^{x+y} \) (שימו לב שהתחלתי לתאר כפל עם נקודה ולא עם \( \times \) סתם כי זה סימון שיותר נוח לי). באופן דומה לא קשה לראות ש-\( \left(a^{x}\right)^{y}=a^{xy} \). במילים אחרות: פעולת החזקה איכשהו מתרגמת את פעולת החיבור של המעריכים לפעולת כפל של תוצאות החזקה, ואת פעולת הכפל של המעריכים לפעולת העלאה בחזקה נוספת של פעולת החזקה. זה כל כך חשוב שאני אכתוב את זה שוב במפורש:

• \( a^{x+y}=a^{x}\cdot a^{y} \)
• \( a^{xy}=\left(a^{x}\right)^{y} \)

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

אז למשל, אם \( y=0 \), השוויון \( a^{x+0}=a^{x}\cdot a^{0} \) מתורגם ל-\( a^{x}=a^{x}\cdot a^{0} \) מה ש”מכריח” את \( a^{0}=1 \). ועכשיו, \( a^{x+\left(-x\right)}=a^{x}\cdot a^{-x} \) מתורגם ל-\( 1=a^{x}\cdot a^{-x} \) מה ש”מכריח” את \( a^{-x}=\frac{1}{a^{x}} \) (זה לא עובד אם \( a=0 \)! לכן אני דורש ש-\( a \) יהיה מספר חיובי!). כמו כן, מכיוון ש-\( \frac{1}{2}+\frac{1}{2}=1 \) אז \( a=a^{1}=a^{\frac{1}{2}+\frac{1}{2}}=\left(a^{\frac{1}{2}}\right)^{2} \) “מכריח” את \( a^{\frac{1}{2}}=\sqrt{a} \) ובאופן כללי יותר מקבלים \( a^{\frac{1}{n}}=\sqrt[n]{a} \). מכל אלו אנחנו מקבלים את ההגדרה \( a^{\frac{x}{y}}=\sqrt[y]{a^{x}} \) שעובדת למעריך שהוא מספר רציונלי כללי (מספר רציונלי הוא מספר שהוא מנה של שני מספרים שלמים, \( \frac{x}{y} \)).

השלב האחרון, של להגדיר חזקה שהיא לא מספר רציונלי אלא מספר ממשי כללי, היא מסובכת יותר פשוט כי ההגדרה של “מספר ממשי כללי” היא מסובכת. אני יכול לומר ש-\( a^{x} \) מוגדר בתור \( \lim_{q\to x}a^{q} \) כך ש-\( q \) היא סדרת רציונליים ששואפת ל-\( x \), אבל זה לא יגיד כלום אם לא מכירים את המושגים הרלוונטיים וגם אם מכירים אותם יש כל מני שאלות מציקות (למה זה אותו גבול עבור כל סדרת רציונליים?) אז אני לא אכנס לזה הפעם, אבל זה עובד יפה.

עכשיו נחזור לדבר על לוגריתמים. ראשית כל, עד עכשיו דיברתי על לוגריתם שהיה קשור למספר 10, אבל אין משהו קדוש ב-10; גם מספרים אחרים יכולים להיות בסיס ללוגריתם. למשל 2: אפשר לדבר על \( \log_{2} \) שמוגדר כך: אם \( y=2^{x} \) אז \( \log_{2}y=x \). יש ל-\( \log_{2} \) הזה אפילו סימון מיוחד: \( \lg \). ואפשר לעשות את אות והדבר גם עבור בסיסים אחרים. המגבלה שאנחנו דורשים היא שהבסיס יהיה מספר גדול מ-1, כי עבור 1 העסק כבר מתחיל להיות מעצבן (מכיוון שלכל \( x \) מתקיים \( 1^{x}=1 \) יוצא ש-\( \log \) על בסיס 1 לא מוגדר לשום מספר שונה מ-1) וגם עבור מספרים קטנים ממנו העסק בעייתי בצורות דומות. לכן דורשים \( 1<a \) ואז אפשר לדבר על \( \log_{a} \), שמוגדרת כפי שכבר ראינו: אם \( y=a^{x} \) אז \( \log_{a}\left(y\right)=x \). כלומר, יש הרבה סוגים שונים של לוגריתמים, כפי שיש הרבה סוגים שונים של שורשים (ריבועי, שורש שלישי וכן הלאה).

למעשה, הבסיס הכי חשוב של הלוגריתם הוא בכלל לא מספר טבעי אלא מספר שמסומן ב-\( e \) ושווה בערך ל-\( 2.7182\ldots \) (זה לא מספר רציונלי ולכן אין מחזוריות בספרות). מה זה המספר הזה? למה הוא חשוב כל כך? יש לי פוסט שמציג אותו בצורה שנראית לי טבעית יחסית, אבל לא ניכנס לכך בפוסט הנוכחי - ההסבר המדויק מערב, כרגיל, חשבון דיפרנציאלי ואינטגרלי. גם ל-\( \log_{e} \) יש סימון מיוחד: \( \ln \) (ולפעמים אפילו כותבים פשוט \( \log \) למרות שמתכוונים אל \( \ln \)), אבל לא ארחיב על כך יותר בפוסט הזה.

עכשיו, אם נסתכל שניה על מחשבון, נראה שאין בו הרבה כפתורים עבור לוגריתמים. אם יש לנו מזל יש אחד עבור \( \log \) ואחד עבור \( \ln \) וזהו זה.

איך אפשר לחשוב לוגריתמים עבור בסיסים אחרים? למרבה המזל, יש קשר הדוק בין לוגריתמים בבסיסים שונים שמאפשר לנו לחשב את \( \log_{a}b \) גם אם כל מה שיש לנו הוא \( \log \) רגיל על בסיס 10 (או עבור כל בסיס אחר).

התעלול עובד כך: נניח ש-\( x=\log_{a}b \), ונחפש דרך נחמדה לבטא את \( x \) באמצעות \( \log \) רגיל, על בסיס 10. מכיוון ש-\( x=\log_{a}b \) אז על פי ההגדרה ממש אנחנו יודעים ש-\( a^{x}=b \).

עכשיו, לתעלול! כל עוד \( a>1 \), אפשר להוכיח (שוב, זה דורש חדו”א) ש-\( t=\log a \) הוא מספר שבאמת קיים. כלומר, שקיים \( t \) כלשהו כך ש-\( a=10^{t} \). כשאנחנו מצויידים בידע הזה בואו נחזור למשוואה \( a^{x}=b \) ונציב \( 10^{t} \) במקום \( a \). נקבל:

\( b=a^{x}=\left(10^{t}\right)^{x}=10^{tx} \)

כשהמעבר האחרון נובע מחוקי החזקות שהראיתי קודם.

עכשיו, מה המשמעות של השוויון \( b=10^{tx} \)? כמקודם, על פי ההגדרה ממש משמעותו היא \( \log b=tx \). או במילים אחרות, \( x=\frac{\log b}{t} \). אבל מה היה \( t \)? לכו טיפה אחורה ותראו ש-\( t=\log a \). כלומר קיבלנו \( x=\frac{\log b}{\log a} \), ובמילים אחרות: \( \log_{a}b=\frac{\log b}{\log a} \). כך אפשר לחשב לוגריתם על פי כל בסיס בעזרת מחשבון שיודע רק לחשב את \( \log \) על בסיס 10.

למעשה, אנחנו רואים כאן אפילו טיפה יותר מכך: אם נגדיר פונקציה \( f\left(x\right)=\log_{a}x \), אנחנו רואים ש-\( f\left(x\right)=\frac{1}{\log a}\log x \). במילים אחרות, ההבדל בין פונקציית הלוגריתם “הרגילה”, על בסיס 10, ובין כל פונקציית לוגריתם אחרת הוא רק כפל בקבוע. זו תוצאה מעניינת מאוד כשאנחנו במדעי המחשב, למשל, ואנחנו מתעניינים רק בסדרי גודל של דברים ולא בערך המספרי המדויק שלהן; זה אומר שכל הפונקציות הלוגריתמיות הן מאותו סדר גודל.

עכשיו, אחרי שהבנו מה זה לוגריתמים, בואו ננסה לראות בשביל מה זה טוב. בשביל זה כדאי לראות עוד תכונות שלוגריתמים מקיימים. נתחיל עם יישום של הנוסחה \( \log_{a}b=\frac{\log b}{\log a} \) שראינו עבור מקרה פרטי. אם \( b=a^{x} \), אז \( x=\log_{a}b=\frac{\log\left(a^{x}\right)}{\log\left(a\right)} \). אם נכפול את שני קצוות המשוואה ב-\( \log\left(a\right) \) נקבל \( \log\left(a^{x}\right)=x\log\left(a\right) \). זו תכונה חשובה של לוגריתם - הוא “מוריד את המעריך” מחזקה והופך אותו לכפל; זה בעצם ההופכי של תכונת ה-\( a^{xy}=\left(a^{x}\right)^{y} \) של הפונקציה המעריכית, שבה כפל הופך לחזקה.

באופן דומה גם לתכונת ה”חיבור הופך לכפל”, \( a^{x+y}=a^{x}\cdot a^{y} \), יש היפוך: \( \log_{a}x+\log_{a}y=\log_{a}\left(xy\right) \). כדי לראות את זה אני הולך להיעזר בעוד תכונה פשוטה של לוגריתמים: \( a^{\log_{a}x}=x \). כלומר, לוגריתם בתוך מעריך של חזקה מתבטל עם החזקה; זו פחות או יותר ההגדרה. הרי אמרנו ש-\( \log_{a}x=t \) פירושו ש-\( a^{t}=x \), אז אם נכתוב את \( \log_{a}x \) במקום \( t \) נקבל בדיוק \( a^{\log_{a}x}=x \).

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

\( a^{\log_{a}x+\log_{a}y}=a^{\log_{a}x}\cdot a^{\log_{a}y}=x\cdot y \)

כאשר המעבר הראשון נובע מהתכונה של אקספוננטים להפוך סכום למכפלה, והמעבר השני הוא ה-\( a^{\log_{a}x}=x \) שהראיתי. עכשיו אפשר לקחת את \( xy \) ולהשתמש עליו באותה נוסחה: \( xy=a^{\log_{a}\left(xy\right)} \). קיבלנו בסך הכל:

\( a^{\log_{a}x+\log_{a}y}=a^{\log_{a}\left(xy\right)} \)

עכשיו נפעיל את \( \log_{a} \) על שני האגפים ונקבל \( \log_{a}\left(x\right)+\log_{a}\left(y\right)=\log_{a}\left(xy\right) \), כפי שרצינו.

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

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

הנה שיטת העבודה: נניח שיש לי מספרים \( x,y \) ואני רוצה לחשב את \( xy \) בקלות. מה אעשה? ראשית כל, אחשב את \( \log\left(x\right),\log\left(y\right) \); עכשיו אבצע פעולת חיבור שתיתן לי את \( \log\left(x\right)+\log\left(y\right)=\log\left(xy\right) \). עכשיו רק צריך לשחזר מתוך \( \log\left(xy\right) \) את \( xy \) ו… ניצחנו! איזה יופי! רק שאלה קטנה נשארה: איך, בהינתן \( x,y \), מחשבים מתוכם את \( \log\left(x\right) \) ואת \( \log\left(y\right) \)? ואיך מתוך \( \log\left(xy\right) \) מקבלים חזרה את \( xy \)? התשובה היא כמובן… מחשבון! רגע, משהו לא מסתדר פה.

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

אני מתחמק כאן מכניסה לפרטים הטכניים של איך להשתמש בטבלאות הללו כי הפוסט ממילא ארוך מדי, אבל הרעיון ברור - בעזרת הטבלאות היה אפשר לחשב יחסית בקלות לוגריתמים, מה שאיפשר למי שיש לו טבלה כזו להמיר כפל בחיבור. באופן דומה גם אפשר היה להמיר חילוק בחיסור, כי מתקיים גם הכלל הבא: \( \log_{a}x-\log_{a}y=\log_{a}\frac{x}{y} \). כדי לראות את זה אפשר להשתמש בכללים שכבר ראינו: ראינו ש-\( \log_{a}x^{t}=t\log_{a}x \), ולכן בפרט עבור \( t=-1 \) נקבל \( -\log_{a}x=\log_{a}x^{-1}=\log_{a}\frac{1}{x} \), ומכאן נשתמש בכלל החיבור עבור \( \log_{a}x-\log_{a}y=\log_{a}x+\left(-\log_{a}y\right) \).

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

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

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

למה “לצערי”? כי הדוגמא הראשונה שקופצת לי לראש היא זו של מגיפת הקורונה של 2020.

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

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

המשמעות של גידול אקספוננציאלי היא זו: שאם מחלקים את הגידול לפרקי זמן קצרים, אז בכל פרק זמן הגידול כפול ממה שהיה קודם (כפול בקבוע כלשהו,לאו דווקא ב-2). זה מאופיין על ידי פונקציה כמו \( f\left(t\right)=a^{t} \) (כאן \( t \) הוא הזמן). המשמעות של גידול לינארי היא שאם מחלקים את הגידול לפרקי זמן קצרים, אז בכל פרק זמן הגידול זהה למה שהיה קודם - למשל \( f\left(t\right)=at \). את החלק הלינארי אפשר לראות די בבירור, אבל הקפיצה האקספוננציאלית היא פשוט קפיצה: נראה שהגרף “שטוח” ברגע אחד, ופתאום הוא מתחיל לעלות - שינוי שמעביר אותו מאפס למיליון כמעט בבת אחת.

אבל יש דרך אחרת להציג את הנתונים, שעוזרת להבין אותם יותר טוב - סקלה לוגריתמית. מה זה אומר? ובכן, בסקלה רגילה, לינארית, הגובה של ערך בציר \( y \) הוא פונקציה לינארית של הערך שלו. אם נסתכל על הגרף שלמעלה, נראה שערכים של 2 מיליון מפוזרים במרווחים שווים. אם \( f \) היא הפונקציה שמתאימה לערך את הגובה שלו אז \( f\left(2\cdot10^{6}\right)=a \) כאשר \( a \) הוא הגובה של הקו הראשון, זה שכתוב לידו \( \text{2M} \); ואז \( f\left(4\cdot10^{6}\right)=2a \) ו-\( f\left(6\cdot10^{6}\right)=3a \) וכן הלאה: הפונקציה באופן כללי היא \( f\left(x\right)=\frac{a}{2\cdot10^{6}}x \). זו דוגמא לפונקציה לינארית - היא לוקחת את \( x \) וכופלת אותו בקבוע.

הנה איך אותו גרף נראה בסקלה לוגריתמית:

מה השתנה? ציר \( y \). אם נסתכל על הערכים שם, נראה שעכשיו מה שקורה במרווחים שווים הוא שהערך שמיוצג מוכפל ב-10. הערך הנמוך ביותר הוא 100; אחר כך, במרווח שווה ממנו, יש את \( 1,000 \); אחר כך במרווח שווה ממנו יש את \( 10,000 \) וכן הלאה. אם נסמן את הגובה של הקו של ה-1,000 ב-\( a \) אז נקבל את הפונקציה \( f\left(x\right)=\log\left(x\right)a-2a \) (ה-\( -2a \) מגיע מכך שהקו התחתון בגרף, זה שבגובה 0, הוא 100).

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

יש עוד סקלות לוגריתמיות שמשמשות אותנו בחיי היום יום - מדידה של חומציות עם סקלת pH היא לוגריתמית; מדידה של רעש עם סקלת הדציבלים היא לוגריתמית, ואולי הסקלה הלוגריתמית המוכרת ביותר היא סולם ריכטר למדידת העוצמה של רעידות אדמה. כשמדווחים על רעידות אדמה בדרך כלל אומרים שהן היו בעוצמה של “5.8 בסולם ריכטר” או “6.1 בסולם ריכטר” וכדומה. אל תתנו למספרים הדומים לבלבל אתכם - כל עליה בסולם ריכטר פירושה הכפלה בקבוע כלשהו של עוצמת רעידת האדמה. רעידת אדמה שהיא 3 בסולם ריכטר בקושי תורגש; רעידת האדמה של יפן ב-2011 שהייתה 9 בסולם ריכטר לא הייתה פי 3 יותר מה”בקושי תורגש” הזה אלא הייתה אסון אדיר ממדים וחריג בעוצמתו.

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

בלי להיכנס לעובי הקורה של איך מודדים זמן ריצה של אלגוריתמים, הרעיון הוא שאם יש לנו מספר \( n \) שמהווה מדד כלשהו לגודל של הקלט, ויש לנו פונקציה \( f\left(n\right) \) שאומרת לנו מה הולך להיות זמן הריצה על קלט בגודל \( n \) במקרה הגרוע ביותר, אז אנחנו מתעניינים במה סדר הגודל בערך של \( f \) הזו. יש לי פוסט שמסביר את הסימון שבו משתמשים למטרה הזו אבל אין צורך לקרוא אותו כרגע: הרעיון הוא שאם אני כותב \( f\left(n\right)=O\left(n^{2}\right) \), למשל, זה אומר שאני יכול להבטיח ש-\( f \) היא לא יותר מאשר בערך הפונקציה \( n^{2} \).

בעיה בסיסית במדעי המחשב היא בעיה של מיון. נניח שיש לנו קבוצה של \( n \) מספרים ואני רוצה לסדר אותם בסדר עולה. כמה זמן יידרש לי לשם כך? שיטות נאיביות כמו לקחת איבר ולהשוות אותו לכל האיברים שסידרנו עד כה כדי לדעת איפה לדחוף אותו (שיטה שנקראת מיון הכנסה ודומה לאופן שבו מסדרים קלפים ביד במשחק קלפים) לוקחות לי בערך \( O\left(n^{2}\right) \) זמן. זה לא טוב. תחשבו על סיטואציה עם 1000 קלטים - זמן הריצה יהיה בערך 1,000,000 (מיליון מה? כאמור, אני מטאטא את הפרטים מתחת לשטיח). ואם אני מכפיל את מספר הקלטים ב-10, אז זמן הריצה גדל פי 100. זה בהחלט לא משהו.

אבל יש מיונים יותר מתוחכמים ויותר מהירים, למשל מיון מיזוג. מבלי להיכנס לפרטים, הרעיון במיון הזה הוא לחלק את הקבוצה שצריך למיין לשני חלקים. ואז כל חלק למיין לשני חלקים. ושוב, ושוב, עד שמגיעים לקבוצות קטנות מספיק כדי שאפשר יהיה למיין אותן “מייד” ואז מתחילים למזג בצורה חכמה את הקבוצות הממויינות. והרי לכם שאלה: נניח שיש לי \( n \) איברים ובכל סיבוב אני מחלק את קבוצות האיברים שלי ל-2; כמה סיבובים יידרשו עד שקבוצות האיברים שלי יהיו מגודל אפסי?

נניח שהקבוצה שלי היא בת 16 איברים. אחרי סיבוב אחד אקבל שתי קבוצות של 8 איברים; אחרי 2 סיבובים הקבוצות יהיו בנות 4 איברים ואחרי 3 סיבובים הן יהיו בנות 2 איברים. אחרי 4 סיבובים הן יהיו בנות 4 איברים ואפשר יהיה לסיים כאן. כל סיבוב הקטין את גודל הקבוצה פי 2, כלומר כפל אותה בחצי: אם \( n \) הוא הגודל המקורי של הקבוצה אז אחרי \( k \) סיבובים נקבל קבוצות בנות \( \frac{n}{2^{k}} \) איברים. אם \( \frac{n}{2^{k}}=1 \) אז \( n=2^{k} \), כלומר \( k=\lg n \) (כזכור, \( \lg \) הוא לוגריתם על בסיס 2). אם כן, מספר הצעדים עד שמגיעים לקבוצות קטנות הוא לוגריתמי ב-\( n \). זה אומר שגם כאשר \( n \) הוא ממש גדול, מספר הצעדים עד לפיצול יהיה ממש קטן. המשך הניתוח של האלגוריתם יראה שבהתחשב בזמן שלוקח לבצע את המיזוג, זמן הריצה הכולל של האלגוריתם יהיה \( O\left(n\log n\right) \), וזאת להבדיל מהאלגוריתמים של \( O\left(n^{2}\right) \). הדבר הזה הוא שיפור גדול, כי \( \log n \) הרבה יותר קטן מ-\( n \) ולכן \( n\log n \) הרבה יותר קטן מ-\( n^{2} \). למשל, עבור \( n=1000 \), ראינו ש-\( n^{2}=1,000,000 \) בעוד ש-\( n\log n=3000 \).

והנה עוד דוגמא אחרונה לסיום - מספרים גדולים. אנחנו מתעסקים עם מספרים גדולים כל הזמן - דוגמא פופולרית במיוחד היא שיטת ההצפנה \( \text{RSA} \) שמתבססת על עבודה עם מספרים בני מאות ספרות. אנחנו צריכים לבצע איתם פעולות כמו חיבור, כפל, העלאה בחזקה וכדומה; כמה זמן זה לוקח?

ובכן, התשובה טמונה במה שאמרתי במשפט הקודם: כשאני מדבר על “מספר בן מאות ספרות” המשמעות היא “מספר שהלוגריתם שלו הוא בסדר גודל של כמה מאות”. הלוגריתם בבסיס 10 של מספר כלשהו הוא פשוט מספר הספרות שלו פחות 1 ועוד תיקון כלשהו. למשל, עבור \( 100 \) הלוגריתם הוא בדיוק 2, ואילו עבור 121 ראינו שהלוגריתם הוא “2 ועוד קצת משהו” שהוא פחות ממספר שלם.

עכשיו, אלגוריתמים עבור חיבור וכפל, גם מאלו שלומדים בבית הספר היסודי, הם משהו שעובד על הספרות של המספר. למשל, אלגוריתם לחיבור מחבר ספרה-ספרה, החל מספרת האחדות. אז הזמן שאלגוריתמים כאלו לוקחים הוא מסדר גודל של לוגריתם של המספר, או ריבוע של לוגריתם כזה, וכו; כלומר משהו כמו \( O\left(\log^{2}n\right) \) כדי לבצע כפל. כשמתעסקים במספרים, אלו זמני הריצה שנחשבים יעילים; זמן ריצה של \( O\left(n\right) \) הוא אסון, כי אם \( n=10^{100} \) למשל (וזה מספר קטן יחסית למספרים שאנחנו עשויים להתעסק איתם) אז פרק זמן ששווה בערך ל-\( 10^{100} \) הוא גדול בהרבה מהשניות שחלפו מאז תחילת היקום.

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