Haskell中的整数平方根函数 [英] Integer square root function in Haskell

问题描述

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

The integer square root of a positive integer n is the largest integer whose square is less than or equal to n. (E.g. the integer square root of 7 is 2, and that of 9 is 3).

这是我的尝试:

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

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

I'm guessing its not working because n decreases along with the recursion as required, but due to this being Haskell you can't use variables to keep the original n.

推荐答案

...但是由于这是Haskell，您不能使用变量来保留原始n.

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

我不知道是什么让你这么说.这是实现它的方法:

I don't know what makes you say that. Here's how you could implement it:

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

这足够好玩，但是它不是一个非常有效的实现.可以在 Haskell的Wiki 中找到一个更好的版本:

This is good enough to play around, but it's not a very efficient implementation. A better one can be found on 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

这篇关于Haskell中的整数平方根函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！