#constexpr sieve

21 messages · Page 1 of 1 (latest)

sleek hemlock
# 
template <size_t N> struct sieve {
  vector<vector<int>> divs;
  sieve() {
    divs.resize(N + 1);
    for (int i = 1; i <= N; i++) {
      for (int j = i; j <= N; j += i)
        divs[j].emplace_back(i);
    }
  }
  vector<int>& operator[](int i) {
    return divs[i];
  }
};

is there any ways to make this sieve a constexpr-able type ?
because of vector resize thing it doesnt work that way , is there any alternative ways to store divisors and get it get calculated during compile time ?

plush topazBOT
#

When your question is answered use !solved to mark the question as resolved.

Remember to ask specific questions, provide necessary details, and reduce your question to its simplest form. For tips on how to ask a good question use !howto ask.

verbal sequoia
#

Since the size is known at compile time you could be using an std::array instead

#

It's not just resize that fucks up the constexrp-ability of this class, it's the vector itself

#

In general, dynamic allocation can occur in a constant expression if the memory is freed as part of evaluating the constant expression

#

Unless your sieve struct is used as an anonymous object that get instantiated, used, and then destructed all in one expression, there's not much you can do with it (in constexpr terms)

#

But regardless this is a good place to be using std::array

night iron
#

Yes, there's no need for vector here since N can be used as array size

verbal sequoia
#

Note: you'll be using quite a lot more memory you actually need, wasting some memory on the inner arrays but that's a trade off you need to accept if you really want this to be constexpr all the way

#

Also indexing the inner arrays becomes less trivial but... you can still hide that complexity behind consteval functions that take in the indices you would like to be using

tulip shard
#

There is no way to generate a sieve algorithm eith this way and make this a constexpr

night iron
#

you can, since each inner array is at most N in size

#

then store the length of each in another array

#

you could also use a flattened array, the size of which can be computed at compile time

#

then funny index tricks to access them and return a view

sleek hemlock
night iron
#

you can calculate the total size needed like so:

template<std::size_t N>
consteval std::size_t total_size()
{
    std::size_t count = 0;
    for (std::size_t i = 1; i <= N; i++)
    {
        count += (N - i) / i + 1;
    }
    return count;
}
#

for count += (N - i) / i + 1 you could also just have a second for loop like your code has, if it's more readable

#

then you should be able to calculate a formula to convert divs[i][j] to divs[???] but i'm too lazy currently

slim delta
#

i * arr[i].size() + j?

night iron
#

the original code has divs[j].emplace_back(i) instead of the other way around so it's not that simple