339. Computing a square root

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

בהמשך לאווירת הטיפים האחרונים:

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

1
2
3
4
5
6
7
8
9
10
11
public static int Sqrt(int n)
{
    int currentNumber = 0;
    while (currentNumber * currentNumber <= n)
    {
        currentNumber++;
    }
    return (currentNumber - 1);
}

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

במקום זאת, ניתן לפתור את הבעיה בצורה הבאה: נשים לב ש

$ 1 = 1 \\ 1 + 3 = 4 \\ 1 + 3 + 5 = 9 \\ 1 + 3 + 5 + 7 = 16 \\ 1 + 3 + 5 + 7 + 9 = 25 \\ \dots \\ 1 + 3 + 5 + 7 + \dots + (2n - 1) = n^2 $

לכן אפשר לפתור את הבעיה כך:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static int Sqrt(int n)
{
    int currentOdd = 1;
    int numOfIterations = 0;
    while (n > 0)
    {
        numOfIterations++;
        currentOdd += 2;
        n -= currentOdd;
    }
    return numOfIterations;
}

שימו לב שיותר קל לכתוב קוד שקול לזה בAssembly 😃

המשך יום עם שורשים טובים.

שתף