[Haskell-cafe] Why was this function that fast ?

[Romain Gehrig]

Hi,

I implemented a function to count how many steps it takes for a number to be reduced to 1 using the Collatz Conjecture (also known as the 3n + 1 problem) and I was very surprised to see it working instantaneously for integers as big as 10^100000.

The said function:

collatzSteps :: Integer -> Integer
collatzSteps n = steps 1 n
    where steps acc 1 = acc
          steps acc n' | even n' = steps (acc+1) (n' `div` 2)
          steps acc n'           = steps (acc+1) (n' * 3 + 1)

You can try in GHCi (apparently with an upper limit of 10^199669):

GHCi> collatzSteps 10^199668
[big num...]
GHCi> length $ show $ collatzSteps 10^199668
168740 
GHCi> collatzSteps 10^199669 -- Oops
[1]    36128 bus error  ghci

Notice the number 168740: it is the number of digits for the number of steps. It implies that the `acc` is ~= 10^168740 when the function ends. Without optimisation at some point, it would mean there were as much (acc+1) calls ! My understanding completely stops there; I can't comprehend why a function that shouldn't return anything even long after the end of the universe just finished before my eyes.

Can someone shed some light on how this peculiar function was optimised by GHC?

Many thanks,

(still dazed) Romain

[Justin Holmgren]

Function application has higher precedence than exponentiation

_______________________________________________
Haskell-Cafe mailing list
Haskel...@haskell.org
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe

[rat...@gmail.com]

Wow, nice catch!