אז איך באמת מוצאים שורש ריבועי?

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

כשעוסקים בשורשים ריבועיים של מספרים טבעיים, יש אחת משתי אפשרויות - או שהשורש יהיה מספר שלם, או שיהיה מספר אי רציונלי (הדגמתי כאן את ההוכחה לאי הרציונליות של שורש 2; אפשר להכליל אותה לכל מספר שאין לו שורש שלם, אבל זה לא מיידי. אתגר: חשבו מדוע השיטה לא עובדת עבור 4, למשל). מספרים אי רציונליים ניחנים בתכונה המרגיזה שאי אפשר לכתוב אותם כמספר עשרוני סופי או מחזורי (וגם שינוי בסיס הספירה לא יעזור כאן), ולכן מראש אנו מוותרים על הרעיון להציג אותם בצורה הזו במדוייק. אנו כותבים \( \sqrt{2}=1.41421356\dots \) ואומרים ששלוש הנקודות מסמנות ש”זה לא סוף הסיפור”. בשביל מחשבונים, סוף הסיפור מגיע אחרי מספר לא גדול במיוחד של ספרות - הם פשוט לא מסוגלים להציג על המסך יותר ספרות. לכן, מחשבון מסתפק בהצגת קירוב של השורש האי רציונלי, ולנו זה לא כל כך מפריע, כי מי שם לב להבדל כשהוא כל כך זניח.

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

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

אם כן, איך אפשר למצוא במדוייק שורש של מספר טבעי? בלו דיבר על “חידת הראשוניים”, וייתכן שכאן התשובה. אפשר לקחת כל מספר טבעי ולפרק אותו לגורמים - להציג אותו בתור מכפלת מספרים ראשוניים. הרעיון אינו מסובך: ניקח למשל את 100. לא קשה לנחש מספר שמחלק אותו - נניח, 50, ולכן \( 100=50\cdot 2 \). כאן לא נגמר הסיפור - את 2 אי אפשר לפרק למכפלה בצורה שתוסיף לנו משהו - הפירוק היחיד הוא \( 2=2\cdot 1 \) שלא מגלה לנו משהו לא ידענו עדיין. למספרים כאלו, שמתחלקים רק בעצמם וב-1, קוראים ראשוניים. לעומת 2, 50 אינו ראשוני: אפשר לפרק אותו למכפלה של 2 ושל 25. גם את 25 אפשר לפרק למכפלה - של 5 בעצמו. 5 הוא ראשוני, כך שקיבלנו:

\( 100=2^2\cdot 5^2 \)

וזה מכונה "הפירוק לגורמים של מאה”. ה’ הידיעה כאן אינה מקרית - אין עוד פירוק אחר, וההוכחה לכך אינה מסובכת (התוצאה הזו נקראת “המשפט היסודי של האריתמטיקה”). כמובן שאפשר להתחכם ולהגיד שאפשר גם לכתוב \( 100=5^2\cdot 2\cdot 2 \) וכדומה - אולם אין הבדל מהותי בין שתי צורות הכתיבה; שתיהן מכילות בדיוק אותם גורמים ראשוניים, שהם הדבר החשוב.

העובדה הזו, שהמספרים הראשוניים מהווים “אבני בניין” שכאלו, היא אחת הסיבות שבגללן הראשוניים הם כל כך חשובים. הוצאת שורש היא דוגמה נאה למקרה שבו הכרת הפירוק לגורמים עוזרת לנו - כדי לדעת אם יש שורש שלם למספר די לפרק אותו לגורמים ולהביט בחזקה של כל גורם. אם כל חזקה היא זוגית, אז יש למספר שורש שמתקבל על ידי חלוקת כל חזקה ב-2. אחרת, אין לו שורש. נכונות הטענה הזו נובעת מחוקי החזקות הבסיסיים - נסו להוכיח אותה (או, אם זה עדיין לא ברור, שאלו שאלות בתגובות). במקרה שלנו, מה שנקבל הוא \( \sqrt{100}=2^{2\cdot \frac{1}{2}}\cdot 5^{2\cdot \frac{1}{2}}=2\cdot 5=10 \)

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

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

איני יודע מה השיטה שבה משתמשים מחשבונים בימינו, ואני מניח שזה משתנה ממחשבון למחשבון. ויקיפדיה האנגלית מספרת ששיטה קיימת נפוצה היא מעין “רמאות” - משתמשים בכך שלמחשבון כבר יש קירוב לשתי פונקציות “מסובכות” אחרות, ומשתמשים בקירוב הזה כדי לחשב שורשים. הפונקציות הן הלוגריתם הטבעי (ln באנגלית) ופונקצית האקספוננט \( e^x \). השאלה מי הן ומה הן ראויה לדיון נפרד שלא אכנס אליו כאן - רק אציין שמתכונותיהן נובע שמתקיים \( \sqrt{x}=e^{\frac{1}{2}\ln x} \).

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

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

הרעיון בשיטה הוא פשוט: נתונה פונקציה ממשית כלשהי \( f(x) \) (“ממשית” פירושה - מקבלת כקלט מספר ממשי ומוציאה כפלט מספר ממשי), שאנו רוצים למצוא ערך שמאפס אותה, כלומר שמתקיים בו \( (f(x)=0 \). בצורה גרפית, זוהי נקודה שבה גרף הפונקציה חותך את ציר ה-x. מה שעושים הוא לנחש נקודה שנמצאת בסביבות נקודת החיתוך - “קירוב ראשוני”. את הקירוב הזה משפרים בצורה הדרגתית והולכים ומתקרבים אל נקודת החיתוך, באופן הבא: מעבירים אנך מנקודת החיתוך הנוכחית אל גרף הפונקציה. בנקודה שבה פוגשים את גרף הפונקציה (שקוארדינטת ה-x שלה היא בדיוק הקירוב הנוכחי - נניח שהוא מסומן ב-\( x_n \) - ולכן גובהה הוא \( f(x_n) \) מעבירים משיק לגרף הפונקציה (קו ישר שהכיוון שלו הוא “כמו הכיוון של הפונקציה בנקודה”) עד שהוא חותך את ציר x. נקודת החיתוך היא הקירוב החדש שלנו. ממשיכים עד שהקירוב טוב דיו.

ויקיפדיה האנגלית מסכמת זאת בתמונה נאה:

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

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

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

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

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

ואיך מבצע מחשב את השיטה? משחק קצר בגאומטריה אנליטית, תוך כדי כך שזוכרים שהשיפוע של משיק לפונקציה בנקודה \( x_n \) הוא \( f\prime(x_n) \), מביא אותנו לנוסחה הבאה: \( x_{n+1}=x_n-\frac{f(n)}{f\prime(n)} \). זה תרגיל נחמד להגיע לתוצאה הזו, ואשאיר אותו למי שמעוניין בכך.

עבור שורש, הנגזרת פשוטה במיוחד: הנגזרת של \( x^2-n \) היא פשוט \( 2x \), ולכן הצבה בנוסחה הכללית מניבה לבסוף את הנוסחה הבאה:

\( x_{n+1}=\frac{1}{2}\cdot(x+\frac{n}{x}) \). זו השיטה הפרטית שגם הבבלים הכירו.

כדי לראות כמה מהר זה מתכנס, הנה דוגמה, עבור n=314,721, מספר שבחרתי שרירותית בתור מכפלה של שני ריבועים של ראשוניים (17 ו-33). זה מספר בן שש ספרות, כך שמימוש נבון ינחש בתור ערך התחלתי מספר בן 3 ספרות - נניח 500, שנמצא במקום טוב באמצע. הנה סדרת הקירובים:

500 564.5 561.010850310009 561.000000104926 561.0

ואכן, 561 הוא השורש.

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

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

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

הרעיון הבסיסי בשיטה פשוט עד כדי כך שיראה כמו רמאות. איך אני יודע מהו שורש 2? ברור לי שהוא גדול מ-1 (כי 1 בריבוע זה 1) וקטן מ-2 (כי 2 בריבוע הוא 4). אם כן, הוא חייב להתחיל בספרה 1. מה הספרה הבאה? פשוט מתחילים לעבור על הספרות - 1.0 בריבוע זה 1.0 - קטן מ-2. 1.1 בריבוע זה 1.21 - קטן מ-2, וכן הלאה, עד שנגלה כי 1.4 בריבוע הוא 1.960 שעדיין קטן מ-2, אבל 1.5 בריבוע הוא 2.2500, שגדול מ-2, ולכן הספרה הבאה היא 4, כלומר בינתיים הקירוב שלנו הוא 1.4, וכן הלאה. את כל חישובי ההעלאה בריבוע הללו לא קשה לעשות - כפל מספרים עשרוניים הוא קל למדי.

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

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