Посчитай, как часто я могу делить

Question

Следующая функция подсчитывает, как часто я могу делить одно число на другое:

divs n p = if (n `mod` p == 0) then 1 + divs (n `div` p) p else 0

Есть ли более короткий способ написать divs?

Answer 1

Мой вариант будет:

factors :: Integral i => i -> i -> Int
factors f =
    length . takeWhile (== 0) .
    map (`mod` f) . iterate (`div` f)

Шаблон итерации / карты очень полезен для многих задач.

Answer 2

divs n p = case n `divMod` p of (q,0) -> 1 + divs q p; _ -> 0

И еще эффективнее! Обратите внимание, что quotRem, который ведет себя по-разному с отрицательными значениями, все еще эффективнее.

Answer 3

Хорошо, реальный вопрос здесь заключается в следующем: вы выполняете поиск среди списка [0..] последнего значения m, для которого p^m делит n. В настоящее время вы выполняете поиск по порядку, линейно увеличивая список. Есть ли лучший поиск?

Не знаю наверняка, но, возможно, вы можете добиться большего успеха, быстрее прыгая вперед, пока не получите верхнюю и нижнюю границы на m. Например, одним из способов было бы угадать верхнюю границу (скажем, 1), а затем многократно удваивать ее, пока она действительно не станет верхней границей; алгоритм выглядит очень похоже на повторное возведение в квадрат:

upBound p n = if n `mod` p == 0 then 2 * upBound (p^2) n else 1
divs p n = m + divs' p (n `div` (p ^ m)) where
    m = upBound p n `div` 2
    divs' p n = {- your algorithm -}

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

edit: упс, похоже, что я отвечал "есть ли способ написать это быстрее", а не "есть ли способ написать это короче"

Answer 4

import Control.Arrow

divs n d = pred $ length $ takeWhile ((== 0).snd) $ iterate (((`div` d) &&& (`mod` d)).fst) (n,0)

Рубе Голдберг гордился бы мной ...

[Изменить]

Это выглядит лучше:

divs n d = length $ takeWhile ((==0).(`mod` d)) $ scanl div n $ repeat d

Answer 5

Что вы делаете, это вычисление логарифма .Возможно, вы можете использовать функцию Haskell log для этого.

Например:

log(16) / log(2) == 4