Segmentation Fault

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

  1. Rahul

    Rahul Guest

    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
    #1
    1. Advertising

  2. 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
    #2
    1. Advertising

  3. Rahul

    Nobody Guest

    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
    #3
  4. Rahul

    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
    #4
  5. Rahul

    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
    #5
  6. 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

    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
    Beej Jorgensen, Sep 2, 2009
    #6
  7. Rahul

    Eric Sosman Guest

    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
    #7
  8. Rahul

    Eric Sosman Guest

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


    That's headology, that is.

    --
    Eric Sosman
    lid
    Eric Sosman, Sep 2, 2009
    #8
  9. Rahul

    Phil Carmody Guest

    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
    drug-addicted gang member who had committed his first murder
    before he had sex, which was rape. -- Erik Naggum (1965-2009)
    Phil Carmody, Sep 2, 2009
    #9
  10. Rahul

    Phil Carmody Guest

    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
    drug-addicted gang member who had committed his first murder
    before he had sex, which was rape. -- Erik Naggum (1965-2009)
    Phil Carmody, Sep 2, 2009
    #10
  11. Rahul

    Rahul Guest

    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
    #11
  12. 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
    #12
  13. Rahul

    Nobody Guest

    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
    #13
  14. 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
    #14
  15. Rahul

    Default User Guest

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

    >
    > That's headology, that is.


    Nanny != Granny.




    Brian

    --
    Day 212 of the "no grouchy usenet posts" project
    Default User, Sep 2, 2009
    #15
  16. 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
    #16
  17. -----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
    YgvLBvunegGJMTW2fyviUqgvukmitw/cPPWuOxAyWhpeXAbuhT7hXGPWQ9SADiJx
    SETpA1jBBmSzcDb/KXWCI0dAHOJnwsp/zUHK4C0k6RrSL0tY0UoUSnHOpjU2HOm/
    BKFJ2/TtCIsImSgu9erjdI1Q25hlFx23iHANlkWabVe1xHmjNscQmolk3FNwpUWC
    gczgLUL5u8NtoluRGMLE34B+xBHgA70t2wGcK2QN+tPJeyIH7gUKFpK5mvgwxHHH
    rxsXwLKx75HnQSes0Z3K
    =ny59
    -----END PGP SIGNATURE-----
    Falcon Kirtaran, Sep 2, 2009
    #17
  18. "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
    shifts and masks).

    --
    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
    #18
  19. 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
    #19
  20. 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
    #20
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Alex Hunsley
    Replies:
    17
    Views:
    849
  2. Pud
    Replies:
    0
    Views:
    563
  3. Replies:
    0
    Views:
    517
  4. Ivan Vecerina
    Replies:
    0
    Views:
    476
    Ivan Vecerina
    Jun 29, 2003
  5. Vasileios Zografos

    Re: segmentation fault exception handling

    Vasileios Zografos, Jun 30, 2003, in forum: C++
    Replies:
    5
    Views:
    15,575
    Pete Becker
    Jul 1, 2003
Loading...

Share This Page