3

在学习考试时，我刚刚在练习中发现了以下任务：

编写一个函数，将整数对数以 2 为底（四舍五入），同时仅使用乘法和加法。

我立即尝试，但无法找到任何解决方案。我认为这将是一件容易的事，但我只能在使用整数除法时找到解决方案（例如在 Haskell 中）：

log2 :: Int -> Int
log2 1 = 0
log2 2 = 1
log2 x = 1 + log2 (x `div` 2)

这个任务完全可以用乘法来完成吗？在左侧（模式）上使用乘法总是会导致编译器错误。并在右侧使用它，我如何将解决方案追溯到较低的数字？

4

3 回答 3

5

并在右侧使用它，我如何将解决方案追溯到较低的数字？

递归。由于计算下限更容易，我们使用以下事实

ceiling (log_2 n) == floor (log_2 (2*n-1))

很容易看出。然后为了找到以底为底b的对数，我们计算以底为底的对数b²并进行调整：

log2 :: Int -> Int
log2 1 = 0
log2 2 = 1
log2 n
    | n < 1     = error "Argument of logarithm must be positive"
    | otherwise = fst $ doLog 2 1
      where
        m = 2*n-1
        doLog base acc
            | base*acc > m = (0, acc)
            | otherwise = case doLog (base*base) acc of
                            (e, a) | base*a > m -> (2*e, a)
                                   | otherwise  -> (2*e+1,a*base)

需要更多步骤的更简单算法是简单地迭代，在每一步中乘以 2，然后计数，直到达到或超过参数值：

log2 :: Int -> Int
log2 n
    | n < 1     = error "agument of logarithm must be positive"
    | otherwise = go 0 1
      where
        go exponent prod
            | prod < n  = go (exponent + 1) (2*prod)
            | otherwise = exponent
于 2013-01-10T22:11:27.770 回答
3

怎么样：

log2 n = length (takeWhile (<n) (iterate (*2) 1))

?

我假设您可以使用 Prelude 中的函数（如error,fst和比较运算符）。如果这在考试中是不允许的，理论上你可以使用 的定义length，takeWhile并且iterate最终得到与丹尼尔的答案相对接近的东西（在精神上，可能不是在信中！）。

于 2013-01-16T13:50:00.270 回答
0

也许您可以使用级数展开来近似 log 函数。尤其是泰勒的那些。

于 2013-01-10T22:39:12.980 回答