[Haskell-cafe] C-like Haskell

[drblanco]

I'm trying to do a calculation for Gauss' circle problem, which counts the
integer lattice points with distance to the origin <= r.  It's sequence
A000328 on the AT&T integer sequence database.  I can't figure out a way to
do it quickly in Haskell for r around 10^9.

Here's my attempt, which takes about 75s for r=10^8.

circ2 r = (1+4*r) + 4 * (circ2' (rs+1) r 1 0)
          where
            rs = r^2
--            circ2' :: Int64 -> Int64 -> Int64 -> Int64 -> Int64                        
            circ2' rad x y sum
                | x<y =	sum
                | rad<=rs = circ2' (rad+1+2*y) x (y+1) (sum+1+2*(x-y))
                | otherwise = circ2' (rad+1-2*x) (x-1) y sum

The commented out line was to try to force it to use machine-size ints, but
instead it made it eat memory like mad.  It overflows if everything is
forced to be ints, and isn't much faster.  Making rad and sum Integers fixes
the overflow but still takes ~45 secs.

I do already have the number I wanted, but was wondering how this could be
made faster, or even why it's so slow.  This is all on GHC 6.8.3 under OS X
Intel, using ghc -O2.

For comparison, the C code below runs in <1 second.


typedef unsigned long long bigint;

bigint gausscount(bigint r) {
        bigint sum=0;
        bigint x, y;
        bigint rs=r*r;
        bigint rad=rs+1;
        x=r; y=1;

        while (y<x) {
                while (rad>rs) {
                        rad-=2*x;
                        rad++;
                        x--;
                }
                sum+=1+2*(x-y);
                rad+=2*y+1;
                y++;

        }
        sum*=4;
        sum++;

        return sum;
}

-- 
View this message in context: http://www.nabble.com/C-like-Haskell-tp21717584p21717584.html
Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.