Re: Segmentation Fault
- From: Beej Jorgensen <beej@xxxxxxx>
- Date: Tue, 1 Sep 2009 23:51:14 +0000 (UTC)
Rahul <nospam@xxxxxxxxxx> wrote:
I believe my code is correct and caches all results in an Array for
efficiency (only look up is needed). But it generates a Segmentation Fault
everytime I run it.
First of all, you need to compile with max warnings set.
c99 -o foo foo.c
foo.c:8: warning: return type defaults to â??intâ??
* foo.c: In function â??setupsquaresâ??:
* foo.c:10: warning: operation on â??iâ?? may be undefined
foo.c: At top level:
foo.c:20: warning: return type defaults to â??intâ??
foo.c:25: warning: return type defaults to â??intâ??
foo.c: In function â??printsquareâ??:
foo.c:22: warning: control reaches end of non-void function
foo.c: In function â??setupsquaresâ??:
foo.c:11: warning: control reaches end of non-void function
The one I've marked is particularly nasty. See this link for more info:
http://c-faq.com/expr/evalorder1.html
You can replace that for-loop with this:
for(i = 0; i < INT_MAX; squares[i * i] = true, i++);
although it would be more idiomatic and clearer to write:
for(i = 0; i < INT_MAX; i++) {
squares[i * i] = true;
}
With this fix, it still dumps core (but it takes a little longer to do
it. :) )
Now I'm going to take you on a little detour, assuming you're on a
Unix-type machine--note the -g on the gcc command line to embed symbolic
debugging info:
$ ulimit -c unlimited # unlimit core dump file size
$ gcc -Wall -Wextra -std=c99 -pedantic -g -o foo foo.c
$ ./foo
Segmentation fault (core dumped)
$ gdb -tui foo -c core
gdb instantly shows me that it crashed on line 10 (the for loop). So I
use "p" to print some values:
(gdb) p i
$1 = 46341
(gdb) p squares[i*i]
Cannot access memory at address 0xffffffff80601bf9
(gdb) p i*i
$2 = -2147479015
Whoa--that's not a good index.
So you're trying to run i all the way up to INT_MAX, square it, and use
that as an index into an array of INT_MAX elements. But because you're
squaring it, as soon as i becomes greater than the sqrt(INT_MAX), you're
going to overflow the int; IOW:
(sqrt(INT_MAX)+1)^2 > INT_MAX;
So what you want is to go up to the square root of the size of your
array.
However, that /still/ doesn't fix it for me, because INT_MAX is so high,
having that huge array is causing problems when I try to populate it. I
don't have enough memory.
Instead, just have the for-loop populate the array up through the first,
say, 100 squares (which means the square array needs to have 100*100
elements). You're only testing the first 10 of those numbers anyway:
$ ./foo
0 true
1 true
2 false
3 false
4 true
5 false
6 false
7 false
8 false
9 true
10 false
Whew!
Now we can argue if this is a good approach, or if just using sqrt()
would be faster. I just wrote a naive program that tested all numbers
between 0 and 1 billion for perfect squares; runtime: 16 seconds,
perfect squares found: 31623. My computer should be able to do
something like 25 million square roots per second...
(I wrote another program to generate perfect squares and compared the
output of the two for verification.)
-Beej
.
- References:
- Segmentation Fault
- From: Rahul
- Segmentation Fault
- Prev by Date: Re: Question : is the answer related to the buffer or to pointers...
- Next by Date: Re: in standard C it is impossible to write a correct program. Why?
- Previous by thread: Re: [OT] Re: Segmentation Fault
- Next by thread: Re: Segmentation Fault
- Index(es):
Relevant Pages
|
