Is this mingw bug ?

Question

Hi, I have been trying to execute this program on my migw ,through code::blocks,

#include <string.h>
#include <math.h>
#include <stdio.h>
#define N 100
int p[N];
int pr[N];
int cnt;

void sieve()
{
   int i,j;
   for(i=0;i<N;i++) pr[i]=1;
   pr[0]=pr[1]=0;

   for(i=2;i<N;i++)
      if(pr[i])
        {
         p[cnt]=i; cnt++;
         for(j=i+i;j<=N;j+=i) pr[j]=0;
        }

  }

int main(){
    sieve();
    int i;
    for(i=0;i<cnt;i++)
       printf("%d ",p[i]);
    puts("");
   printf("Total number of prime numbers : %d",cnt);
  return 0;
}

In My system the output is :

7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 Total number of prime numbers : 22

Which is completely insane,since I am completely sure about the implementation of my algorithm.

So I decided to try it in Ideone where it gives correct output.Can anybody point out the reason ?

EDIT:I changed it to N,but the output doesn't change. :|

Answer 1

Your array, p, only has one element since you're declaring it with the integer division, 100/64.

Change it to

int p[N];

or something that has at least 25 elements.

Answer 2

No, it's actually known as a Debanjan bug :-) Have a look at this:

#define N 100
int p[N / 64];

It looks to me like you only allow enough space to store one prime in the p array. That means writing to p[X] for X > 0 is likely to overwrite other values.

This is the dreaded undefined behavior which means that anything can happen (including it working as in the Ideone situation).

Just use:

int p[N];

to declare the array. I'm pretty certain there won't be more than 100 primes less than or equal to 100 :-)

Answer 3

The array p is too small and you are going to overrun it and write into pr.

Change:

int p[N / 64];

to:

int p[N / 2];

---

Foonote: never assume a compiler bug just because you see a problem that you can't immediately explain. 99.999% of the time it will be your bug - you just haven't found it yet.

Answer 4

100/64 is 1. So the p has only one element - p[0]. When you access p[1], p[2], etc you start overwriting elements in pr array. Which produces wrong result.

This is a bug in your program, not a mingw bug.

Answer 5

No. I don't believe that there is a MinGW bug in this case.

There is a bug in your application. As people previously mentioned the p array has only 1 element. (100/64 = 1 when dealing with integer values).

This means that when you access after p[1] or p[2] or p[3] (out of array bounds) you will actually access the zone memory after p which is the pr array.

With Ideone I believe it is possible that the memory zones of the arrays can be at greater distance, not one after the other like in the MinGW case (this is just an assumption).

Answer 6

There are two important bugs in your code.

One is that your p array is too small, so you are writing off the end of it. This is undefined behaviour, though on the platforms you are using it overwrites the start of the pr array. This has no effect on the output, since the location you are overwriting is before the location you are testing in the sieve.

The other is that you are also writing off the end of your pr array:

        for(j=i+i;j<=N;j+=i) pr[j]=0;

This loops sets pr[N] to zero, which is off the end of pr. In MinGW this is where cnt is stored, so each time i divides N, cnt is set to zero. As N is 100, this happens for i==2 and i==5, so you lose the primes before five from your result. IdeOne seems to put cnt somewhere else in relation to pr, so it does not get overwritten. This is why you get different output with the different compilers.

Change the size of the array p to N, or use only one array for both sieve and output, and change <= in line 18 to < so you don't write off the end of it.

int p[N];
int *pr = p; // reuse the array