-4

Let's say I have an integer n and I want to find the largest number m for which the square of that number is smaller than n.

What would be the optimal solution for this problem?

dmckee --- ex-moderator kitten
  • 98,632
  • 24
  • 142
  • 234
Simon
  • 4,999
  • 21
  • 69
  • 97
  • 3
    Start by doing some research: http://en.wikipedia.org/wiki/Methods_of_computing_square_roots – Marc B Mar 07 '13 at 17:58
  • possible duplicate of [Fastest way to get the integer part of sqrt(n)?](http://stackoverflow.com/questions/4930307/fastest-way-to-get-the-integer-part-of-sqrtn) – NPE Mar 07 '13 at 17:58
  • is m an integer also? – David Hope Mar 07 '13 at 17:58
  • Your title answers the question already. Include the library and use the sqrt function, then cast that from a double to an int. If you use a float, you may face inaccuracy problems when dealing with larger numbers. – user123 Mar 07 '13 at 17:59
  • I cannot do cast from sqrt. I am not allowed to use sqrt. – Simon Mar 07 '13 at 18:01
  • Oh, damn, my bad. I read that without as while. Derp. In that case, I agree with Marc. (Unless you shouldn't be using sqrt in the sense that you should be avoiding Square Roots for the solution completely). – user123 Mar 07 '13 at 18:01
  • Use the "Babylonian Method" which is basicaly an application of the Newton-Raphson method. The link was posted by Marc B. – Axel Kemper Mar 07 '13 at 18:05
  • The Babylonian method is really not what he needs. It is used to find the square root, which is not what he wants. He just wants to find the floor of the square root. A simple search on integers will be perfect. You start with some number with half of the digits of your number, and you square it. If it's bigger than your number, you try smaller, and vice versa. – bruce_ricard Mar 07 '13 at 18:10
  • Not sure why this question was "closed as not a real question" and why double squeeze says Babylonian method is not applicable. The question and answer were exactly what I was looking for. I read this question as being same as http://stackoverflow.com/questions/4930307/fastest-way-to-get-the-integer-part-of-sqrtn which has other good answers as well. – Don Hatch Feb 16 '14 at 03:34

2 Answers2

9

"The Optimal Solution" rarely exists, but a reasonably fast algorithm is as follows (anyone knows its name?), it's called the Babylonian Method:

int num = 4567;

int r1 = num / 2;
int r2 = 2;

while (std::abs(r2 - r1) > 1) {
     r2 = (r1 + r2) / 2;
     r1 = num / r2;
}

Here r1 and r2 are the lower and higher approximations of the square root. In your case, you'll need the smaller one.

1

Since you're just looking for the integer part, you could do it this way:

  1. Start a loop with the lowest possible m, ie m=1 ( unless you're allowing n < 1 )
  2. Check if m*m is greater than n
  3. If it's not, you need to check the next m, so add 1 to m and go on to the next iteration of the loop
  4. If it is bigger, then stop looping and subtract 1 from m, because m-1 was the final value to be smaller than the square root of n.
int n = 123; //or whatever you want
int m = 1;
while (m * m <= n) {
    m = m + 1;
}
return (m - 1);
jonhopkins
  • 3,844
  • 3
  • 27
  • 39