haskell - Haskell中的整数平方根函数

Question

正整数 n 的整数平方根是平方为的最大整数
小于或等于 n。 (例如，7 的整数平方根是 2，9 的整数平方根是 3)。

这是我的尝试:

intSquareRoot :: Int -> Int
intSquareRoot n
    | n*n > n   = intSquareRoot (n - 1) 
    | n*n <= n  = n

我猜它不起作用，因为 n 根据需要随着递归而减少，但是由于这是 Haskell，您不能使用变量来保留原始 n。

Answer 1

... but due to this being Haskell you cant use variables to keep the original n.

我不知道是什么让你这么说。以下是您可以如何实现它:

intSquareRoot :: Int -> Int
intSquareRoot n = aux n
  where
    aux x
      | x*x > n = aux (x - 1)
      | otherwise = x

这足以发挥作用，但它不是一个非常有效的实现。更好的可以在 Haskell's wiki 上找到:

(^!) :: Num a => a -> Int -> a
(^!) x n = x^n

squareRoot :: Integer -> Integer
squareRoot 0 = 0
squareRoot 1 = 1
squareRoot n =
   let twopows = iterate (^!2) 2
       (lowerRoot, lowerN) =
          last $ takeWhile ((n>=) . snd) $ zip (1:twopows) twopows
       newtonStep x = div (x + div n x) 2
       iters = iterate newtonStep (squareRoot (div n lowerN) * lowerRoot)
       isRoot r  =  r^!2 <= n && n < (r+1)^!2
  in  head $ dropWhile (not . isRoot) iters