The Haskell code works with arbitrary precision
Integer, the C code with a fixed size int.
This is also a work for a library (BTW like Haskell does), you can use
gmp or mpfr. This will just add one line to store x/2 in y and avoid its
recomputation. You will also have to switch from intset to set. And
there one can start to see the difference. The code refactoring will be
longer since C doesn't support parametric polymorphism nor operator
overloading.
Yes, Haskell is just great, so many things are hard-wired. Even if you
use arbitrary precision Integer and appropriate set implementations,
there is still no infinite, lazy list that avoids recomputation... I
guess your C code either uses some non-standard includes or does not fit
on a single page anymore.
Just for the record: Using a 64-bit machine (1.5GHz Itanium2) and a well
scaling intset (Judy1), (something like) your C code calculates:
* within 1GB and in about 25 mins:
a_{892163852} = 11314755057
max seen so far:
a_{846081651} = 770163004735488 (50 bit)
* and within 32GB and in about 22 hours:
a_{28515445370} = 165480993670
max seen so far:
a_{25880571766} = 32905425960566784 (55 bit)
I guess that a Haskell program that verifies these values will depend on
an external intset implementation. Or uses another data structure, for
example some Set_of_Intervals...
/BR, Mirko Rahn
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
