0

I want to generate a constant array power[501] = {1, p % MODER, p*p % MODER, p*p*p % MODER, ..., p^500 % MODER}, of which p is an constant number.

I know I could generate p^n % MODER by using the following code:

template<int a, int n> struct pow
{
  static const int value = a * pow<a, n-1>::value % MODER;
};
template<int a> struct pow<a, 0>
{
  static const int value = 1;
};

And it does work!

My question is if I could generate the array that I want?

abcdabcd987
  • 2,043
  • 2
  • 23
  • 34

2 Answers2

4

You can use BOOST_PP_ENUM as:

#include <iostream>
#include <boost/preprocessor/repetition/enum.hpp>

#define MODER 10

template<int a, int n> struct pow
{
  static const int value = a * pow<a, n-1>::value % MODER;
};
template<int a> struct pow<a, 0>
{
  static const int value = 1;
};

#define ORDER(count, i, data) pow<data,i>::value

int main() {
  const int p = 3;
  int const a[] = { BOOST_PP_ENUM(10, ORDER, p) };
  std::size_t const n = sizeof(a)/sizeof(int);
  for(std::size_t i = 0 ; i != n ; ++i ) 
    std::cout << a[i] << "\n";
  return 0;
}

Output:

1
3
9
7
1
3
9
7
1
3

See online demo

The line:

int const a[] = { BOOST_PP_ENUM(10, ORDER, p) };

expands to this:

int const a[] = { pow<p,0>::value, pow<p,1>::value, ...., pow<p,9>::value};
Nawaz
  • 353,942
  • 115
  • 666
  • 851
  • Does this deal with integer overflow? int^500 is going to be a problem I'd think... – tmpearce Jul 26 '12 at 08:54
  • @tmpearce: That is a problem anyway irrespective of whether you use `BOOST_PP_ENUM` or not. It is a problem with `BOOST_PP_ENUM` itself. It is problem with the definition of `pow` class template. If you handle that case, implement `pow` in such a way to handle this. Simple! – Nawaz Jul 26 '12 at 08:55
  • Thanks a lot. But whatif i don't have a boost library, just g++? is there no solution? – abcdabcd987 Jul 26 '12 at 08:58
  • @abcdabcd987: then you've to either implement the functionality of `BOOST_PP_ENUM` yourself, or initialize the array at runtime! – Nawaz Jul 26 '12 at 08:59
1

Unless n has an upper bound, I would presume that that is impossible. Check this question out. There are ways to make the preprocessor look like a Turing-complete machine but only if you accept the fact that your code size should increase in the order of n, which is not better than placing a precomputed array by hand.

Important Update: You should see this question too. It seems that not the preprocessor but the template engine is indeed Turing-complete (at least can do recursion). So, now I suspect that the answer is yes.

Community
  • 1
  • 1
Eser Aygün
  • 7,794
  • 1
  • 20
  • 30
  • It is no C++ solution. It is not C solution either. It is only C99 solution. `P99` is available in C99 only. – Nawaz Jul 26 '12 at 09:05