In the book "The Haskell Road to Logic, Maths and Programming", the authors present two alternative ways of finding the least divisor k
of a number n
with k > 1
, claiming that the second version is much faster than the first one. I have problems understanding why (I am a beginnner).
Here is the first version (page 10):
ld :: Integer -> Integer -- finds the smallest divisor of n which is > 1
ld n = ldf 2 n
ldf :: Integer -> Integer -> Integer
ldf k n | n `rem` k == 0 = k
| k ^ 2 > n = n
| otherwise = ldf (k + 1) n
If I understand this correctly, the ld
function basically ends up iterating through all integers in the interval [2..sqrt(n)]
and stops as soon as one of them divides n
, returning it as the result.
The second version, which the authors claim to be much faster, goes like this (page 23):
ldp :: Integer -> Integer -- finds the smallest divisor of n which is > 1
ldp n = ldpf allPrimes n
ldpf :: [Integer] -> Integer -> Integer
ldpf (p:ps) n | rem n p == 0 = p
| p ^ 2 > n = n
| otherwise = ldpf ps n
allPrimes :: [Integer]
allPrimes = 2 : filter isPrime [3..]
isPrime :: Integer -> Bool
isPrime n | n < 1 = error "Not a positive integer"
| n == 1 = False
| otherwise = ldp n == n
The authors claim that this version is faster because it iterates only through the list of primes within the interval 2..sqrt(n)
, instead of iterating through all numbers in that range.
However, this argument doesn't convince me: the recursive function ldpf
is eating one by one the numbers from the list of primes allPrimes
. This list is generated by doing filter
on the list of all integers.
So unless I am missing something, this second version ends up iterating through all numbers within the interval 2..sqrt(n)
too, but for each number it first checks whether it is prime (a relatively expensive operation), and if so, it checks whether it divides n
(a relatively cheap one).
I would say that just checking whether k
divides n
for each k
should be faster. Where is the flaw in my reasoning?