# Segmentation Fault

Discussion in 'C Programming' started by Rahul, Sep 1, 2009.

1. ### RahulGuest

Hello Friends ~

We have the assignment to write efficient function to decide if an integer
is a square. An integer n is a square if n = m * m where m is an other
integer. Then write a test program to show whether the first ten integers
are squares.

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.

Can anyone see what the problem is?

~~ Thanks

#include"stdio.h"
#include"limits.h"
#include"stdbool.h"

static bool squares[INT_MAX]; // automatically initialized to 0, no
memset needed

setupsquares ()
{
int i;
for(i = 0; i < INT_MAX; squares[i * i++] = true);
}

bool
issquare (int i)
{
return squares;
}

printsquare (int i)
{
printf ("%d\t%s\n", i, issquare (i) ? "true" : "false");
}

main ()
{
int i;
setupsquares ();
for(i = 0; i <= 10; printsquare (i++));
}

Rahul, Sep 1, 2009

2. ### Chris McDonaldGuest

Rahul <> writes:

>static bool squares[INT_MAX]; // automatically initialized to 0, no memset needed

Are you sure that you can allocate that many bools
(probably 2147483647 of them) ?

--
Chris,

Chris McDonald, Sep 1, 2009

3. ### NobodyGuest

On Tue, 01 Sep 2009 22:57:48 +0100, Rahul 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.
>
> Can anyone see what the problem is?

> static bool squares[INT_MAX]; // automatically initialized to 0, no

You shouldn't assume that you will be able to allocate an array this
large (on a 32-bit system, INT_MAX is typically 2^31-1, which would
require at least 2GiB of memory).

> setupsquares ()
> {
> int i;
> for(i = 0; i < INT_MAX; squares[i * i++] = true);

If i can go up to INT_MAX-1, then i*i can go up to (INT_MAX-1) squared,
which is outside the bounds of the array. But you almost certainly won't
be able to allocate an array that large (for INT_MAX == 2^31-1,
that's approximately 4 Exabytes).

Nobody, Sep 1, 2009
4. ### Mart.Guest

On Sep 1, 10:57 pm, Rahul <> wrote:
> Hello Friends ~
>
> We have the assignment to write efficient function to decide if an integer
> is a square. An integer n is a square if n = m * m where m is an other
> integer. Then write a test program to show whether the first ten integers
> are squares.
>
> 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.
>
> Can anyone see what the problem is?
>
> ~~ Thanks
>
> #include"stdio.h"
> #include"limits.h"
> #include"stdbool.h"
>
> static bool squares[INT_MAX]; // automatically initialized to 0, no
> memset needed
>
> setupsquares ()
> {
>   int i;
>   for(i = 0; i < INT_MAX; squares[i * i++] = true);
>
> }
>
> bool
> issquare (int i)
> {
>   return squares;
>
> }
>
> printsquare (int i)
> {
>   printf ("%d\t%s\n", i, issquare (i) ? "true" : "false");
>
> }
>
> main ()
> {
>   int i;
>   setupsquares ();
>   for(i = 0; i <= 10; printsquare (i++));
>
>
>
> }

lots of things - but u might want to try turning -Wall on when you
compile. For example you need to include #include <stdlib.h> for the
printf call.Have you tried running it through a debugger (gdb or ddd)
to see where your error occurs?

Mart., Sep 1, 2009
5. ### Mart.Guest

On Sep 1, 11:10 pm, "Mart." <> wrote:
> On Sep 1, 10:57 pm, Rahul <> wrote:
>
>
>
>
>
> > Hello Friends ~

>
> > We have the assignment to write efficient function to decide if an integer
> > is a square. An integer n is a square if n = m * m where m is an other
> > integer. Then write a test program to show whether the first ten integers
> > are squares.

>
> > 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.

>
> > Can anyone see what the problem is?

>
> > ~~ Thanks

>
> > #include"stdio.h"
> > #include"limits.h"
> > #include"stdbool.h"

>
> > static bool squares[INT_MAX]; // automatically initialized to 0, no
> > memset needed

>
> > setupsquares ()
> > {
> >   int i;
> >   for(i = 0; i < INT_MAX; squares[i * i++] = true);

>
> > }

>
> > bool
> > issquare (int i)
> > {
> >   return squares;

>
> > }

>
> > printsquare (int i)
> > {
> >   printf ("%d\t%s\n", i, issquare (i) ? "true" : "false");

>
> > }

>
> > main ()
> > {
> >   int i;
> >   setupsquares ();
> >   for(i = 0; i <= 10; printsquare (i++));

>
> > }

>
> lots of things - but u might want to try turning -Wall on when you
> compile. For example you need to include #include <stdlib.h> for the
> printf call.Have you tried running it through a debugger (gdb or ddd)
> to see where your error occurs?

your functions don't have type declarations from what I can see and
don't return anything? e.g. setupspace?

Mart., Sep 1, 2009
6. ### Beej JorgensenGuest

Rahul <> 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

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

Beej Jorgensen, Sep 2, 2009
7. ### Eric SosmanGuest

Nobody wrote:
> On Tue, 01 Sep 2009 22:57:48 +0100, Rahul wrote:
> [...]
>> for(i = 0; i < INT_MAX; squares[i * i++] = true);

>
> If i can go up to INT_MAX-1, then i*i can go up to (INT_MAX-1) squared,
> which is outside the bounds of the array. [...]

<Self-administered dope slap> I *knew* there was something
else wrong with that line, but I let myself get so beguiled by
the other errors that I missed it entirely. Worse, I posted an
"improvement" that did in fact improve things a little (it avoided
the obvious UB) but failed to correct the rather blatant issue
that I missed and you spotted ...

Thanks, Nobody. <Self-administered dope slap, Take II>

--
Eric Sosman
lid

Eric Sosman, Sep 2, 2009
8. ### Eric SosmanGuest

[OT] Re: Segmentation Fault

Richard Heathfield wrote:
> In <1251844565.627125@news1nwk>, Eric Sosman wrote:
>
> <snip>
>
>> This rule is made to be
>> broken, but not made to be ignored. There's a difference.

>
> Terry Pratchett points out that rules are there to make you *think*
> before you break them. (And Nanny Ogg adds that, when you do break
> 'em, you should break 'em good and hard.)

--
Eric Sosman
lid

Eric Sosman, Sep 2, 2009
9. ### Phil CarmodyGuest

Rahul <> writes:
> #include"stdio.h"
> #include"limits.h"
> #include"stdbool.h"

Why are you defining you own versions of those headers? If you aren't
why are you pretending that you are?

> static bool squares[INT_MAX]; // automatically initialized to 0, no
> memset needed

That latter line will never compile - check your posting settings

> setupsquares ()
> {
> int i;
> for(i = 0; i < INT_MAX; squares[i * i++] = true);
> }

Why miss out INT_MAX - it's a perfectly valid int value?

The answer to that question may give you a little more insight
into at least 2 quite literally bigger problems with the code.

Phil
--
If GML was an infant, SGML is the bright youngster far exceeds
expectations and made its parents too proud, but XML is the
before he had sex, which was rape. -- Erik Naggum (1965-2009)

Phil Carmody, Sep 2, 2009
10. ### Phil CarmodyGuest

Nobody <> writes:
> On Tue, 01 Sep 2009 22:57:48 +0100, Rahul 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.
>>
>> Can anyone see what the problem is?

>
>> static bool squares[INT_MAX]; // automatically initialized to 0, no

>
> You shouldn't assume that you will be able to allocate an array this
> large (on a 32-bit system, INT_MAX is typically 2^31-1, which would
> require at least 2GiB of memory).
>
>> setupsquares ()
>> {
>> int i;
>> for(i = 0; i < INT_MAX; squares[i * i++] = true);

>
> If i can go up to INT_MAX-1, then i*i can go up to (INT_MAX-1) squared

No it can't. i*i can only numerically go up to INT_MAX and down to
INT_MIN. However, it can take on the additional property of being
undefined, and rendering it and the remaining program meaningless.

Phil
--
If GML was an infant, SGML is the bright youngster far exceeds
expectations and made its parents too proud, but XML is the
before he had sex, which was rape. -- Erik Naggum (1965-2009)

Phil Carmody, Sep 2, 2009
11. ### RahulGuest

Hello Chris ~~

That is definitely not the problem. Remember that a bool is one single
bit, so this is 2147483647/8 bytes = less than 300MB. My workstation has
1GB of RAM lots of swap and nothing else is running.

Regards ~~

Chris McDonald wrote:
> Rahul <> writes:
>
>>static bool squares[INT_MAX]; // automatically initialized to 0, no

> memset needed
>
>
> Are you sure that you can allocate that many bools
> (probably 2147483647 of them) ?

Rahul, Sep 2, 2009
12. ### Keith ThompsonGuest

Rahul <> writes:
> Chris McDonald wrote:
>> Rahul <> writes:
>>
>>>static bool squares[INT_MAX]; // automatically initialized to 0, no

>> memset needed
>>
>>
>> Are you sure that you can allocate that many bools
>> (probably 2147483647 of them) ?

>
> That is definitely not the problem. Remember that a bool is one single
> bit, so this is 2147483647/8 bytes = less than 300MB. My workstation has
> 1GB of RAM lots of swap and nothing else is running.

[Top-posting corrected.]

No, a bool is not one single bit; it's at least 8 bits.

And even if your array were only 300 megabytes, the fact that your
workstation has more RAM than that doesn't necessarily mean that you
can create an object that big.

--
Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

Keith Thompson, Sep 2, 2009
13. ### NobodyGuest

On Wed, 02 Sep 2009 10:21:45 +0300, Phil Carmody wrote:

>>> for(i = 0; i < INT_MAX; squares[i * i++] = true);

>>
>> If i can go up to INT_MAX-1, then i*i can go up to (INT_MAX-1) squared

>
> No it can't. i*i can only numerically go up to INT_MAX and down to
> INT_MIN. However, it can take on the additional property of being
> undefined, and rendering it and the remaining program meaningless.

Good point.

It can "conceptually" go up to (INT_MAX-1) squared, except that's not
representable as an "int". A type-cast (e.g. "(long)i * i++") would get
around that issue on a 64-bit system (most of which still have a 32-bit
"int"), but not the memory issue.

Nobody, Sep 2, 2009
14. ### Beej JorgensenGuest

Rahul <> wrote:
>That is definitely not the problem. Remember that a bool is one single
>bit, so this is 2147483647/8 bytes = less than 300MB. My workstation has
>1GB of RAM lots of swap and nothing else is running.

On my system, it segfaults when I try to write out near the end of that
array, FWIW.

total (K)
Mem: 2058708
Swap: 987956

-Beej

Beej Jorgensen, Sep 2, 2009
15. ### Default UserGuest

Re: [OT] Re: Segmentation Fault

Eric Sosman wrote:

> Richard Heathfield wrote:
> > In <1251844565.627125@news1nwk>, Eric Sosman wrote:
> >
> > <snip>
> >
> > > This rule is made to be
> > > broken, but not made to be ignored. There's a difference.

> >
> > Terry Pratchett points out that rules are there to make you think
> > before you break them. (And Nanny Ogg adds that, when you do break
> > 'em, you should break 'em good and hard.)

>

Nanny != Granny.

Brian

--
Day 212 of the "no grouchy usenet posts" project

Default User, Sep 2, 2009
16. ### Morris KeesanGuest

On Wed, 02 Sep 2009 13:37:47 -0400, Rahul <> wrote:

> Remember that a bool is one single bit

printf("%z\n", sizeof(bool));

or if that doesn't convince you,

printf("%z\n", (int)sizeof(bool[8]));

Morris Keesan, Sep 2, 2009
17. ### Falcon KirtaranGuest

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Rahul wrote:
> Hello Friends ~
>
> We have the assignment to write efficient function to decide if an integer
> is a square. An integer n is a square if n = m * m where m is an other
> integer. Then write a test program to show whether the first ten integers
> are squares.
>
> 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.
>
> Can anyone see what the problem is?
>
> ~~ Thanks
>
>
> #include"stdio.h"
> #include"limits.h"
> #include"stdbool.h"
>
> static bool squares[INT_MAX]; // automatically initialized to 0, no
> memset needed
>
> setupsquares ()
> {
> int i;
> for(i = 0; i < INT_MAX; squares[i * i++] = true);
> }
>
> bool
> issquare (int i)
> {
> return squares;
> }
>
> printsquare (int i)
> {
> printf ("%d\t%s\n", i, issquare (i) ? "true" : "false");
> }
>
> main ()
> {
> int i;
> setupsquares ();
> for(i = 0; i <= 10; printsquare (i++));
> }
>

If you want to store a listing like this and use some kind of
proto-dynamic programming solution, if you will, the least you could do
is save memory by storing only one bit for each number, as opposed to an
entire bool. You could do this by storing the list as an array of
unsigned char, and then using the bitwise-and operator to mask out the
irrelevant bits. Then, you could evaluate the result as a boolean.
Your iterator iterates until ceil(sqrt(INT_MAX)). This solution is
O(n^(1/2)) on INT_MAX (your lookups are constant time).

Another solution to this would be to compute the (much shorter) list of
all the squares from 4 to INT_MAX and store them in an array of type
int. Then, you could do binary search to try and find the number in the
array. This solution is actually still O(n^(1/2)) on INT_MAX, because
the complexity of the binary search is O(log(n)) on the number of
squares, so it ends up being O(log(n^(1/2)).

As a hacker, of course, I would take the cheap way out and do it in
constant time with almost no memory, assuming my instructor hadn't
restricted the use of floating-point operations:

//compile with -lm

#include <stdio.h>
#include <math.h>

int main() {
int candidate = 0;
while (scanf("%d", &candidate) >0) {
if (candidate<0) candidate*=-1;
int root = floor(sqrt(candidate)+0.5);
printf("%d is ", candidate);
if (candidate != root*root) printf("not ");
printf("a perfect square.\n");
}
return 0;
};

- --
- --Falcon Darkstar Christopher Momot
- --
- --OpenPGP: (7902:4457) 9282:A431

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.11 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iQIcBAEBAgAGBQJKns2aAAoJEOGPymTbQp7Gpj4QAJKd9cQsSVOH9/vDBdDLFnCU
trhz4ZF4mfn/OSyU/xER8tKTzUlPyVIwU8tYS2Ai1d9lNjWxsf1fZdL/CybnqDFD
kqx9UVMXJAGrGhbu7wTUhD9+syQFAr8m54y8rNtanQ4qNn1d2kCGN1pwUM5cTnUB
Bpzx2NIt8zFInYWJZsHAuEFQydfZsSawP0ZXl3VmQL8f3TVQaH66D1w5a7OlZaJ6
g23oBK6utxpiQlLWSf20LaFOAFPWL9oeuwhCcUFc8L5s2sHvBGtw0Dibq+VyhrFz
y+7O77XhzO902J47ge7IhftkwgshDIzg4LPTA93Po5ciClr+70MfPyAFjZGKKsup
7gUlnp74u0Znz5MbfDP9ovGLy7P6T0Rm6YKdlVmMmnl65P7QnwKS/x/8mqzeqow7
SETpA1jBBmSzcDb/KXWCI0dAHOJnwsp/zUHK4C0k6RrSL0tY0UoUSnHOpjU2HOm/
BKFJ2/TtCIsImSgu9erjdI1Q25hlFx23iHANlkWabVe1xHmjNscQmolk3FNwpUWC
gczgLUL5u8NtoluRGMLE34B+xBHgA70t2wGcK2QN+tPJeyIH7gUKFpK5mvgwxHHH
rxsXwLKx75HnQSes0Z3K
=ny59
-----END PGP SIGNATURE-----

Falcon Kirtaran, Sep 2, 2009
18. ### Keith ThompsonGuest

"Morris Keesan" <> writes:
> On Wed, 02 Sep 2009 13:37:47 -0400, Rahul <> wrote:
>
>> Remember that a bool is one single bit

>
> printf("%z\n", sizeof(bool));

You mean "%zu".

> or if that doesn't convince you,
>
> printf("%z\n", (int)sizeof(bool[8]));

Either the format should be "%zu\n" and the cast should be dropped, or
the format should be "%d\n".

The point, of course, is that C doesn't support objects smaller than 1
byte (which is at least 8 bits), other than bit fields. It would be
nice to have an array of booleans packed 1 bit per element, but C
doesn't provide any direct way to do that (though you can fake it with

--
Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

Keith Thompson, Sep 2, 2009
19. ### Antoninus TwinkGuest

On 1 Sep 2009 at 22:17, Richard Heathfield wrote:
> As another poster has pointed out, INT_MAX is one heck of a lot of
> bools.

Wrong.

By your usual "assume nothing beyond the ISO Standard" bullshit, it
could be as few as 32767 bools. Hardly "one heck of a lot" in the modern
age.

Antoninus Twink, Sep 2, 2009
20. ### Morris KeesanGuest

On Wed, 02 Sep 2009 16:12:59 -0400, Keith Thompson <> wrote:

> "Morris Keesan" <> writes:
>> On Wed, 02 Sep 2009 13:37:47 -0400, Rahul <> wrote:
>>
>>> Remember that a bool is one single bit

>>
>> printf("%z\n", sizeof(bool));

>
> You mean "%zu".

Quite right. I've never knowingly used a compiler/library that supported
'z', ergo I've never used that modifier, and I was misreading the
documentation,
thinking it was a format specifier, not a length modifier.

>> or if that doesn't convince you,
>>
>> printf("%z\n", (int)sizeof(bool[8]));

>
> Either the format should be "%zu\n" and the cast should be dropped, or
> the format should be "%d\n".

Indeed. I had originally written this with "%d", and then incompletely
edited.

Thanks for catching my errors.

Morris Keesan, Sep 3, 2009