drblanco white at u.washington.edu
Wed Jan 28 19:42:49 EST 2009

```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
| x<y =	sum
| 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
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;
x=r; y=1;

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

}
sum*=4;
sum++;

return sum;
}

--
View this message in context: http://www.nabble.com/C-like-Haskell-tp21717584p21717584.html