Re: [Haskell-cafe] A few questions on primes generating.

On 13/08/07, Pekka Karjalainen wrote:

On 8/13/07, L.Guo wrote:

...

Hi All:

Hello,

...

I am reading http://www.haskell.org/haskellwiki/Prime_numbers

The code in sector "1 Bitwise prime sieve".

I have 3 questions about it.

1) In function go, what does the number 46340 mean ? Is it sqrt(MAX_LONG) ?

Yes, it appears so. In a 32 bit implementation I get:

Prelude> sqrt $ fromIntegral (maxBound :: Int) 46340.950001051984

...

2) We have this type definition : pureSieve :: Int -> Int Why there is no error (type mismatch) of this call in func main : pureSieve 10000000

If you have integer literals in your program, the compiler sees a fromInteger in front of them. So the value is just converted to type Int automatically, because that is expected here.

You can give different numeric default declarations in your own modules. Please see sections 10.3 (for overloaded literals) and 10.4 (for defaults) here: http://www.haskell.org/tutorial/numbers.html

Sometimes you can get an overflow like this:

Prelude> 100000000000000000000000 :: Int -159383552

...

3) In main again, what does expression [| x |] mean ? Why this cannot be execute in GHCi ?

It's Template Haskell, and is used there for some kind of optimisation (I think). Template Haskell needs to be enabled with a command line switch for it to work. Please see the documentation for more information. It's section 7.6 in your User's Guide.

Though in this case you can probably just remove it to try out the program. Perhaps someone else can explain what actual effect it has here.

I think it just computes a single function call to pureSieve at compile time. I believe its origin is from making a point that when you stop comparing apples to apples it's easy to cheat (this code comes from a discussion on this list where someone insisted on adding optimizations to the, admittedly naive, algorithm in C# and comparing it without making the same optimizations in Haskell -- so someone, I forget who but I'm a search will turn it up, wrote a quick template Haskell "optimization" to make a point that we don't really get useful results unless we compare the same algorithms in both languages). In general you should probably ignore that TH bit and just call pureSieve normally. -- Sebastian Sylvan +44(0)7857-300802 UIN: 44640862