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

• Aleksi Torhamo: I don't really know haskell, and so can't say which one is best, but intlog'' is clearly the worst, as it will produce the wrong output! log returns floating point values, which aren't always exact - for example 3^5 == 243, but logg 243 / logg 3 == 4.999999999999999, so floor $ logg 243 / logg 3 == 4, instead of the correct 5. (And yes, logBase 3 243 has the same problem)

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.

• jon_darkstar: hah i didnt even know about logBase. but thanks for suggesting the takeWhile that is exactly the kind of thing i was looking for. i liked that solution the best due to its conciseness except for the obvious efficiency problem.
• jon_darkstar: also noticed logBase has arguments with other order, which makes sense since the base is the argument you'd more likely want to curry. i need to get in the habit of thinking like that when specifying argument order
• Aleksi Torhamo: You are right that in most cases one should use the built-in functionality, but we're talking about an integer version of a floating-point function here; Using the built-in log or logBase with conversion in this case will give incorrect results! log and logBase both return floating point values, which aren't always exact - for example 3^5 == 243, but logg 243 / logg 3 == 4.999999999999999, so floor $ logg 243 / logg 3 == 4, instead of the correct 5. (And logBase 3 243 gives the same result, too)