Does the program still work for numbers less than 2^32-1? Or is the failure occuring in this range?

Kent

Solved

Posted on 2007-10-04

I wrote a program to generate prime numbers, it works correctly for 2^(32-1).

Now I want it to work with 2^32 so I used unsigned values but now the program doesn't work. It fails at different places. I can't figure this out. (The programs doesn't need negative numbers.) What are the things that I need to watch out for when converting from signed -> unsigned. Suggestions?

Now I want it to work with 2^32 so I used unsigned values but now the program doesn't work. It fails at different places. I can't figure this out. (The programs doesn't need negative numbers.) What are the things that I need to watch out for when converting from signed -> unsigned. Suggestions?

22 Comments

Does the program still work for numbers less than 2^32-1? Or is the failure occuring in this range?

Kent

At a 32bit system the maximum unsigned integer is 2^32-1 == 4294967296.

Hence 2^32 == 0 what maybe the cause for your problems.

You may use a 64bit integer (__int64 on Windows or longlong at other OS) to get around.

Regards, Alex

Kdo,

With unsigned values the program fails for certain values less than 2^32-1 and some values greater than 2^32-1.

> You may use a 64bit integer (__int64 on Windows or longlong at other OS) to get around.

Alex,

I can use long long but I am trying to figure out what's causing the program to fail with unsigned values.

If anybody wants to see the program please ask.

What's the algorithm used ? Does it ever try to increment the value above the unsigned int max. limit ?

How did you calculate the 2^32?

unsigned int mx = 4294967296;

That would give mx == 0 as I outlined above. Hence all loops like

for (unsigned int ui = 0; ui < mx; ++ui)

would not be processed.

Please post your code if you still don't know whai is causing your problems.

Infinity08,

I tried two approaches:

1) change all the int's to unsigned int's

2) selectively change int's where necessary

Both cause problems. I tried to carefully spot any problems but I still can't figure it out. Maybe it's obvious to someone having more experience with C programming.

> What's the algorithm used ? Does it ever try to increment the value above the unsigned int max. limit ?

No it doesn't increment beyond UINT_MAX anywhere.

I started with a simple sieve of erathosthenes but I wanted the program to be able to calculate primes upto atleast 10^9 as fast as possible. The most important problem is to save memory so I tried to divide the sieve into many pages. I calculate all the primes in the first page using SOE. Then I use these primes to strike out all the composites in the other pages. Everytime a page is finished, I add all the primes to the list of primes. This technique works - actually I managed to improve/tweak it quite a bit and now it runs pretty fast 10^9 takes 6 secs on my 2.4ghz p4. Memory usage is constant and not more than 1MB. :)

Program follows. this is the original. please help me to use it with unsigned values so that I can calculate primes upto 2^32.

#include <errno.h>

#include <getopt.h>

#include <limits.h>

#include <math.h>

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include <time.h>

/*

* Add all the primes in the page to the list of primes.

* Only sqrt(high) primes are required for calculating

* the higher primes. This results in very low memory usage.

* The higher primes are not stored and will be printed to

* screen or file immediately.

*/

#define fill_primes(s, n) for (m = 0; m < n; m += 2) {\

if (page[m]) {\

c = m + s;\

if (c <= mprime)\

primes[nprimes++] = c;\

if (prnt && c >= l) \

fprintf(fp, "%d\n", c);\

if (c >= l)\

tprimes++;\

}\

}

void usage(char *);

int

main(int argc, char *argv[])

{

char *page, *file, *ep; /* pages are character arrays */

int pgsz = 100000; /* page size */

int c, i, j, k, m, h, s, t;

int strt, end;

int l = 0;

int primes[10000]; /* array to store primes */

int nprimes = 0; /* no. primes in array */

int tprimes = 0; /* total primes. */

int prnt = 0; /* print on screen */

int mprime; /* maximum prime required for calculation */

long a;

extern char *optarg;

extern int optind, optopt;

FILE *fp = stdout;

while ((c = getopt(argc, argv, "f:hp")) != -1) {

switch (c) {

case 'f':

file = optarg;

if ((fp = fopen(file, "w")) == NULL) {

perror("Error: fopen");

exit(1);

}

prnt++;

break;

case 'h':

usage(argv[0]);

exit(2);

break;

case 'p':

prnt++;

break;

case '?':

fprintf(stderr, "Unrecognised option: -%c\n", optopt);

usage(argv[0]);

exit(2);

}

}

if (optind == argc) {

usage(argv[0]);

exit(2);

}

errno = 0;

if (argc - optind == 2) {

a = strtol(argv[optind], &ep, 10);

if (argv[optind] == ep || ERANGE == errno || a > INT_MAX || a < 0) {

fprintf(stderr, "Sorry, given number is invalid or out of range\n");

exit(1);

}

l = a;

optind++;

}

a = strtol(argv[optind], &ep, 10);

if (argv[optind] == ep || ERANGE == errno || a > INT_MAX || a < 0) {

fprintf(stderr, "Sorry, given number is invalid or out of range\n");

exit(1);

}

h = a;

mprime = sqrt(h); /* size of max prime needed */

if (h < pgsz)

pgsz = h;

t = time(NULL);

if ((page = malloc(pgsz * sizeof(char))) == NULL) {

perror("Error: malloc");

exit(1);

}

/*

* The sieve is divided into pages to save memory.

* Fill first page using sieve eratosthenes algorithm. The

* primes found here will be kept in an array and used for

* striking out composites in the other pages.

* We will ignore even numbers throughout for efficiency.

*/

memset(page, 1, pgsz * sizeof(char));

page[0] = 0; /* 1 is not prime */

s = sqrt(pgsz);

for (i = 3; i <= s; i += 2) {

if (page[i-1]) {

for (j = i * 3, k = i << 1; j <= pgsz; j += k)

page[j-1] = 0;

}

}

/* print 2 seperately since we aren't dealing with even no.s */

if (prnt && l <= 2)

fprintf(fp, "2\n");

fill_primes(1, pgsz);

/*

* Do remaining pages.

*/

for (end = pgsz; (h -= pgsz) > 0; ) {

memset(page, 1, pgsz * sizeof(char));

/* Mark the start and end of the page */

strt = end + 1;

if (h < pgsz)

end += h;

else

end += pgsz;

/*

* Strike out all odd multiples of known primes in the page.

* We don't need to check for primes > sqrt(end)

*/

s = sqrt(end);

for (i = 0; i < nprimes && primes[i] <= s; ++i) {

k = end / primes[i];

j = strt / primes[i];

if (strt % primes[i])

j++;

if (j % 2 == 0)

j++;

for (; j <= k; j += 2) {

page[primes[i] * j - strt] = 0;

}

}

fill_primes(strt, end-strt);

}

fprintf(stdout, "%d primes found (%d secs)\n",\

(l > 2) ? tprimes : ++tprimes,time(NULL) - t);

free(page);

// system("PAUSE");

}

void

usage(char *name)

{

fprintf(stderr,

"Prime number generator and checker.\n\n"

"Usage: %s [-f file] [-p] [-h] [low] high\n\n"

" -f save primes to file.\n"

" -p print primes on the screen.\n"

" -h help.\n"

" low find primes >= low.\n"

" high find prime <= high.\n\n", name

);

}

Like I said that the original code.

I made these changes to it:

unsigned strt, end,h, l, s, c;

unsigned long a;

used stroul

used UINT_MAX

But the code fails with either a segfault or a arithmetic exception (SIGFPE) with certain values but it seems to calculate correctly for other. Out of desperation I also tried changing all the int't to unsigned but still same problem.

That is far too less. In case of 200,000,000 I found 11,078,938 primes though I don't know whether the results were ok because of overwriting the primes array.

an unsigned int32 never is greater UINT_MAX and always >= 0.

So, the statment

if (argv[optind] == ep || ERANGE == errno || a > INT_MAX || a < 0) {

turns to

if (argv[optind] == ep || ERANGE == errno || a < 2) {

> (h -= pgsz) > 0;

when h is unsigned, this can only fail when h==0

You spotted the bug. thanks.

But there is still a problem, it segfaults for input greater than 4,294,838,268. looks like there is another bug lying hidden somewhere.

alex,

> >>>> int primes[10000];

That is far too less. In case of 200,000,000 I found 11,078,938 primes though I don't know whether the results were ok because of overwriting the primes array.

since i am actually only storing only primes greater than sqrt(200,000,000) = 1663 primes, the space is more than sufficient.

>>>> used UINT_MAX

an unsigned int32 never is greater UINT_MAX and always >= 0.

Since that's a sanity check for the input, that can't be cause of the problem.

typo,

s/greater than/less than/

This can only stop when h == 0, since unsigned h is never < 0

That can only happen when h is a multiple of pgsz

This can only stop when h == 0, since unsigned h is never < 0

That can only happen when h is a multiple of pgsz

ozo,

Yes, I get it. (I think you missed my earlier post -- please see above)

As a temporary workaround I defined h as long long.

But there seems to be another bug as the program segfaults for input > 4,294,838,268

Title | # Comments | Views | Activity |
---|---|---|---|

Problem in finding output of a program | 11 | 87 | |

using pointers to pointers to write to a two dimensional array | 16 | 82 | |

thread-safe code in c++ | 2 | 60 | |

Need some help with Microsoft Visual Studio C++ 2003 | 5 | 21 |

Join the community of 500,000 technology professionals and ask your questions.

Connect with top rated Experts

**16** Experts available now in Live!