Integer Square root of a number

Question

It's not that I don't understand how to find the integer square root of a number. I know several ways of finding them using Python and C++.

It's just that this algorithm is really messing with my brain. And having to write it in SML is another headache.

Please help me in understanding this algorithm. Do note that this should be using recursion:

The integer square root of 𝑛 is the integer 𝑘 such that 𝑘²≤𝑛<(𝑘+1)². The integer square root can be computed using the following inductive process:

1. Compute the integer square root 𝑖 of 𝑚 = 𝑛 div 4 recursively. We then have that 𝑖²≤𝑚<(𝑖+1)².
2. Since 𝑚 and 𝑖 are integers, we have that (𝑚+1)≤(𝑖+1)². We thus have (2𝑖)²≤4𝑚≤𝑛<4𝑚+4≤(2𝑖+2)².
3. Hence we have that the integer square root of 𝑛 is either 2𝑖 or 2𝑖+1.

Write a recursive ML program corresponding to the above algorithm.

Answer 1

The piece that is missing from the description is the so-called base case of the recursion. It is trivial, but necessary to specify: the integer square root of 0 is 0. By repeatedly recursing with a value that is one fourth (integer divison) of the current value, you'll eventually get to that base case.

I'm not fluent in SML, but I believe it should be something like this:

fun intSquareRoot 0 = 0
  | intSquareRoot n = 
    let 
      val m = n div 4 
      val i = intSquareRoot m
      val k = 2 * i + 1
    in 
      if k * k <= n then k
      else k - 1
    end;