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

[Justin Holmgren]

Function application has higher precedence than exponentiation

On Fri, Nov 27, 2015 at 9:04 PM, Romain Gehrig <romain.gehrig at gmail.com>
wrote:

> 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
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20151127/128ce469/attachment.html>