время компиляции шаблонных расчетов C ++ для unsigned long long?на двоих?

Question

Я использую Power для вычисления мощностей во время компиляции, чтобы вычислить n ** p.Он использует целые.Я хочу вычислить что-то большее, чем int, хорошо?Это вписывается в u64 (unsigned long long).Могут ли шаблоны C ++ выполнять вычисления во время компиляции на u64?Enums не может этого сделать.На двоих?Возможно?

Я бы очень хотел, чтобы тип был аргументом шаблона.Является ли это возможным ?Мой компилятор не c ++ 0x.

Спасибо, Андрей

template<int N, int P> struct Power {
   enum { val = N * Power<N, P-1>::val };
};

template<int N> struct Power<N, 0> {
   enum { val = 1 };
};

int result = Power<2, 5>; // 2**5 == 32

Answer 1

Да, вы можете выполнять вычисления во время компиляции для любого примитивного целочисленного типа.Однако вы не можете выполнять вычисления для значений с плавающей запятой, поскольку шаблоны не могут быть параметризованы по этим значениям.В будущем стандарте C ++ 0x будут введены специальные классы для рациональной арифметики во время компиляции, поэтому вы можете использовать ее, если хотите.

Answer 2

Вы можете использовать математику с множественной точностью для вычисления больших чисел (в моем примере ниже я использую 96-битные вычисления с 3 параметрами шаблона, вы можете использовать любое постоянное число). Вам нужно иметь более одного целого числа в качестве параметра шаблона.

При выполнении умножения во время компиляции вам, вероятно, следует умножить 32-разрядные числа, имеющие 64-разрядные результаты; результат должен быть разбит на 2 параметра шаблона.

Проверка переполнения, вероятно, возможна, но может быть сложной.

const uint64_t W = 1000000000; // word size: 2^32 is best; any smaller number is OK
// I use a power of 10 as word size for ease of printing (see main() below)

// The following class performs multiplication of (n0 + W*n1 + W*W*n2) by (base)
template <unsigned n0, unsigned n1, unsigned n2, uint64_t base, unsigned p> class power_temp
{
    typedef power_temp<
        n0 * base % W,
        n1 * base % W + n0 * base / W,
        n2 * base % W + n1 * base / W,
        base, p - 1> mult_type;
public:
    static const unsigned x0 = mult_type::x0;
    static const unsigned x1 = mult_type::x1;
    static const unsigned x2 = mult_type::x2;
};

// The following partial specialization is used to end recursion
template <unsigned n0, unsigned n1, unsigned n2, uint64_t base>
class power_temp<n0, n1, n2, base, 0>
{
public:
    static const unsigned x0 = n0;
    static const unsigned x1 = n1;
    static const unsigned x2 = n2;
};

// The following class calculates a power, using compile-time calculations
template <unsigned base, unsigned p> struct power
{
    static const unsigned x0 = power_temp<1, 0, 0, base, p>::x0;
    static const unsigned x1 = power_temp<1, 0, 0, base, p>::x1;
    static const unsigned x2 = power_temp<1, 0, 0, base, p>::x2;
};

int main()
{
    typedef power<123456789, 3> my1;
    printf("%09d%09d%09d\n", my1::x2, my1::x1, my1::x0);

    typedef power<5, 33> my2;
    printf("%09d%09d%09d\n", my2::x2, my2::x1, my2::x0);
}

Answer 3

Чтобы расширить реализацию sbi, вот тот, который возводит возведение в квадрат (что требует меньшего количества экземпляров шаблона для больших мощностей).

Обратите внимание, что если вы действительно хотите рассчитать степени 2, вы 'Намного лучше просто сдвинуть влево (т.е. 2**x == 1 << x), а не делать все эти шаблоны.

#include <iostream>

template <unsigned long long N, unsigned int P, int Odd = (P&1)> struct Power;

template <unsigned long long N, unsigned int P>
struct Power<N,P,0> { // even (square N and halve the power)
    static const unsigned long long val = Power<N*N,(P/2)>::val;
};

template <unsigned long long N, unsigned int P>
struct Power<N,P,1> { // odd (multiply by N and decrement the power)
    static const unsigned long long val = N * Power<N,(P-1)>::val;
};

template <unsigned long long N>
struct Power<N,0,0> { // zero (x**0 is 1 for all x != 0)
    static const unsigned long long val = 1;
};

int main() {
    std::cout << "2**0 = " << Power<2,0>::val << "\n";
    std::cout << "2**1 = " << Power<2,1>::val << "\n";
    std::cout << "2**2 = " << Power<2,2>::val << "\n";
    std::cout << "2**3 = " << Power<2,3>::val << "\n";
    std::cout << "2**4 = " << Power<2,4>::val << "\n";
    std::cout << "2**5 = " << Power<2,5>::val << "\n";
    std::cout << "2**6 = " << Power<2,6>::val << "\n";
    std::cout << "2**7 = " << Power<2,7>::val << "\n";
    std::cout << "2**8 = " << Power<2,8>::val << "\n";
    std::cout << "2**9 = " << Power<2,9>::val << "\n";
    std::cout << "2**10 = " << Power<2,10>::val << "\n";
    std::cout << "2**11 = " << Power<2,11>::val << "\n";
    std::cout << "2**12 = " << Power<2,12>::val << "\n";
    std::cout << "2**30 = " << Power<2,30>::val << "\n";
    std::cout << "2**40 = " << Power<2,40>::val << "\n";
    std::cout << "2**50 = " << Power<2,50>::val << "\n";
    std::cout << "2**60 = " << Power<2,60>::val << "\n";
    return 0;
}

Отказ от ответственности: я не утверждаю, что этот код обязательно будет компилироваться быстрее из-за уменьшенияколичество экземпляров шаблона (хотя это может быть).Я действительно только написал это как игрушечную демонстрацию.Я оставляю читателю в качестве упражнения написать версию, не уязвимую для того, чтобы кто-то явно передавал значение для параметра Odd при использовании Power<>.

Answer 4

template<int N, unsigned int P> struct Power {
   static const unsigned long long val = N * Power<N, P-1>::val;
};

template<int N> struct Power<N, 0> {
   static const unsigned long long val = 1;
}

Обратите внимание, что я сделал P unsigned int, потому что ваш шаблон потерпит неудачу при отрицательных значениях.