We help IT Professionals succeed at work.

program doesn't work when using unsigned value

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

Kent OlsenData 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
>>>> 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
>>>> the maximum unsigned integer is 2^32-1 == 4294967296.
Of course it is (4294967296-1)

Author

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.

If anybody wants to see the program please ask.

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






Author

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

Author

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)
UNLOCK SOLUTION
>>>> 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.
>>>> 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) {



Author

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.

Author

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.

Author

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

typo,

s/greater than/less than/
ozo
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

Author

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

ozo
CERTIFIED EXPERT
Most Valuable Expert 2014
Top Expert 2015

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

Author

Commented:
Ok, it's fixed, had made a mistake.
Thanks everyone.

Author

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.

Author

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.

Get Access
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

When asked, what has been your best career decision?

Deciding to stick with EE.

Mohamed Asif
Technical Department Head

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

Carl Webster
CTP, Sr Infrastructure Consultant
Empower Your Career
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

Ask ANY Question

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

  • Troubleshooting
  • Research
  • Professional Opinions
Unlock the solution to this question.
Thanks for using Experts Exchange.

Please provide your email to receive a sample view!

*This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.

OR

Please enter a first name

Please enter a last name

8+ characters (letters, numbers, and a symbol)

By clicking, you agree to the Terms of Use and Privacy Policy.