函数语言中的对数只有加法和乘法

Question

在学习考试时,我刚刚在练习中找到了以下任务:

编写一个函数,将整数对数给予基数2(向上舍入),同时仅使用乘法和加法.

我马上尝试过,但无法解决任何问题.我认为这将是一项简单的任务,但我只能在使用整数除法时找到解决方案(例如在Haskell中):

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

这项任务是否只能通过乘法来完成？在左侧使用乘法(模式)总是会导致编译器错误.在右侧使用它,如何将解决方案追溯到较低的数字？

Answer 1

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

递归.由于计算楼层更容易,我们使用的事实是

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