Thread: Why am I not getting the correct primes?

  1. #1
    Registered User
    Join Date
    Aug 2013
    Posts
    8

    Why am I not getting the correct primes?

    Hi. I'm a beginner in C and system programming. I need to use multiple process and POSIX shared memory to find all primes between 0 and 100. My code compiles, but the result is not correct, it shows all the multiples of 3 as primes.

    My instructor also mentioned that the multi-process portion will fork() the appropriate number of child processes. The parent process will create a POSIX shared memory object to which the sub-processes will attach. I am confused about the things he said about parent process.

    Can someone take a look at my code and let me know why I'm not getting the right primes? Your help is greatly appreciated.

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <sys/time.h>
    #include <sys/types.h>
    #include <sys/mman.h>
    #include <sys/stat.h>
    #include <getopt.h>
    #include <ctype.h>
    #include <stdint.h>
    #include <unistd.h>
    #include <math.h>
    #include <fcntl.h>
    #include <signal.h>
    #include <errno.h>
     
    #define BITS_PER_WORD 8
    #define WORD_OFFSET(b) ((b) / BITS_PER_WORD)
    #define BIT_OFFSET(b) ((b) % BITS_PER_WORD)
    #define SHM_NAME "/cc_prm"
     
     
    //function to set all non-primes to 0
    void set_notPrime(unsigned int n);
    void set_bitmap();
    void seed_primes();
    int check_Prime(unsigned int n);
    unsigned long next_seed(unsigned long cur_seed);
    void count_primes();
    void prime_process();
    void *mount_shmem(char *path, int object_size);
    void sieve(unsigned long i);
    void nevermore();
     
    //global variables 
    unsigned long m = 100;                  //maximum number
    int c = 5;                            //number of processes
    char *prime_nums = NULL;
    pid_t *process_array;
    int tot_p_num = 0;                    //total number of primes found
     
    int main (int argc, char *argv[])
    {
    //print n and c
        printf("m=%ld, c=%d\n", m, c);
       
       
        struct sigaction action;
       
        sigemptyset(&action.sa_mask);
        //action.sa_handler = nevermore();
        action.sa_flags = 0;
       
       
        sigaction(SIGQUIT, &action, NULL);
        sigaction(SIGINT, &action, NULL);
        sigaction(SIGHUP, &action, NULL);
       
       
        unsigned long primes_size = m / BITS_PER_WORD + 1;
       
        void *addr = mount_shmem(SHM_NAME, primes_size);
        printf("Memory is mounted\n");
       
        prime_nums = (unsigned char *) addr;
           
        set_bitmap();
        printf("Bitmap is set\n");
       
        seed_primes();
        printf("Primes are seeded\n");
       
        prime_process();
        printf("children have lived and died\n");
       
        count_primes();
       
        shm_unlink(SHM_NAME);
       
        int pid = 0;
        while((pid=wait(NULL))!= -1)
        {
           continue;
        }
       
        if(errno!=ECHILD)
        {
           perror("couldn't kill child processes\n");
        }
       
        free(process_array);
        printf("everything has been freed\n");
       
       
        return 0;
    }
     
     
    void set_bitmap()
    {
        prime_nums[0] = 0x00;
        unsigned long i;
        for (i = 1; i < (m/BITS_PER_WORD); i++)
        {
            prime_nums[i] = 0x01;
        }
    }
     
     
    void seed_primes()
    {
        unsigned long i;
        unsigned long j=3;
        unsigned long sqrt_n = sqrt(sqrt(m));
        while (j <= sqrt_n + 1)
        {
            for (i = j; i*j <= sqrt(m)+1; i++)
            {
                set_notPrime;
            }
           
            j++;
            while(!check_Prime(j))
            {
                j++;
            }
        }    
    }
     
    void set_notPrime(unsigned int n)
    {
        prime_nums[WORD_OFFSET(n)] |= (1 << BIT_OFFSET(n));
    }
     
     
    int check_Prime(unsigned int n)
    {
        char bit = prime_nums[WORD_OFFSET(n)] & (1 << BIT_OFFSET(n));
        return bit == 0;
    }
     
     
    void prime_process()
    {
        int i;
       
        for (i = 0; i < c; i++)
        {
           process_array = malloc(sizeof(pid_t) * c);
           pid_t pid;
           switch (pid = fork())
            {
                case -1:
                    perror("Forking Error");
                    exit(EXIT_FAILURE);
                    break;
                //This is the child
                case 0:         
                    sieve(i);
                    exit(EXIT_SUCCESS);
                    break;
                //This is the parent
                default:
                    process_array[i] = pid;
                    break;
           }
        }
    }
     
     
    void *mount_shmem(char *path, int object_size)
    {
        int shmem_fd;
        void *addr;
       
        //create and resize the file
        shmem_fd = shm_open(path, O_CREAT | O_RDWR, S_IRUSR | S_IWUSR);
       
        if (shmem_fd == -1)
        {
           perror("Can't open shared memory");
           exit(EXIT_FAILURE);
        }
       
        //resize the file
        if (ftruncate(shmem_fd, object_size) == -1)
        {
           perror("Can't resize shared memory");
           exit(EXIT_FAILURE);
        }
       
        /* map the shared memory object */
        addr = mmap(NULL, object_size, PROT_READ | PROT_WRITE, MAP_SHARED,
             shmem_fd, 0);
       
        if (addr == MAP_FAILED)
        {
           perror("Failure mapping shared memory");
           exit(EXIT_FAILURE);
        }
       
        return addr;
    }
     
     
    unsigned long next_seed(unsigned long cur_seed)
    {
        unsigned long i;
        for (i = cur_seed + 1; i <= sqrt(m); i++)
           if (check_Prime(i) == 1)
               return i;
        return 0;
    }
     
    void sieve(unsigned long i)
    {
        unsigned long min = i * (m / c) + 1;
       
        unsigned long max =(i == c - 1) ? m : min + (m / c) - 1;
        unsigned long j;
        unsigned long k;
        j = 1;
        while ((j = next_seed(j)) != 0)
        {
           for (k = (min / j < 3) ? 3 : (min / j);(j * k) <= max;k++)
            {
               set_notPrime(j * k);
           }
        }
    }
     
     
    void count_primes()
    {
        unsigned long i;
     
        if(m >= 2)
        {
            printf("2\t");
            tot_p_num++;        //2 is prime, add 1 to tot_p_num
        }
       
        for(i=3;i<=m; i = i+2)
        {
           if(check_Prime(i))
            {
                printf("%lu\t",i);
               tot_p_num++;
               
                if (tot_p_num % 8 == 0)
                    printf("\n");
           }
        }
        printf("\nThere are %d primes between 0 and %lu\n", tot_p_num, m);        
    }
     
     
    void nevermore()
    {
        ;
    }

  2. #2
    Registered User
    Join Date
    May 2009
    Posts
    3,957
    What do you think this line does?
    Why is it NOT giving you a compiler warning or error?

    Edit: line 118

    Code:
    set_notPrime;
    Tim S.
    Last edited by stahta01; 08-20-2013 at 11:44 AM.
    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.." Bill Bryson

  3. #3
    Registered User
    Join Date
    Aug 2013
    Posts
    8
    Thank you for catching that. I used "gcc -std=c99 file.c -o file" to compile on Mac and Linux, I did not get any error or warnings. I removed that already. But I'm still not getting the correct primes.

  4. #4
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,907
    With GCC, you should be adding the -Wall (all warnings) flag to your compile command. Once I figured out I needed to #define _XOPEN_SOURCE 500, here's what I get:
    Code:
    $ make prime
    gcc -Wall -ggdb3 -std=c99 -o prime prime.c -lm -lpthread -lrt
    prime.c: In function ‘main’:
    prime.c:65:14: warning: pointer targets in assignment differ in signedness [-Wpointer-sign]
    prime.c:81:3: warning: implicit declaration of function ‘wait’ [-Wimplicit-function-declaration]
    prime.c: In function ‘seed_primes’:
    prime.c:119:7: warning: statement with no effect [-Wunused-value]
    Line 65: Whether char is signed or unsigned is implementation/system dependent. Either change the declaration of prime_nums on line 38 or the cast on line 65, to match.
    Line 81: You need to #include <sys/wait.h> to use the wait() function. Also, declare pid to be the correct type: pid_t.
    Line 119: Already mentioned by Tim. Perhaps you meant to make that a function call?

    More detail would help. Post the output you get and tell us what's wrong with it, as well as posting the output you expect to get. Do you get the same wrong output every time? Does your program crash randomly? etc, etc. The more you can tell us about the problem, the easier it will be for us to help you find and fix it.

  5. #5
    Registered User
    Join Date
    Aug 2013
    Posts
    8
    Thank you so much for the tip. I used your suggestions and fixed the warnings/error, but I'm still not getting the correct primes. Please see below:

    Here is what I did and what the output looks like:

    gcc -Wall -ggdb3 -std=c99 -o prime prime.c -lm -lpthread

    Output:
    my_laptop:$ ./prime
    m=100, c=5
    Memory is mounted
    Bitmap is set
    Primes are seeded
    children have lived and died
    2 5 7 9 11 13 17 19
    23 29 31 33 37 39 41 43
    47 51 53 57 59 61 63 65
    67 69 71 73 75 77 79 81
    83 85 87 89 91 93 95 97
    99
    There are 41 primes between 0 and 100
    everything has been freed



    I believe the correct output is

    2 3 5 7 11 13 17 19
    23 29 31 37 41 43 47 53
    59 61 67 71 73 79 83 89


    There are 24 primes between 0 and 100.

  6. #6
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    38,416
    Explain what you think this is doing...
    Code:
    void set_bitmap()
    {
        prime_nums[0] = 0x00;
        unsigned long i;
        for (i = 1; i < (m/BITS_PER_WORD); i++)
        {
            prime_nums[i] = 0x01;
        }
    }
    If a set bit indicates a prime number, then this is broken.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  7. #7
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    It would probably have been beneficial if you had spent more time on the logic of identifying primes than on signal handling, process management, and setting up shared memory.

    The main problem I see on a VERY quick look (you have too much code that is irrelevant to your problem, so I haven't looked deeply) is in the starting conditions established by the set_bitmap() function. It doesn't help that seed_primes() unconditionally registers 3 to be non prime.
    Right 98% of the time, and don't care about the other 3%.

    If I seem grumpy or unhelpful in reply to you, or tell you you need to demonstrate more effort before you can expect help, it is likely you deserve it. Suck it up, Buttercup, and read this, this, and this before posting again.

  8. #8
    Registered User
    Join Date
    Aug 2013
    Posts
    8
    Do you mind to give me more hints on how to fix this? I commented out "set_bitmap()" in my main function, but the result is still not correct.

    I run it 2 times and got different results.
    1.
    m=100, c=5
    Memory is mounted
    Bitmap is set
    Primes are seeded
    children have lived and died
    2 5 7 9 11 13 17 19
    23 29 31 33 37 39 41 43
    45 47 49 51 53 55 57 59
    61 63 65 67 69 71 73 75
    77 79 81 83 85 87 89 91
    93 95 97 99
    There are 44 primes between 0 and 100
    everything has been freed

    2.
    m=100, c=5
    Memory is mounted
    children have lived and died
    2 3 5 7 11 13 17 19
    23 29 31 37 41 43 47 53
    59 61 63 65 67 69 71 73
    75 77 79 81 83 85 87 89
    91 93 95 97 99
    There are 37 primes between 0 and 100

  9. #9
    Registered User
    Join Date
    Aug 2013
    Posts
    8
    My program finally works. Here is what I did in the main function - 1) I commented out "set_bitmap()" and "seed_primes()" and 2) I moved "
    count_primes()" to be after
    printf("everything has been freed\n"). I got 25 primes between 1 and 100.



  10. #10
    Registered User
    Join Date
    Aug 2013
    Posts
    8
    I also figured that I fixed set_bitmap() and I did not have to comment them out to make my program works.

  11. #11
    11DE784A SirPrattlepod's Avatar
    Join Date
    Aug 2013
    Posts
    485
    Which sieve is this?

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. primes program need some help
    By Mshock in forum C Programming
    Replies: 2
    Last Post: 04-17-2006, 07:21 PM
  2. Factors and Primes
    By -JM in forum C++ Programming
    Replies: 18
    Last Post: 07-21-2005, 12:48 AM
  3. Help Me - whats the correct way to priint primes
    By superfly in forum C++ Programming
    Replies: 9
    Last Post: 10-28-2002, 09:01 PM
  4. primes
    By godfather in forum C++ Programming
    Replies: 3
    Last Post: 05-08-2002, 01:44 PM
  5. Primes.c help
    By Meronka in forum C Programming
    Replies: 7
    Last Post: 11-17-2001, 06:36 PM

Tags for this Thread