#73: Sieve of Eratosthenes crashes if using "Integer" while not if using "Int" ---------------------+------------------------------------------------------ Reporter: guest | Owner: nobody Type: defect | Status: new Priority: minor | Milestone: Component: hugs | Version: 200609 Resolution: | Keywords: ---------------------+------------------------------------------------------ Old description:
The following program crashes near the 5000th prime nr.
sieveGH :: ([Integer], Integer) -> Integer sieveGH ([], y) = 0 sieveGH ((p:xs), 0) = p sieveGH ((p:xs), y) = sieveGH ([x| x <- xs, x `mod` p /= 0], y-1)
While the following does not crash, and i was taught that Integer was designed for near infinite/large calculations(?) :
sieveGH :: ([Int], Int) -> Int sieveGH ([], y) = 0 sieveGH ((p:xs), 0) = p sieveGH ((p:xs), y) = sieveGH ([x| x <- xs, x `mod` p /= 0], y-1)
Main> sieveGH ([2..], 10000) 104743 (505275796 reductions, 696417680 cells, 787 garbage collections)
New description: The following program crashes near the 5000th prime nr. {{{ sieveGH :: ([Integer], Integer) -> Integer sieveGH ([], y) = 0 sieveGH ((p:xs), 0) = p sieveGH ((p:xs), y) = sieveGH ([x| x <- xs, x `mod` p /= 0], y-1) }}} While the following does not crash, and i was taught that Integer was designed for near infinite/large calculations(?) : {{{ sieveGH :: ([Int], Int) -> Int sieveGH ([], y) = 0 sieveGH ((p:xs), 0) = p sieveGH ((p:xs), y) = sieveGH ([x| x <- xs, x `mod` p /= 0], y-1) Main> sieveGH ([2..], 10000) 104743 (505275796 reductions, 696417680 cells, 787 garbage collections) }}} Comment (by ross): What kind of crash is it? What version of Hugs are you using, and on what operating system? With the latest version, under Linux, it (eventually) terminates: {{{ Sieve> sieveGH ([2..], 10000) 104743 (3271774548 reductions, 701928246 cells, 5211 garbage collections) }}} The `Integer` type is appropriate for large numbers, but it takes up extra space, with the associated overheads. In Hugs, it uses extra space even for small numbers. -- Ticket URL: http://hackage.haskell.org/trac/hugs/ticket/73 Hugs http://www.haskell.org/hugs/ Hugs 98, an interpreter for Haskell