Why was this function that fast ?

27 Nov 2015

      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

Romain Gehrig

Justin Holmgren

ratzes＠gmail.com

tags

participants (3)