340. More about computing a square root

שבוע מתמטי טוב 2
Math, Square root computation

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

כעקרון אפשר לחשב שורש של מספר בשיטות שראינו בפעם הקודמת, אבל החסרון של השיטות הוא יעילות זמן הריצה שלהן: יעילות זמן הריצה שלהן הוא $ O\left(\sqrt{n}\right) $.

בכדי לשפר זאת ניתן לשים לב לנקודה הבאה:

הסדרה $ f(n) = n^2 $ היא סדרה עולה. נדמיין אותה כמו מערך אינסופי שבמקום ה$ n $ שלו נמצא הערך $ n^2 $.

כעת, אנחנו מעוניינים למצוא את התא הכי גדול שעבורו מתקיים $ f(n) \ge m $. (לאיזשהו m נתון)

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static int Sqrt(int n)
{
    int left = 1;
    int right = n;
    int currentIndex = (1 + n) / 2;
    while (!(currentIndex * currentIndex <= n &&
        (currentIndex + 1) * (currentIndex + 1) > n))
    {
        if (currentIndex * currentIndex > n)
        {
            currentIndex = (currentIndex + left)/2;
        }
        else
        {
            currentIndex = (currentIndex + right)/2;
        }
    }
    return currentIndex;
}

זו שיטה נחמדה ואנחנו מקבלים פה יעילות חבל על הזמן של $ O \left(\log{n} \right) $.

למרבה הצער יש פה הרבה פעולות כפל, כך שלממש את זה באסמבלי זה לא להיט.

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

אז איך נממש את האלגוריתם? נשים לב ש

$ (a + b)^2 = a^2 + 2ab + b^2 $

ולכן

$ (a + 2^m)^2 = a^2 + 2^{m + 1} \cdot a + 2^{2m} $

כעת נתחיל בחיפוש החזקה הגבוהה ביותר של 2 כך שהריבוע שלה קטן גדול מהמספר:

1
2
3
4
5
6
7
8
9
10
11
int right = 1;
int rightSquared = 1;
while (rightSquared <= n)
{
    right *= 2;
    rightSquared *= 4;
}
int current = right / 2;
int currentSquared = rightSquared / 4;

כעת ננסה להוסיף למספר חזקות של 2 כל עוד זה משאיר את הריבוע שלו קטן מn:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public static int Sqrt(int n)
{
    int right = 1;
    int rightSquared = 1;
    while (rightSquared <= n)
    {
        right *= 2;
        rightSquared *= 4;
    }
    int current = right / 2;
    int currentSquared = rightSquared / 4;
    int currentSuccesorSquared = currentSquared + 2*current + 1;
    int currentPower = current;
    int currentPowerSquared = currentSquared;
    while (!((currentSquared <= n) &&
            (currentSuccesorSquared > n)))
    {
        int additionSquared =
            currentPowerSquared +
            2*currentPower*current +
            currentSquared;
        if (additionSquared <= n)
        {
            currentSquared = additionSquared;
            current = current + currentPower;
            currentSuccesorSquared = currentSquared + 2*current + 1;
        }
        currentPower /= 2;
        currentPowerSquared /= 4;
    }
    return current;
}

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

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

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

המשך שבוע מושרש לטובה.

הערה: יש ערך די מעניין על חישוב inverse square root עבור ערכי float (וייצוג floating point בכלליות) בויקיפדיה (כולל הקוד המקורי מ-Quake שחישב אותו 😃) אם מתעסקים בחישובי שורש.

שתף