[Okta Webinar] Learn how to a build a cloud-first strategyRegister Now

x
?
Solved

program doesn't work when using unsigned value

Posted on 2007-10-04
22
Medium Priority
?
294 Views
Last Modified: 2010-04-01
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?
0
Comment
Question by:nixfreak
  • 10
  • 5
  • 3
  • +3
22 Comments
 
LVL 46

Expert Comment

by:Kent Olsen
ID: 20014751
Hi nixfreak,

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


Kent
0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
ID: 20014762
>>>> 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
0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
ID: 20014770
>>>> the maximum unsigned integer is 2^32-1 == 4294967296.
Of course it is (4294967296-1)
0
What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

 
LVL 7

Author Comment

by:nixfreak
ID: 20014889
> 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.

If anybody wants to see the program please ask.
0
 
LVL 22

Expert Comment

by:grg99
ID: 20015014
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.

0
 
LVL 53

Expert Comment

by:Infinity08
ID: 20015023
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 ?
0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
ID: 20015080
>>>> 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.

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






0
 
LVL 7

Author Comment

by:nixfreak
ID: 20015218
> 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
     );
}

0
 
LVL 53

Expert Comment

by:Infinity08
ID: 20015305
I don't see any unsigned ints in that code ... ?
0
 
LVL 7

Author Comment

by:nixfreak
ID: 20015686
> 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.
0
 
LVL 85

Accepted Solution

by:
ozo earned 2000 total points
ID: 20015805
(h -= pgsz) > 0;
when h is unsigned, this can only fail when h==0
0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
ID: 20015947
>>>> 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.
0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
ID: 20016319
>>>> 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) {



0
 
LVL 7

Author Comment

by:nixfreak
ID: 20016481
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.

0
 
LVL 7

Author Comment

by:nixfreak
ID: 20016483

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.
0
 
LVL 7

Author Comment

by:nixfreak
ID: 20016494
> since i am actually only storing only primes greater than sqrt(200,000,000) = 1663 primes

typo,

s/greater than/less than/
0
 
LVL 85

Expert Comment

by:ozo
ID: 20016528
> 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
0
 
LVL 7

Author Comment

by:nixfreak
ID: 20016627
> 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

0
 
LVL 85

Expert Comment

by:ozo
ID: 20016781
How big is UINT_MAX and LONG_MAX on your implementation?
0
 
LVL 7

Author Comment

by:nixfreak
ID: 20016811
Ok, it's fixed, had made a mistake.
Thanks everyone.
0
 
LVL 7

Author Comment

by:nixfreak
ID: 20016912
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.
0
 
LVL 7

Author Comment

by:nixfreak
ID: 20016963
How big is UINT_MAX and LONG_MAX on your implementation?

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

Featured Post

What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Have you thought about creating an iPhone application (app), but didn't even know where to get started? Here's how: ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ Important pre-programming comments: I’ve never tri…
Windows programmers of the C/C++ variety, how many of you realise that since Window 9x Microsoft has been lying to you about what constitutes Unicode (http://en.wikipedia.org/wiki/Unicode)? They will have you believe that Unicode requires you to use…
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use while-loops in the C programming language.
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.
Suggested Courses

873 members asked questions and received personalized solutions in the past 7 days.

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

Join & Ask a Question