Efficient Collatz sequence analysis

Question

I'm new to Haskell, and I'm wondering why my programs are so slow compared to other languages.

Haskell, 6 seconds (x64, -O2):

nextCollatz :: Int -> Int
nextCollatz x = if even x
 then quot x 2
 else 3 * x + 1
collatzLength :: Int -> Int
collatzLength x = if x == 1
 then 0
 else 1 + collatzLength (nextCollatz x)
main = print . show . sum . map collatzLength $ [1..3000000]

Julia, 0.8 seconds (excluding the compilation time):

function main()
 sum = 0
 for i = [1:3000000]
 while i > 1
 i = isodd(i) ? 3 * i + 1 : i >> 1
 sum += 1
 end
 end
 sum
end
println(main())

Maybe the comparison isn't fair, but I'd like to know how to improve my Haskell code to bring it on par with other high-level languages such as Julia and JavaScript.

While memoization and parallelization would definitely help, currently I'm concerned with efficient iteration and arithmetic.

Answer 1

Your initial version - 6.834 seconds.

Version with quot and even operations replaced with bitwise - 6.651 seconds.

This version - 0.928 seconds:

import Data.Bits
tOdd sum 1 = sum
tOdd sum x = tEven (sum + (tEven2 0 x)) (x - 1)
tEven sum x = tOdd (sum + (tOdd2 0 x)) (x - 1)
tEven2 sum x | (x .&. 2) == 0 = tEven2 (sum + 1) (x `shiftR` 1)
tEven2 sum x | otherwise = tOdd2 (sum + 1) (x `shiftR` 1)
tOdd2 sum 1 = sum
tOdd2 sum x = tEven2 (sum + 1) (3 * x + 1)
main = print . show $ tEven (0 :: Int) (3000000 :: Int)

The previous with -O3 -fllvm -optlo-O3 flags - 0.686 seconds.

The previous with all functions supported with INLINE pragma - 0.604 seconds.

More than 10 times faster than initially :)

Yes, low-level numeric operations and iterations are hard in Haskell, the language doesn't suite well for this.

• Alexey Lebedev: OMG, this is impressive. I like your trick with (x .&. 2) and splitting the function into even and odd to save some calls and avoid checking parity. Thank you!

Answer 2

This one is based on my original code with improvements suggested by leventov. Down to 0.7 seconds from the initial 6 seconds thanks to tail recursion and bitwise operations.

import Data.Bits
collatzLength :: Int -> Int -> Int
collatzLength sum x
 | x == 1 = sum
 | testBit x 0 = collatzLength (sum + 2) (shiftR (3*x + 1) 1)
 | otherwise = collatzLength (sum + 1) (shiftR x 1)
main = print $ foldl collatzLength 0 [1..3000000]

Answer 3

Your program is non-portable: you might have an Int overflow. An Int is only guaranteed to hold up to 2²⁹ - 1, though the limit could be larger on some systems.

The Collatz sequence for 159487 goes rather high.

collatzSeq :: Integer -> [Integer]
collatzSeq 1 = [1]
collatzSeq x
 | even x = x : collatzSeq (x `div` 2)
 | otherwise = x : collatzSeq (3 * x + 1)
*Main> maximum $ collatzSeq 159487
17202377752
*Main> (maximum $ collatzSeq 159487) < 2 ^ 29
False

Therefore, you should be using an Int64 or Integer for this problem.

• Alexey Lebedev: Yeah, I ran into this issue when I tried using Word32 and got an overflow on 159487. But Integer and Int64 were 3 times slower than Int in my experiments.
• 200_success: That's weird that Int64 performs slower than Int, if Int is already 64-bit arithmetic on your machine.
• Alexey Lebedev: Yes, that's so weird. In the first example in my answer if I change Int to Int64 the execution time goes up from 0.6 to 20 seconds! But it the second example I've added Int64 and the execution time went down from 0.95 to 0.85. I've checked and rechecked several times.