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.

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.