Nim Product
(game/nim_product.hpp)

• View this file on GitHub
• Last update: 2026-08-24 02:00:33+09:00
• Include: #include "game/nim_product.hpp"

Overview

Arithmetic on 64-bit nimbers. Nim addition is bitwise xor; nim_product implements Conway’s recursively defined nim multiplication. Together these operations form the finite field with 2^64 elements.

The implementation recursively views a nimber as a quadratic extension and uses a 256-by-256 byte lookup table at the leaves. This avoids a large per-query table while keeping the fixed 64-bit multiplication fast enough for batched queries.

Functions

All functions are in namespace m1une::game and use uint64_t.

Function signature	Description	Complexity
uint64_t nim_product(uint64_t x, uint64_t y)	Returns x nim-multiplied by y.	O(1) time and O(1) extra space per call
uint64_t nim_power(uint64_t base, uint64_t exponent)	Returns the nim-product power of base. The zeroth power is one.	O(log exponent) nim products
uint64_t nim_inverse(uint64_t value)	Returns the nonzero value’s multiplicative inverse.	O(64) nim products
uint64_t nim_quotient(uint64_t numerator, uint64_t denominator)	Returns the nim-field quotient.	O(64) nim products

The first operation that uses this header initializes a 64 KiB lookup table. nim_inverse asserts that value != 0, and nim_quotient asserts that the denominator is nonzero.

Example

#include "game/nim_product.hpp"
#include <cstdint>
#include <iostream>

int main() {
    uint64_t product = m1une::game::nim_product(4, 4);
    std::cout << product << '\n';  // 6

    uint64_t inverse = m1une::game::nim_inverse(7);
    std::cout << m1une::game::nim_product(7, inverse) << '\n';  // 1
}

Required by

• Game Library (game/all.hpp)

Verified with

• verify/game/game_algorithms.test.cpp
• verify/game/nim_product.test.cpp

Code

#ifndef M1UNE_GAME_NIM_PRODUCT_HPP
#define M1UNE_GAME_NIM_PRODUCT_HPP 1

#include <array>
#include <cassert>
#include <cstdint>
#include <limits>

namespace m1une {
namespace game {
namespace internal {

inline uint64_t nim_product_small(uint64_t x, uint64_t y) {
    if (x < 2 || y < 2) return x * y;

    int shift = 1;
    const uint64_t largest = x | y;
    while ((uint64_t(1) << (shift * 2)) <= largest) shift *= 2;
    const uint64_t mask = (uint64_t(1) << shift) - 1;
    const uint64_t x_high = x >> shift;
    const uint64_t x_low = x & mask;
    const uint64_t y_high = y >> shift;
    const uint64_t y_low = y & mask;

    const uint64_t high_product = nim_product_small(x_high, y_high);
    const uint64_t low_product = nim_product_small(x_low, y_low);
    const uint64_t mixed_product =
        nim_product_small(x_high ^ x_low, y_high ^ y_low);
    return ((mixed_product ^ low_product) << shift) ^ low_product
           ^ nim_product_small(high_product, uint64_t(1) << (shift - 1));
}

inline const std::array<uint8_t, 1 << 16>& nim_product_8_table() {
    static const auto table = [] {
        std::array<uint8_t, 1 << 16> result{};
        for (int x = 0; x < 256; ++x) {
            for (int y = 0; y < 256; ++y) {
                result[(x << 8) | y] = uint8_t(nim_product_small(x, y));
            }
        }
        return result;
    }();
    return table;
}

inline uint64_t nim_product_8(uint64_t x, uint64_t y) {
    return nim_product_8_table()[(x << 8) | y];
}

template <int Bits>
inline uint64_t nim_product_fixed(uint64_t x, uint64_t y) {
    if constexpr (Bits == 8) {
        return nim_product_8(x, y);
    } else {
        constexpr int shift = Bits / 2;
        constexpr uint64_t mask = (uint64_t(1) << shift) - 1;
        const uint64_t x_high = x >> shift;
        const uint64_t x_low = x & mask;
        const uint64_t y_high = y >> shift;
        const uint64_t y_low = y & mask;

        const uint64_t high_product =
            nim_product_fixed<shift>(x_high, y_high);
        const uint64_t low_product = nim_product_fixed<shift>(x_low, y_low);
        const uint64_t mixed_product = nim_product_fixed<shift>(
            x_high ^ x_low,
            y_high ^ y_low
        );
        return ((mixed_product ^ low_product) << shift) ^ low_product
               ^ nim_product_fixed<shift>(
                   high_product,
                   uint64_t(1) << (shift - 1)
               );
    }
}

}  // namespace internal

inline uint64_t nim_product(uint64_t x, uint64_t y) {
    return internal::nim_product_fixed<64>(x, y);
}

inline uint64_t nim_power(uint64_t base, uint64_t exponent) {
    uint64_t result = 1;
    while (exponent != 0) {
        if (exponent & 1) result = nim_product(result, base);
        base = nim_product(base, base);
        exponent >>= 1;
    }
    return result;
}

inline uint64_t nim_inverse(uint64_t value) {
    assert(value != 0);
    return nim_power(value, std::numeric_limits<uint64_t>::max() - 1);
}

inline uint64_t nim_quotient(uint64_t numerator, uint64_t denominator) {
    assert(denominator != 0);
    return nim_product(numerator, nim_inverse(denominator));
}

}  // namespace game
}  // namespace m1une

#endif  // M1UNE_GAME_NIM_PRODUCT_HPP

#line 1 "game/nim_product.hpp"



#include <array>
#include <cassert>
#include <cstdint>
#include <limits>

namespace m1une {
namespace game {
namespace internal {

inline uint64_t nim_product_small(uint64_t x, uint64_t y) {
    if (x < 2 || y < 2) return x * y;

    int shift = 1;
    const uint64_t largest = x | y;
    while ((uint64_t(1) << (shift * 2)) <= largest) shift *= 2;
    const uint64_t mask = (uint64_t(1) << shift) - 1;
    const uint64_t x_high = x >> shift;
    const uint64_t x_low = x & mask;
    const uint64_t y_high = y >> shift;
    const uint64_t y_low = y & mask;

    const uint64_t high_product = nim_product_small(x_high, y_high);
    const uint64_t low_product = nim_product_small(x_low, y_low);
    const uint64_t mixed_product =
        nim_product_small(x_high ^ x_low, y_high ^ y_low);
    return ((mixed_product ^ low_product) << shift) ^ low_product
           ^ nim_product_small(high_product, uint64_t(1) << (shift - 1));
}

inline const std::array<uint8_t, 1 << 16>& nim_product_8_table() {
    static const auto table = [] {
        std::array<uint8_t, 1 << 16> result{};
        for (int x = 0; x < 256; ++x) {
            for (int y = 0; y < 256; ++y) {
                result[(x << 8) | y] = uint8_t(nim_product_small(x, y));
            }
        }
        return result;
    }();
    return table;
}

inline uint64_t nim_product_8(uint64_t x, uint64_t y) {
    return nim_product_8_table()[(x << 8) | y];
}

template <int Bits>
inline uint64_t nim_product_fixed(uint64_t x, uint64_t y) {
    if constexpr (Bits == 8) {
        return nim_product_8(x, y);
    } else {
        constexpr int shift = Bits / 2;
        constexpr uint64_t mask = (uint64_t(1) << shift) - 1;
        const uint64_t x_high = x >> shift;
        const uint64_t x_low = x & mask;
        const uint64_t y_high = y >> shift;
        const uint64_t y_low = y & mask;

        const uint64_t high_product =
            nim_product_fixed<shift>(x_high, y_high);
        const uint64_t low_product = nim_product_fixed<shift>(x_low, y_low);
        const uint64_t mixed_product = nim_product_fixed<shift>(
            x_high ^ x_low,
            y_high ^ y_low
        );
        return ((mixed_product ^ low_product) << shift) ^ low_product
               ^ nim_product_fixed<shift>(
                   high_product,
                   uint64_t(1) << (shift - 1)
               );
    }
}

}  // namespace internal

inline uint64_t nim_product(uint64_t x, uint64_t y) {
    return internal::nim_product_fixed<64>(x, y);
}

inline uint64_t nim_power(uint64_t base, uint64_t exponent) {
    uint64_t result = 1;
    while (exponent != 0) {
        if (exponent & 1) result = nim_product(result, base);
        base = nim_product(base, base);
        exponent >>= 1;
    }
    return result;
}

inline uint64_t nim_inverse(uint64_t value) {
    assert(value != 0);
    return nim_power(value, std::numeric_limits<uint64_t>::max() - 1);
}

inline uint64_t nim_quotient(uint64_t numerator, uint64_t denominator) {
    assert(denominator != 0);
    return nim_product(numerator, nim_inverse(denominator));
}

}  // namespace game
}  // namespace m1une

Back to top page