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

[ratzes at gmail.com]

Wow, nice catch!

> On Nov 27, 2015, at 9:21 PM, Justin Holmgren <holmgren at mit.edu> wrote:
> 
> 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
> 
> _______________________________________________
> 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/20151128/75a82e42/attachment.html>