Thread: Just can't find the problem.

  1. #1
    Registered User
    Join Date
    May 2015
    Posts
    65

    Just can't find the problem.

    edit: found the problem.

    Since I had nothing better to do, I thought I'd play around with some prime numbers, but there's a problem...

    It gives me 3, 5, 7 and 11 just fine, then it skips 13 and 17, after which things get really funny. of course there is a mistake somewhere, but I can't find it and would like some help.

    Code:
    #include <stdint.h>
    #include <stdio.h>
    
    // For convinience, the width of the desired type.
    #define WORD_BITS ( 8 * sizeof( uint_fast8_t ) )
    // array size.
    #define ARRAY_SIZE ( 0x10000000 / sizeof( uint_fast8_t ) )
    // number of bits in the bitset.
    #define ARRAY_SIZE_BITS ( 0x80000000 )
    
    // allocate 2^31 bits of memory, to represent all uneven numbers from
    // 0 -> 2^32-1
    static uint_fast8_t b[ ARRAY_SIZE ];
    
    // should be selfexplanatory. Flip bits, and and assign.
    static inline void resetBit( uint_fast32_t idx )
    {
        b[ idx / WORD_BITS ] &= ~(1 << ( idx % WORD_BITS ) );
    }
    
    // This is a bit more complicated, as I don't really need to return 0 or 1,
    // but will be parfectly happy with 0 and non-0. Thus there are two ways:
    // (x>>n)&1 or x & (1 << n) and I would very much like to know which is more
    // efficient.
    static inline uint_fast8_t getBit( uint_fast32_t idx )
    {
        return ( 1 & ( b[ idx / WORD_BITS ] >> ( idx % WORD_BITS ) ) );
    }
    
    // Should initialize it all, but there are issues.
    void initialize()
    {
        // set all bits to 1.
        for( uint_fast32_t n = 0; n < ARRAY_SIZE; n++ )
            b[ n ] = UINT_FAST8_MAX;
    
        uint_fast32_t p;
        // loop through all numbers from 0 -> 2^16.
        for( uint_fast32_t n = 0; n < 0x8000; n++ )
        {
            // If prime...
            if( getBit( n ) )
            {
                // calculate the actual value
                p = 2 * n + 3;
                printf("%d\n", p); //for testing purposes.
                // loop through the bitset and reset required bits.
                // found the flaw: uint_fast32_t i = p -> uint_fast32_t i = p + n
                for( uint_fast32_t i = p + n; i < ARRAY_SIZE_BITS; i += p )
                {
                    resetBit( i );
                }
            }
        }
    }
    Important notes is that I completely disregard even numbers, and strive for the minimum amount of time to initialize b[], not usability.

    other than that, apart from the fact that it does not work, I'm actually quite pleased with my self.

    Any help is most welcome.


    Best regards.

    edit: found the flaw. missed +n at a rather crucial point.
    Last edited by Zacariaz; 06-08-2015 at 09:22 PM. Reason: found the problem on my own.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Array problem. Can you find the problem with this?
    By Aitra in forum C Programming
    Replies: 21
    Last Post: 01-03-2013, 10:33 AM
  2. Can't seem to find the problem, help.
    By JoeyJoe in forum C Programming
    Replies: 8
    Last Post: 03-04-2011, 02:03 PM
  3. help me to find the problem
    By behzad_shabani in forum C Programming
    Replies: 3
    Last Post: 06-12-2008, 01:17 AM
  4. pls help i cant find the problem :(((
    By condorx in forum C Programming
    Replies: 3
    Last Post: 11-07-2002, 09:05 AM
  5. Can't find problem
    By b-ref in forum C Programming
    Replies: 2
    Last Post: 12-06-2001, 05:39 AM