Логарифм на функциональном языке только со сложением и умножением

Готовясь к экзамену, я только что нашел следующую задачу в упражнении:

Напишите функцию, которая вычисляет целочисленный логарифм по основанию 2 (с округлением вверх), используя только умножение и сложение.

Я попытался сразу же, но не смог прийти к какому-либо решению. Я думал, что это будет простая задача, но я смог найти решение только при использовании целочисленного деления (например, в Haskell):

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

Возможна ли вообще эта задача только с умножением? Использование умножения в левой части (шаблон) всегда приводит к ошибкам компилятора. И, используя его с правой стороны, как я могу отследить решение до меньших чисел?


functional-programming haskell logarithm
person caw    schedule 10.01.2013    source источник
comment
Вы можете сделать это с помощью сложения, умножения и <=. Кроме того, ваш случай для 2 является избыточным в этом примере.   -  person Carl    schedule 11.01.2013
comment
Умножение деления IS   -  person Wes    schedule 11.01.2013
comment
Но я должен использовать Ints, без дробей.   -  person caw    schedule 11.01.2013

Ответы (3)


arrow_upward
5
arrow_downward

И, используя его с правой стороны, как я могу отследить решение до меньших чисел?

Рекурсия. Так как вычислить пол проще, мы используем тот факт, что

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
person Daniel Fischer    schedule 10.01.2013
comment
doLog :: (Num a) => a -> a -> (a, a) или что-то в этом роде. Разве вы не должны проецировать это в случае log2 n | otherwise? ;) - person ; 11.01.2013
comment
Ах, забыл fst, спасибо. Из-за подписи верхнего уровня это doLog :: Int -> Int -> (Int,Int), но, конечно, он также будет работать полиморфно. - person Daniel Fischer; 11.01.2013
comment
Конечно. Однако для этого вам потребуется явно передать m. - person ; 11.01.2013
comment
Я не вижу этого. Зачем нужно проходить m? - person Daniel Fischer; 11.01.2013
comment
Большое спасибо! Очевидно, это работает именно так, как задумано. Но нет ли способа упростить это? - person caw; 11.01.2013
comment
@DanielFischer: в предложении where m :: Int, потому что n :: Int. В первой гвардии doLog, base, acc :: Int потому что m :: Int. - person ; 11.01.2013
comment
@Tinctorius А если n :: t для какого-то (Ord t, Num t), то m :: t и base, acc :: t. Если log2 вызывается для типа a -> r, то doLog наследует тип a -> a -> (b, a) от охранников, не требует передачи m. - person Daniel Fischer; 11.01.2013
comment
@МаркоВ. Думаю, это уже достаточно просто. Конечно, у вас может быть более простой и медленный алгоритм. Это не проблема, я добавлю один. - person Daniel Fischer; 11.01.2013

arrow_upward
3
arrow_downward

Как насчет:

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

?

Я предполагаю, что вы можете использовать функции из Prelude (например, error, fst и операторы сравнения). Если это не разрешено на экзамене, вы теоретически можете использовать определения length, takeWhile и iterate и получить что-то относительно близкое (по духу, возможно, не по букве!) к ответу Дэниела.

person yatima2975    schedule 16.01.2013
comment
Спасибо за эту суперкороткую альтернативу! - person caw; 16.01.2013

arrow_upward
0
arrow_downward

Возможно, вы можете использовать расширение ряда, чтобы аппроксимировать логарифмическую функцию. Особенно Тейлор.

person phaazon    schedule 10.01.2013
comment
Благодарю вас! Я предполагаю, что ничего такого сложного не требуется, только некоторые основные операции со списками. - person caw; 11.01.2013