Segmentation Fault

R

Rahul

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++));
}
 
C

Chris McDonald

Rahul said:
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) ?
 
N

Nobody

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

Mart.

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?
 
M

Mart.

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?
 
B

Beej Jorgensen

Rahul said:
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
 
E

Eric Sosman

Nobody said:
]
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>
 
E

Eric Sosman

Richard said:
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.)

That's headology, that is.
 
P

Phil Carmody

Rahul said:
#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
 
P

Phil Carmody

Nobody said:
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
 
R

Rahul

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 said:
Rahul said:
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) ?
 
K

Keith Thompson

Rahul said:
Chris said:
Rahul said:
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.
 
N

Nobody

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

Beej Jorgensen

Rahul said:
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
 
F

Falcon Kirtaran

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
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
YgvLBvunegGJMTW2fyviUqgvukmitw/cPPWuOxAyWhpeXAbuhT7hXGPWQ9SADiJx
SETpA1jBBmSzcDb/KXWCI0dAHOJnwsp/zUHK4C0k6RrSL0tY0UoUSnHOpjU2HOm/
BKFJ2/TtCIsImSgu9erjdI1Q25hlFx23iHANlkWabVe1xHmjNscQmolk3FNwpUWC
gczgLUL5u8NtoluRGMLE34B+xBHgA70t2wGcK2QN+tPJeyIH7gUKFpK5mvgwxHHH
rxsXwLKx75HnQSes0Z3K
=ny59
-----END PGP SIGNATURE-----
 
K

Keith Thompson

Morris Keesan said:
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
shifts and masks).
 
A

Antoninus Twink

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

Morris Keesan

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.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,743
Messages
2,569,478
Members
44,899
Latest member
RodneyMcAu

Latest Threads

Top