algorithm - 整数 数字的平方根

Question

并不是我不明白如何求一个数的整数平方根。我知道使用 Python 和 C++ 查找它们的几种方法。

只是这个算法实在是太搞乱我的大脑了。而且必须用 SML 编写它是另一个令人头疼的问题。

请帮助我理解这个算法。请注意，这应该使用递归:

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

描述中缺少的部分是所谓的递归的基本情况。这很简单，但有必要指定:0 的整数平方根是 0。通过使用当前值的四分之一(整数除法)的值重复递归，您最终将得到该基本情况。

我不太熟悉 SML，但我相信它应该是这样的:

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;