[Hugs] #73: Sieve of Eratosthenes crashes if using "Integer" while not if using "Int"
#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 Keywords: | --------------------+------------------------------------------------------- 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) -- Ticket URL: http://hackage.haskell.org/trac/hugs/ticket/73 Hugs http://www.haskell.org/hugs/ Hugs 98, an interpreter for Haskell
#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
#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: ---------------------+------------------------------------------------------ Comment (by neil): I can replicate this with on Windows. If I compile with Debug I get a stack overflow, which is caught properly. If I compile with Release I get a division by zero error, breaking into the debugger: bignums.c, line 802 is the error Local variables: us -1048576 int vs -247 int gc 2 unsigned int v -247 int sc 0 int ds 0 int v2 5000 int qs 0 int uj2 -248 int v1 9999 int n 5000 int vs1 -247 int qhat 0 int nd 0 int Call stack:
winhugs.exe!digitsQrm(int us=-1048576, int vs=-247) Line 802 +
0x1e bytes C winhugs.exe!bigQrm(int a=0, int b=0) Line 629 + 0x13 bytes C winhugs.exe!primQrmInteger(int root=90) Line 972 C winhugs.exe!eval(int n=-282) Line 1369 + 0x5 bytes C winhugs.exe!run(int start=30675, int root=88) Line 1770 + 0x13 bytes C winhugs.exe!eval(int n=-315) Line 1371 + 0xc bytes C winhugs.exe!primSel(int root=84) Line 695 C winhugs.exe!eval(int n=-317) Line 1369 + 0x5 bytes C winhugs.exe!primEqInteger(int root=81) Line 392 C winhugs.exe!eval(int n=-251) Line 1369 + 0x5 bytes C winhugs.exe!run(int start=1294, int root=76) Line 1767 + 0x16 bytes C winhugs.exe!eval(int n=-268) Line 1371 + 0xc bytes C winhugs.exe!primEqInteger(int root=73) Line 392 C winhugs.exe!eval(int n=-258) Line 1369 + 0x5 bytes C winhugs.exe!run(int start=30681, int root=66) Line 1767 + 0x16 bytes C winhugs.exe!eval(int n=-318) Line 1371 + 0xc bytes C winhugs.exe!run(int start=30858, int root=64) Line 1770 + 0x13 bytes C winhugs.exe!eval(int n=-331) Line 1371 + 0xc bytes C winhugs.exe!primSel(int root=60) Line 695 C winhugs.exe!eval(int n=-340) Line 1369 + 0x5 bytes C winhugs.exe!primEqInteger(int root=57) Line 392 C winhugs.exe!eval(int n=-334) Line 1369 + 0x5 bytes C winhugs.exe!run(int start=137, int root=55) Line 1770 + 0x13 bytes C winhugs.exe!eval(int n=-337) Line 1371 + 0xc bytes C winhugs.exe!run(int start=35059, int root=50) Line 1767 + 0x16 bytes C winhugs.exe!eval(int n=-171364) Line 1371 + 0xc bytes C winhugs.exe!run(int start=35059, int root=47) Line 1770 + 0x13 bytes C winhugs.exe!eval(int n=-171263) Line 1371 + 0xc bytes C winhugs.exe!run(int start=35059, int root=44) Line 1770 + 0x13 bytes C winhugs.exe!eval(int n=-171163) Line 1371 + 0xc bytes C winhugs.exe!run(int start=35059, int root=41) Line 1770 + 0x13 bytes C winhugs.exe!eval(int n=-171063) Line 1371 + 0xc bytes C winhugs.exe!run(int start=35059, int root=38) Line 1770 + 0x13 bytes C winhugs.exe!eval(int n=-170963) Line 1371 + 0xc bytes C winhugs.exe!run(int start=35059, int root=35) Line 1770 + 0x13 bytes C winhugs.exe!eval(int n=-170862) Line 1371 + 0xc bytes C winhugs.exe!run(int start=35059, int root=32) Line 1770 + 0x13 bytes C winhugs.exe!eval(int n=-170762) Line 1371 + 0xc bytes C winhugs.exe!run(int start=35059, int root=29) Line 1770 + 0x13 bytes C winhugs.exe!eval(int n=-170662) Line 1371 + 0xc bytes C winhugs.exe!run(int start=35059, int root=26) Line 1770 + 0x13 bytes C winhugs.exe!eval(int n=-170642) Line 1371 + 0xc bytes C winhugs.exe!run(int start=35117, int root=22) Line 1770 + 0x13 bytes C winhugs.exe!eval(int n=-1048490) Line 1371 + 0xc bytes C winhugs.exe!primBPrint(int root=18) Line 110 C winhugs.exe!eval(int n=-1048486) Line 1369 + 0x5 bytes C winhugs.exe!primHPutStr(int root=14) Line 869 C winhugs.exe!eval(int n=-1048470) Line 1369 + 0x5 bytes C winhugs.exe!run(int start=11031, int root=12) Line 1770 + 0x13 bytes C winhugs.exe!eval(int n=-1048462) Line 1371 + 0xc bytes C winhugs.exe!evalWithNoError(int e=-1048462) Line 1882 C winhugs.exe!primCatchException(int root=10) Line 685 + 0x19 bytes C winhugs.exe!eval(int n=-1048461) Line 1369 + 0x5 bytes C winhugs.exe!run(int start=11071, int root=6) Line 1770 + 0x13 bytes C winhugs.exe!eval(int n=-1048465) Line 1371 + 0xc bytes C winhugs.exe!run(int start=11176, int root=2) Line 1770 + 0x13 bytes C winhugs.exe!eval(int n=-1048482) Line 1371 + 0xc bytes C winhugs.exe!run(int start=11466, int root=0) Line 1770 + 0x13 bytes C winhugs.exe!eval(int n=-1048484) Line 1371 + 0xc bytes C winhugs.exe!evalWithNoError(int e=-1048484) Line 1882 C winhugs.exe!evaluator(int m=2628) Line 181 + 0x19 bytes C winhugs.exe!evaluatorThreadBody(unsigned long * notUsed=0x00000000) Line 245 + 0xb bytes C v1 isn't zero, so I've no idea where/what the division by zero is. Remember that this is optimised code going through a debugger, so it may be a little random, and the accuracy is not guaranteed. -- Ticket URL: http://hackage.haskell.org/trac/hugs/ticket/73 Hugs http://www.haskell.org/hugs/ Hugs 98, an interpreter for Haskell
#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: ---------------------+------------------------------------------------------ Comment (by neil): (Reposting with better wiki syntax, my brain can only hold 3 entirely separate wiki syntaxes at one time...) I can replicate this with on Windows. If I compile with Debug I get a stack overflow, which is caught properly. If I compile with Release I get a division by zero error, breaking into the debugger: bignums.c, line 802 is the error Local variables: {{{ us -1048576 int vs -247 int gc 2 unsigned int v -247 int sc 0 int ds 0 int v2 5000 int qs 0 int uj2 -248 int v1 9999 int n 5000 int vs1 -247 int qhat 0 int nd 0 int }}} Call stack: {{{
winhugs.exe!digitsQrm(int us=-1048576, int vs=-247) Line 802 +
0x1e bytes C winhugs.exe!bigQrm(int a=0, int b=0) Line 629 + 0x13 bytes C winhugs.exe!primQrmInteger(int root=90) Line 972 C winhugs.exe!eval(int n=-282) Line 1369 + 0x5 bytes C winhugs.exe!run(int start=30675, int root=88) Line 1770 + 0x13 bytes C winhugs.exe!eval(int n=-315) Line 1371 + 0xc bytes C winhugs.exe!primSel(int root=84) Line 695 C winhugs.exe!eval(int n=-317) Line 1369 + 0x5 bytes C winhugs.exe!primEqInteger(int root=81) Line 392 C winhugs.exe!eval(int n=-251) Line 1369 + 0x5 bytes C winhugs.exe!run(int start=1294, int root=76) Line 1767 + 0x16 bytes C winhugs.exe!eval(int n=-268) Line 1371 + 0xc bytes C winhugs.exe!primEqInteger(int root=73) Line 392 C winhugs.exe!eval(int n=-258) Line 1369 + 0x5 bytes C winhugs.exe!run(int start=30681, int root=66) Line 1767 + 0x16 bytes C winhugs.exe!eval(int n=-318) Line 1371 + 0xc bytes C winhugs.exe!run(int start=30858, int root=64) Line 1770 + 0x13 bytes C winhugs.exe!eval(int n=-331) Line 1371 + 0xc bytes C winhugs.exe!primSel(int root=60) Line 695 C winhugs.exe!eval(int n=-340) Line 1369 + 0x5 bytes C winhugs.exe!primEqInteger(int root=57) Line 392 C winhugs.exe!eval(int n=-334) Line 1369 + 0x5 bytes C winhugs.exe!run(int start=137, int root=55) Line 1770 + 0x13 bytes C winhugs.exe!eval(int n=-337) Line 1371 + 0xc bytes C winhugs.exe!run(int start=35059, int root=50) Line 1767 + 0x16 bytes C winhugs.exe!eval(int n=-171364) Line 1371 + 0xc bytes C winhugs.exe!run(int start=35059, int root=47) Line 1770 + 0x13 bytes C winhugs.exe!eval(int n=-171263) Line 1371 + 0xc bytes C winhugs.exe!run(int start=35059, int root=44) Line 1770 + 0x13 bytes C winhugs.exe!eval(int n=-171163) Line 1371 + 0xc bytes C winhugs.exe!run(int start=35059, int root=41) Line 1770 + 0x13 bytes C winhugs.exe!eval(int n=-171063) Line 1371 + 0xc bytes C winhugs.exe!run(int start=35059, int root=38) Line 1770 + 0x13 bytes C winhugs.exe!eval(int n=-170963) Line 1371 + 0xc bytes C winhugs.exe!run(int start=35059, int root=35) Line 1770 + 0x13 bytes C winhugs.exe!eval(int n=-170862) Line 1371 + 0xc bytes C winhugs.exe!run(int start=35059, int root=32) Line 1770 + 0x13 bytes C winhugs.exe!eval(int n=-170762) Line 1371 + 0xc bytes C winhugs.exe!run(int start=35059, int root=29) Line 1770 + 0x13 bytes C winhugs.exe!eval(int n=-170662) Line 1371 + 0xc bytes C winhugs.exe!run(int start=35059, int root=26) Line 1770 + 0x13 bytes C winhugs.exe!eval(int n=-170642) Line 1371 + 0xc bytes C winhugs.exe!run(int start=35117, int root=22) Line 1770 + 0x13 bytes C winhugs.exe!eval(int n=-1048490) Line 1371 + 0xc bytes C winhugs.exe!primBPrint(int root=18) Line 110 C winhugs.exe!eval(int n=-1048486) Line 1369 + 0x5 bytes C winhugs.exe!primHPutStr(int root=14) Line 869 C winhugs.exe!eval(int n=-1048470) Line 1369 + 0x5 bytes C winhugs.exe!run(int start=11031, int root=12) Line 1770 + 0x13 bytes C winhugs.exe!eval(int n=-1048462) Line 1371 + 0xc bytes C winhugs.exe!evalWithNoError(int e=-1048462) Line 1882 C winhugs.exe!primCatchException(int root=10) Line 685 + 0x19 bytes C winhugs.exe!eval(int n=-1048461) Line 1369 + 0x5 bytes C winhugs.exe!run(int start=11071, int root=6) Line 1770 + 0x13 bytes C winhugs.exe!eval(int n=-1048465) Line 1371 + 0xc bytes C winhugs.exe!run(int start=11176, int root=2) Line 1770 + 0x13 bytes C winhugs.exe!eval(int n=-1048482) Line 1371 + 0xc bytes C winhugs.exe!run(int start=11466, int root=0) Line 1770 + 0x13 bytes C winhugs.exe!eval(int n=-1048484) Line 1371 + 0xc bytes C winhugs.exe!evalWithNoError(int e=-1048484) Line 1882 C winhugs.exe!evaluator(int m=2628) Line 181 + 0x19 bytes C winhugs.exe!evaluatorThreadBody(unsigned long * notUsed=0x00000000) Line 245 + 0xb bytes C }}} v1 isn't zero, so I've no idea where/what the division by zero is. Remember that this is optimised code going through a debugger, so it may be a little random, and the accuracy is not guaranteed. -- Ticket URL: http://hackage.haskell.org/trac/hugs/ticket/73 Hugs http://www.haskell.org/hugs/ Hugs 98, an interpreter for Haskell
participants (1)
-
Hugs