We help IT Professionals succeed at work.

program doesn't work when using unsigned value

on
316 Views
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?
Comment
Watch Question

View Solution Only

Data Warehouse / Database Architect
CERTIFIED EXPERT

Commented:
Hi nixfreak,

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

Kent

Commented:
>>>> so I used unsigned values
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

Commented:
>>>> the maximum unsigned integer is 2^32-1 == 4294967296.
Of course it is (4294967296-1)

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

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.

Commented:
Turn on your compiler's warnings all the way up.   At least with Visual Studio it then complains about every single place you are mixing signed and unsigned values.

CERTIFIED EXPERT
Top Expert 2009

Commented:
Is there any chance you can show the code ? Does it still make use if signed values internally somewhere ?

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

Commented:
>>>> but I am trying to figure out what's causing the program to fail with unsigned values.
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.

Commented:
> Is there any chance you can show the code ? Does it still make use if signed values internally somewhere ?

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

CERTIFIED EXPERT
Top Expert 2009

Commented:
I don't see any unsigned ints in that code ... ?

Commented:
> unsigned strt, end,h, l, s, c;

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.
CERTIFIED EXPERT
Most Valuable Expert 2014
Top Expert 2015
Commented:
Unlock this solution and get a sample of our free trial.
(No credit card required)

Commented:
>>>> 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.

Commented:
>>>> used UINT_MAX
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) {

Commented:
ozo,

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

Commented:

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.

Commented:
> since i am actually only storing only primes greater than sqrt(200,000,000) = 1663 primes

typo,

s/greater than/less than/
CERTIFIED EXPERT
Most Valuable Expert 2014
Top Expert 2015

Commented:
> for (end = pgsz; (h -= pgsz) > 0; ) {
This can only stop when h == 0, since unsigned h is never < 0
That can only happen when h is a multiple of pgsz

Commented:
> for (end = pgsz; (h -= pgsz) > 0; ) {
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

CERTIFIED EXPERT
Most Valuable Expert 2014
Top Expert 2015

Commented:
How big is UINT_MAX and LONG_MAX on your implementation?

Commented:
Thanks everyone.

Commented:
Ozo,

If you have read the whole program and have any suggestions to improve it or do it in some other way I would really appreciate it. Thanks a lot.

Commented:
How big is UINT_MAX and LONG_MAX on your implementation?

UINT_MAX = 2^32 - 1
LONG_MAX = 2^31 - 1

Gain unlimited access to on-demand training courses with an Experts Exchange subscription.

Why Experts Exchange?

Experts Exchange always has the answer, or at the least points me in the correct direction! It is like having another employee that is extremely experienced.

Jim Murphy
Programmer at Smart IT Solutions

Deciding to stick with EE.

Mohamed Asif

Being involved with EE helped me to grow personally and professionally.

Carl Webster
CTP, Sr Infrastructure Consultant
Did You Know?

We've partnered with two important charities to provide clean water and computer science education to those who need it most. READ MORE

Connect with Certified Experts to gain insight and support on specific technology challenges including:

• Troubleshooting
• Research
• Professional Opinions
Unlock the solution to this question.