1

I'm trying to learn to implement template in C++. When I am changing my NTT (Number theoretic transform) code into one that uses template, which looks like this:

template <long long mod> struct NTT{
    int x = 0;
    NTT(){
        long long p = mod-1;
        while(!(p % 2)){
            p >>= 1;
            ++x;
        }       
    }   
    const static long long root_pw = 1 << x;
//(there is a function after this that also needs to read the value 'root_pw')
};

signed main()
{
    NTT<998244353> ntt1;
    vector<long long> a(ntt1::root_pw,0);
}

It tells me to make x static.

When I do that, it tells me to make x const, which beats the reason for x being there in the first place.

I use (GNU C++11) and my complier (Dev-C++ 5.11) set to configure (TDM-GCC 4.9.2 64-bit Release), if it helps.

I really want to make this work, but I don't know how.

This is probably stupidly easy, but just what I'm I missing?

Thank you in advance.

Michael Ta
  • 13
  • 2
  • 2
    You cannot use non-static data member to initialize static data member. Static data members are initialized long before any object (and therefore non-static members) is created. – Yksisarvinen Jan 30 '20 at 22:31
  • 1
    In C++14, constexpr function is mostly easy to write as really similar to regular function. In c++11, it is more tricky because of more restriction... – Jarod42 Jan 30 '20 at 22:32
  • Note that GCC is on version 9 and version 10 [can't be far off](https://gcc.gnu.org/develop.html#timeline). If you are permitted, strongly consider upgrading from 4.9.2. – user4581301 Jan 30 '20 at 22:36

1 Answers1

3

You can replace the C++14 function

template <long long mod>
constexpr int f()
{
    int x = 0;
    long long p = mod-1;
    while(!(p % 2)){
        p >>= 1;
        ++x;
    }       
    return x;
}

by the C++11 version:

template <long long p>
constexpr int f2()
{
    return p % 2 ? 0 : 1 + f2<p / 2>();
}

template <long long mod>
constexpr int f()
{
    return f2<mod - 1>();
}

And so

template <long long mod>
struct NTT{
    constexpr static const long long root_pw = 1LL << f<mod>();

};

Demo

Jarod42
  • 203,559
  • 14
  • 181
  • 302
  • Thank you so much!!! However, after I do so, it says "ntt1 is not a class, namespace, or enumeration" when I wrote: NTT<998244353> ntt1; vector a (ntt1::root_pw, 0); Could you help me with this part? – Michael Ta Feb 03 '20 at 00:58
  • It should be `ntt1.root_pw` (which is an not usual way to call static method (though an instance)) or `using ntt1 = NTT<998244353>;` (so `ntt1` is an alis type instead of an instance class). – Jarod42 Feb 03 '20 at 08:50