Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Weird way of calculating square root [closed]

Tags:

c

math

sqrt

I've been told this code snippet is equivalent to (int)sqrt(n)

int s(int n) {
    for (int i = 1, k = 0; n > 0; i += 2) {
        if (k + i > n)
            return i / 2;
        k += i;
    }
    return 0;
}

And it seem to work, yet I don't understand how it works ?

like image 554
Howard Grey Avatar asked Dec 17 '16 00:12

Howard Grey


People also ask

What is the trick of finding square root?

Step 1: First pair the digits starting from right to left. Step 2: Match the unit digit of number from the chart and determine the possible values of the square root of the unit digit. Step 3: Let us consider the group of the first three digits. Let it be "n".

How many methods are there to find square root?

We can use four methods to find the square root of numbers and those methods are as follows: Repeated Subtraction Method of Square Root. Square Root by Prime Factorization Method. Square Root by Estimation Method.


1 Answers

It uses the fact that x^2 = 1 + 3 + 5 + ... + (2*x-1). Here i goes over the odd numbers and k is their sum. It stops when the sum is more than n. At this point i == (2*x-1) + 2 where x is the square root, so x == floor(i/2).

like image 162
interjay Avatar answered Nov 04 '22 20:11

interjay