#Knuth arrows in C++ metaprogramming.
Two implementations of Knuth's arrows using constexpr
and template metaprogramming.
#include <stdint.h>
#include <stdexcept>
constexpr uint64_t pow(uint64_t a, uint64_t n)
{
return
n == 0
? 1
: a * pow(a, n - 1);
}
constexpr uint64_t tower(uint64_t a, uint64_t b)
{
return
b == 0
? throw std::invalid_argument("b == 0")
: b == 1
? a
: pow(a, tower(a, b - 1));
}
constexpr uint64_t arr(uint64_t a, uint64_t b, uint64_t s);
constexpr uint64_t arr2(uint64_t cnt, uint64_t a, uint64_t sp, uint64_t b)
{
return cnt == 0
? arr(a, sp, b)
: arr(a, arr2(cnt - 1, a, sp, b), sp);
}
constexpr uint64_t arr(uint64_t a, uint64_t s, uint64_t b)
{
return s == 1
? pow(a, b)
: s == 2
? tower(a, b)
: arr2(b - 1, a, s - 1, a);
}
constexpr uint64_t arr_impl(bool arr_iter, uint64_t cnt, uint64_t a, uint64_t s, uint64_t b)
{
return arr_iter
? (cnt == 0
? arr_impl(false, 0, a, s, b)
: arr_impl(false, 0, a, arr_impl(true, cnt - 1, a, s, b), s))
: (s == 1
? pow(a, b)
: s == 2
? tower(a, b)
: arr_impl(true, b - 1, a, s - 1, a));
}
constexpr uint64_t arr(uint64_t a, uint64_t s, uint64_t b)
{
return arr_impl(false, 0, a, s, b);
}
uint64_t x = arr(3, 2, 3); // 3 ↑↑ 3 = 7625597484987
uint64_t x = arr(2, 2, 3); // 2 ↑↑ 3 = 16
(Resembles the variant #2 of constexpr Knuth arrows)
#include <stdint.h>
/// Pow
template <uint64_t A, uint64_t N>
struct Pow {
static constexpr uint64_t value = A * Pow<A, N - 1>::value;
};
template <uint64_t A>
struct Pow<A, 0> {
static constexpr uint64_t value = 1;
};
// Tower
template <uint64_t A, uint64_t B>
struct Tower {
static constexpr uint64_t value = Pow<A,
Tower<A, B - 1>::value
>::value;
};
template <uint64_t A>
struct Tower<A, 1> {
static constexpr uint64_t value = A;
};
// ArrImpl
template <bool arr_iter, uint64_t C, uint64_t A, uint64_t S, uint64_t B>
struct ArrImpl {
static constexpr uint64_t value = 1;
};
template <uint64_t C, uint64_t A, uint64_t S, uint64_t B>
struct ArrImpl<true, C, A, S, B> {
static constexpr uint64_t value
= ArrImpl<false, 0, A,
ArrImpl<true, C - 1, A, S, B>::value,
S>::value;
};
template <uint64_t A, uint64_t S, uint64_t B>
struct ArrImpl<true, 0, A, S, B> {
static constexpr uint64_t value
= ArrImpl<false, 0, A, S, B>::value;
};
template <uint64_t C, uint64_t A, uint64_t B>
struct ArrImpl<false, C, A, 1, B> {
static constexpr uint64_t value
= Pow<A, B>::value;
};
template <uint64_t C, uint64_t A, uint64_t B>
struct ArrImpl<false, C, A, 2, B> {
static constexpr uint64_t value
= Tower<A, B>::value;
};
template <uint64_t C, uint64_t S, uint64_t A, uint64_t B>
struct ArrImpl<false, C, A, S, B> {
static constexpr uint64_t value
= ArrImpl<true, B - 1, A, S - 1, A>::value;
};
// Arr
template <uint64_t A, uint64_t S, uint64_t B>
struct Arr {
static constexpr uint64_t value
= ArrImpl<false, 0, A, S, B>::value;
};
auto T1 = Pow<2, 5>::value; // 32
auto T2 = Tower<2, 3>::value; // 16
auto T3 = Arr<3, 2, 3>::value; // 3 ↑↑ 3 = 7625597484987