Haskell - Different log methods

Question

I'm pretty new to Haskell and was playing around with some number manipulation in different bases when I had to write an integer logarithm function for my task.

I don't mean discrete/modular logs, but simply greatest x s/t b^x <= n

I developed a few versions and can't decide which I like best. Was hoping to hear what some of you think, or if you have other alternatives to suggest

All have signature: intlog :: (Integral a) => a -> a -> a

intlog :: (Integral a) => a -> a -> a
intlog n b
    | n < b = 0
    | otherwise = succ (intlog (div n b) b)

intlog' :: (Integral a) => a -> a -> a
intlog' n b = maximum [i | i<-[0..n], b^i <= n]

logg = log . fromIntegral
intlog'' :: (Integral a) => a -> a -> a
intlog'' intlog n b = floor $ logg n / logg b

The 'best' one relies on haskell's standard natural log function which I was hoping to avoid (as an exercise) and somewhat messy type conversion. Of the remaining two, one is probably fastest but seems nearly procedural in nature. The other feels very functional and 'haskelly' (looking for word analogous to pythonic, meaning in haskells best style) but i cant see it being too efficient unless there is really really good optimization under the hood.

Would love to hear what you guys think.

BTW - i know that for the second one, intlog' i could find a better upperbound than n but im looking for feedback and/or different way to code it. not incremental improvement like that

Answer 1

The problem with your intLog' function is definitely that it goes through all n numbers in the list. As a result of this it takes ages for large n (for n = 2^130 it ran until I killed it, while your other solutions all returned the result instantly).

The reason that it has to go through all the numbers is of course that using a condition in a list comprehension is like using filter and does not make use of the fact that once the condition is false for the first time, it will always be false thereafter. What you should use instead is takeWhile which takes elements from the list while the condition is true and then stops the first time the condition is false. This way the code would look like this:

intlog n b = maximum $ takeWhile (\i -> b^i <= n) [0..]

Since it will no longer go through the list to its end, we also no longer need to pick an upper bound and can just leave it off. This function will instantly return a result like the other solutions.

---

Of course, except for learning purposes, the best solution is still to just use the built-in functionality with conversion as there is no point reinventing the wheel. Regarding that you should note that you can use the prelude function logBase instead of dividing the logs of n and b.