Problem with Sieving program

[aesguitar]

I'm writing an algorithm to perform a custom sieve by marking all values in a boolean array that are divisible by the numbers given as true. Then, it creates and int array equal in length to the number of true values in the boolean array. There is something going wrong and I don't know what it is. It will compile and run once in a while, but it doesn't return correct numbers. When it doesn't run, windows kills it. I'm using code::block as my IDE and MinGW.

int64_t* sieve(int64_t values[], int64_t limit)//creates the method
{
    bool bools [limit+1];//creates the orignal boolean array

    int64_t counter = 0;//creates a true value counter
    for(int64_t i = 0; i < limit+1; i++)//marks all values as false
    {
        bools[i] = false;
    }

    for(int64_t index = 0; index < sizeof values; index++)//this is the sieve
    {
        int64_t val = values[index];//gets an value at index i
        for(int64_t i = val; i < limit+1; i+=val)//loops through, starting at val incrementing by val
        {
           if(bools[i]==false)//if a value at that spot is false, mark it true
           {
               bools[i] = true;
               counter++;//increments the counter because the value is now true
           }
        }
    }

    int64_t vals [counter];//creates an int array of counter length
    int64_t index = 0;//index incrementer
    for(int64_t i = 0; i < limit+1; i++)//loop to set the vals array values
    {
        if(bools[i]==true)//sets the value at index to i if the value in bools is true
        {
            vals[index] = i;
            index++;//increments the indexer
        }
    }
    return vals;//returns the array

}

int main()//main class to test the algo
{
    int64_t siev [] = {3,5};
    int64_t * s;
    s = sieve(siev, 1000);
    int64_t sum = 0;
    for(int64_t i = 0; i < sizeof s; i++)
    {
        sum+=s[i];
        cout << "value = " << s[i];
    }

    cout << endl << endl<< "Sum of values divisible by 3 or 5 less than or equal to 1000:      " << sum;


    return 0;

}

[Smac89]

Line 11

for(int64_t index = 0; index < sizeof values; index++)//this is the sieve

sizeof does not return the size of the array. It returns the sum of the size of the individual values in the array. So if you want to know the size of the array, you do sizeof Array / sizeof *Array

Same for line 44

Also why use int64_t?? int will work perfectly fine for this question. I suspect question one of euler?

Fix those and try it again, might be more bugs.

[aesguitar]

Windows is still killing the program every time or nothing will happen, almost like the program hangs. I ran the debugger, and line 16 is always the culprit. Is there something wrong happening there?

[Smac89]

What is going on at line 40?

[aesguitar]

Line 40 contains the array that the sieve runs off of. In this case, 3 and 5, so every number divisible by 3 and 5 should be marked true. That's the "custom" part of the sieve. I don't think that's the problem, what are your thoughts?

[Smac89]

Are you getting an error that looks something like 'segmentation fault'? If so, then your problem is truly line 16 because since you initialized your array to only contain the values 3 and 5, then at line 16 you accessing part of the array that you have no initialized. So the compiler will ofc complain about this.

A way to fix this will be to initialize everything in your array to 0 before calling the sieving function.

[cire]

Line 3 and line 24 are illegal. Array sizes require a compile-time constant.

On line 34 you are returning a pointer to a local array which ceases existing when the function ends.

On line 40, you create an array with enough room for 2 elements.

On line 42, you feed that array to the sieve function, where it still has only room for 2 elements.

As already mentioned, line 11 is incorrect. values is a pointer, and there is no possible way to determine the number of elements it points to from examining the pointer (via sizeof, for example.)

[aesguitar]

Then how would I do it? I'm coming from Java, where I have a lot of experience, and that's how it's done there, somewhat. How can I get around it then?

[Smac89]

easiest thing really would be to use a void function. Once I get to a computer I will post what I have

E:

#include <iostream>
#define MAX_NUMS 1000

using std::cout;
using std::cin;
using std::endl;

typedef unsigned long ulin;

void Sieve_m(int values[], int M [], ulin S_V, int S_M)//creates the method
{  
  for (int k = 0; k < S_M; ++k)
  {
    for (ulin w = 1; w * M[k] < S_V; ++w)//Might not be the safest method at larger values
      values[w * M[k]] = 1;		  //but works for now
  }  
}

int main()//main class to test the algo
{
  ulin Big =  MAX_NUMS;
  
  int siev [Big];//Set the array to the size needed
  
  for (ulin w = 0; w < Big; w++)
    siev[w] = 0;//Initialise all values to 0
    
  int Mults [] = {3, 5}; //Our multiples
  
  Sieve_m(siev, Mults, Big, (int)(sizeof Mults / sizeof *Mults)); //call the function
  
  int count = 0;
  
  for (ulin r = 0; r < Big; r++)
    if (siev[r])
      count += r;
    
  cout << count << endl;  
  
  return 0;
  
}

[cire]

Then how would I do it? I'm coming from Java, where I have a lot of experience, and that's how it's done there, somewhat. How can I get around it then?

Assuming you're talking about the declaration of dynamically sized arrays and returning them from functions, ideally you would use a std::vector.

#include <iostream>
#include <iomanip>
#include <vector>
#include <cstdint>

typedef std::uint64_t num_type ; 

std::vector<num_type> generatePrimes(num_type upTo)
{
    std::vector<bool> isPrime(upTo, true) ;  // the sieve.
    std::vector<num_type> primes ;

    num_type num = 2 ;
    while ( num < upTo )
    {
        primes.push_back(num) ;

        for ( num_type n = num+num; n < upTo; n += num )
            isPrime[n] = false ;

        while ( ++num < upTo && !isPrime[num] )
            ;
    }

    return primes ;
}

void print( const std::vector<num_type>& v )
{
    for ( unsigned i=0; i!=v.size(); ++i )
    {
        std::cout << std::setw(7) << v[i] ;
        if ( (i+1) % 8 == 0 )
            std::cout << '\n' ;
    }
}

int main()
{
    std::vector<num_type> primes = generatePrimes(1000) ;
    print(primes) ;
}

[aesguitar]

Oh. So do vectors in c++ work more like the arrays in Java?

[Smac89]

There is an array class in c++ that can do the same thing.