C++ metaprogramming Knuth's arrows

This article presents two C++ implementations of Knuth's up-arrow notation for representing extremely large numbers through repeated exponentiation. The first implementation uses `constexpr` functions with recursion, while the second uses template metaprogramming with specialized structs, both capable of computing values like 3↑↑3 (which equals 7,625,597,484,987).

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