[Haskell-cafe] Re: New slogan for haskell.org
Laurent Deniau
laurent.deniau at cern.ch
Thu Nov 29 08:17:07 EST 2007
Mirko Rahn wrote:
>
>> The following code is the direct translation of your Haskell code
>
>> void f(int x, intset s) {
>> printf("%d, ", x);
>> f (intset_elem(s, x/2) ? 3*x : x/2, intset_put(s, x));
>> }
>
> No, not that easy. The Haskell code works with arbitrary precision
> Integer, the C code with a fixed size int. On a 32 bit machine, try to
> calculate a_{1805133}, which equals to 19591041024. Or a_{8392780} =
> 26665583616. Or a_{8500000} = 10804333. These values are calculated with
> the Haskell program in 370s and ~1GB memory usage.
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.
> Fair enough, on the same machine a C program (*two* pages long) was able
> to calculate a_{23448481} = 594261577728 and a_{25000000} = 192365946 in
> 50s and ~1GB memory usage.
;-)
a+, ld.
More information about the Haskell-Cafe
mailing list