A Spoiled Riddle

February 8, 2009

tags: ,
no comments

Here’s a C riddle: The following program was obviously expected to assign 1 to all the prime indices in the array and 0 to all the others.  However, it enters an infinite loop.  Explain.

#define ARR_SIZE 10

 

IsPrime(n)

int n;

{

    int i;

    for (i = 1; i < n; ++i)

        if (n % i == 0) return 0;

    return 1;

}

 

main()

{

    int arr[ARR_SIZE];

    int it;

 

    for (it = 0; it <= ARR_SIZE; ++it)

        arr[it] = IsPrime(it);

}

My first intuition about this was obviously something like “hey, it’s an off-by-one with the array index”.  But an infinite loop?

Let’s cut to the chase: The obvious intent of the riddle’s authors is that arr[10] is essentially the stack location that holds it, our loop variable.  So basically when we overflow the array we reset the index back to IsPrime(10) which happens to be 0 and the loop restarts, indefinitely.

However, the riddle was totally spoiled for me by the following thoughts:

  • Had I run it in Visual Studio, Debug mode, I’d toggle a runtime check failure when the stack around the arr array is corrupted (debug runtime checks would have a canary set up to catch this).
  • Had I run it in Visual Studio, Debug mode, without runtime checks, it would simply exit doing nothing because in Debug there’s enough stack space around each local variable to accommodate a small family.
  • Had I run it in Visual Studio, Release mode, one (or two) of two things would ruin the riddle:
    • The it loop variable is most likely to sit in a register, so overflowing the stack will have no effect on its value whatsoever.
    • Even if it doesn’t sit in a register, the assignments to arr are likely to be eliminated by the optimizer because the program doesn’t seem to need them.  In fact, a smart-enough optimizer would optimize this whole program into a nop.

Running these tests in Visual Studio verified, indeed, that this programming riddle has failed to amuse me.  🙂

Add comment
facebook linkedin twitter email

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*