Count how often I can divide

The following function counts how often I can divide one number by another:

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

Is there a shorter way to write divs?

My variant would be:

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

The iterate/map pattern is very useful for many problems.

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

And more efficient too! Note that quotRem, which behaves differently with negative values, is a tiny-tiny bit more efficient still.

Okay, the real question here is this: you are doing a search among the list [0..] for the last value m for which p^m divides n. Currently, you're doing the search in order, running up the list linearly. Is there any better search?

I don't know for sure, but perhaps you can do a bit better by jumping forward more quickly at the beginning until you've got upper and lower bounds on m. For example, one way would be to guess an upper bound (say, 1), then repeatedly double it until it really is an upper bound; the algorithm then looks a lot like repeated squaring:

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 -}

You might imagine several other search strategies, once the question is framed in this form, but this one is simple and should be about twice as fast if you expect large values of m to be common.

edit: whoops, looks like I was answering "is there any way to write it faster" rather than "is there any way to write it shorter"

import Control.Arrow

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

Rube Goldberg would be proud of me...

[Edit]

This looks better:

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

What you are doing is calculating a logarithm. Maybe you can use Haskell's log function to do this.

For example:

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