מעשה חושב (רלב"ג)
התוכן > חלק ב' > אלגוריתם לחישוב שורש ריבועי

בחלק החמישי של חלק ב' של ספרו נותן הרלב"ג דוגמה לאלגוריתם חישוב של שורש ריבועי (עבור ריבועים שלמים).
השיטה של הרלב"ג מובנת יותר בהשוואה לשיטה של הבבלים לחישוב שורשים ריבועיים. שיטת המיצוי הבבלית למציאת קירוב לשורש ריבוע של  N: נסמן ב- a_{i} את הקירוב לשורש בשלב ה- i, ונסמן  a_{1}=1 (ניתן להתחיל גם מכל מספר אחר). אז נקבל כי  a_{n+1}={(a_{n}+{N \over a_{n}}) \over 2} מהווה קירוב של השורש הריבועי של  N. לדוגמה: עבור  N=2 נקבל  a_{1}=1,a_{2}=1.5,a_{3}=1.416666.
ניסוח המקור לשיטה של הרלב"ג מתוך "מעשה חושב":
דרך הוצאת השרש מהמספר המרובע המקיף בשלמים ראוי שנכתוב המספר שבקשנו לדעת את מרובעו בטור אחד כפי מעלותיו אחר כך חקור על המעלה האחרונה שבטור אם היא מהנפרדות ואם לא הייתה מהנפרדות הורידה אל שלפניה כדי שיהיה המספר האחרון שבמעלה נפרד. אחר כך ראה המרובע היותר קרוב אל זה המספר ואמנם המעט ויסוד המרובע ההוא תכתוב בטור השרש תחת הטור הקודם במעלה האמצעית בין המעלה הראשונה והמעלה האחרונה והוא אשר נקראה הטור היוצא ומרובע השרש היוצא תגרע מהטור העליון והנשאר תחלוק על כפל השרש היוצא אך השמר שיישאר לך אחר החלוקה כמו מרובע השרש היוצא לך מן החלוקה והעולה בחלוק והוא השרש היוצא תכתבהו בטור השרש במעלה אשר מרחקה לאחור מהמעלה שחלקת כמרחק המעלה שחלקת עליה מהראשונה ותעורך זה השרש היוצא לך מן החלוקה תערוך על כפל השרש המוצא ועל עצמו והעולה תגרע מהטור העליו וכן תעשה עד שלא יישאר בטור העליון דבר... דמיון זה אם רצית להוציא שרש א'ח'ב'ו'ד'ו'ב'ח' ולפי שהמעלה האחרונה היא שמינית תורידה אל שלפניה והנה פ"ב והנה פ"א הוא המרובע היותר קרוב לזה שהמספר ושרשו ט' תכתוב ט' בטור השרש ברביעית שהיא אמצעית בין השביעית והראשונית והנה מרובע ט' מהרביעית הוא פ"א מהשביעית גרענום מפ"ב ונישאר אחד בשביעית ולא נוכל לחלק על כפל ט' שהוא השרש המוצא הורדנוהו אל שלפניו עם ו' שהיו בה והנה י"ו ולא נוכל לחלק על כפל ט' הורדנו הי"ו אל שלפניה והנה קס"ד חלקנום על כפל השרש המוצא שהוא י"ח ועלה ט' והוא השרש היוצא ונכתבם בטור השרש ברביעית לאחור במדרגת קס"ד ערכנום על כפל השרש המוצא ועל עצמם והעולה גרענו מהטור העליון ונישאר בו א'ח'א'ח'א' חלקנום על כפל השרש המוצא והוא על צד הקודם י"ח אחדים וב' עשיריות ועלה אחד בראשונה בקרוב ונכתבהו בראשונה בטור השרש ערכנוהו על כפל השרש המוצא ועל עצמו וגרענו העולה מהטור העליון ולא נשאר בטור העליון דבר והנה שרש זה המספר הדרוש הוא ט' אלפים וצ"א והוא המבוקש...
הרלב"ג מציג את האלגוריתם למציאת שורש ריבועי של מספר ריבועי, ולאחר השיטה הוא נותן דוגמה למציאת השורש הריבועי של  82646281 ומראה איך לחשבו, ואכן מקבל את התשובה והיא  9091, שכן  {\sqrt {82646281}}=9091.
הרעיון בשיטה זו של הרלב"ג הוא לבנות את השורש של מספר  N ריבועי, ספרה אחר ספרה, תוך שהוא מוודא שהריבוע של כל שלב בהערכת השורש, עדיין קטן מהמספר המקורי.
הסבר אלגוריתמי בשפה מודרנית לאלגוריתם של הרלב"ג לחישוב השורש הריבועי של מספר  N:
נחלק את כל ספרות המספר מימין לשמאל לזוגות, ונספור את מספר הזוגות. במצב הזה יישאר זוג ספרות בצד שמאל או מספר בודד. נסמן ב- P את מספר הזוגות, בלי הזוג האחרון/הספרה האחרונה, ונסמן ב- M את המספר (בעל ספרה אחת או שתיים) שנשאר בצד השמאלי. לדוגמה, עבור  N=82646281 נקבל  P=3 ו- M=82.
נמצא את המספר הריבועי הגדול ביותר שקטן מ- M, ונסתכל על השורש הריבועי שלו ולאחריו  P אפסים - זה יהיה הקירוב הראשון לשורש של  N, ונסמנו ב- A. בדוגמה מסעיף 1, נקבל כי המספר הריבועי הכי גדול שקטן מ- M הוא  81 כך ש: {\sqrt {81}}=9 , ולכן:  A=9000.
נסמן את השארית  R=N-A^{2}. בדוגמה שלנו,  R=82646281-9000^{2}=1646281.
כעת, נחלק את  R ב- 2A, ונסמן את התוצאה ב- B כך שאנחנו מתעלמים מכל הספרות פרט לספרה המובילה (השמאלית ביותר). כעת נרצה לבדוק כי  2AB+B^{2} לא גדול יותר מ- R. אם כן נקטין את הספרה המובילה ב-1 ונבדוק שוב. בדוגמה שלנו  {R \over {2A}}={1646281 \over {2\cdot 9000}}\approx 91.46... ולכן נסמן  B=90. מתקיים כי  2AB+B^{2}=2\cdot 9000\cdot 90+90^{2}=1628100 וזה אכן קטן מ- R - כדרוש.
נסמן  {\tilde {R}}=R-(2AB+B^{2}) ו- {\tilde {A}}=A+B. בדוגמה שלנו:  {\tilde {R}}=1646281-(2\cdot 9000\cdot 90^{2})=18181 ו-  {\tilde {A}}=9000+90=9090.
כעת, אם קיבלנו כי  {\tilde {R}}=0 סיימנו, ונקבל כי השורש הריבועי של  N הוא  {\tilde {A}}, כלומר  {\sqrt {N}}={\tilde {A}}. אחרת, נסמן  R={\tilde {R}} ו- A={\tilde {A}} ונחזור איתם לשלב מספר 4.
דוגמה מלאה לחישוב השורש הריבועי של  N=16384 בעזרת האלגוריתם הנ"ל:
מתקיים כי  P=2 ו- M=1.
מחישוב נקבל כי  A=100.
R=16384-10000=6384.
B={6384 \over {200}}\approx 30, אבל  2AB+B^{2}=2\cdot 100\cdot 30+30^{2}=6900 גדול מ- 6384. לכן נסמן  B=20.
{\tilde {R}}=6384-(2\cdot 100\cdot 20+20^{2})=1984, ו- {\tilde {A}}=100+20=120.
קיבלנו כי  {\tilde {R}}\neq 0 לכן נחזור לשלב 4 עם  R={\tilde {R}},A={\tilde {A}}.
B={1984 \over {240}}\approx 8 ולכן  B=8.
{\tilde {R}}=1984-(2\cdot 120\cdot 8+8^{2})=0 ובנוסף  {\tilde {A}}=120+8.
קיבלנו כי  {\tilde {R}}=0 ולכן נקבל כי  {\sqrt {N}}={\sqrt {16384}}={\tilde {A}}=128, כנדרש.
בחלק זה ישנם מספר אלגוריתמים דומים לאלגוריתם שהוצג, המשמשים לביצוע חישובים מסוגים שונים. אחד מהם הוא אלגוריתם לחישוב שורש שלישי של מספרים, באופן יחסית דומה לאלגוריתם לחישוב שורש ריבועי, עם הסתמכות על הזהות:  (a+b)^{3}=a^{3}+3ab(a+b)+b^{3} שאותה הוכיח בחלק הראשון של הספר בטענה מספר 62: "ס"ב) כאשר היו שני מספרים מונחים הנה המעוקב ההוה ממקובצם מוסיף על המעוקב ההוה מהמספר הראשון מהם כמו שלשה דמיוני השטח ההוה משטח המספר הראשון המונח בשני על מקובצם וכמו מעוקב המספר השני".
במקום הזהות  (a+b)^{2}=a^{2}+2ab+b^{2} שאותה הוכיח גם בחלק הראשון של הספר בטענה מספר 6:
ו) כאשר נוסיף על מספר מונח מספר מה הנה מרובע שני המספרים מחוברים שוה למרובע המספרים ההם ולכפל שטח זה בזה
קיים שוני בין עבודתו המתמטית של הרלב"ג כפי שהיא מתבטאת בחלק ב' לבין עבודתם של קודמיו. השוני מוצג בשליטה שלו באלגברה, כפי שמתבטא בזהויות שבהן השתמש כדי למצוא שורשים לעומת הגישה הגאומטרית שהייתה יותר מקובלת בזמנו.