internal/barret_reduction.cpp

• View this file on GitHub
• Last update: 2022-01-28 13:07:07+09:00

Depends on

• utility/int_alias.cpp

Required by

• algorithm/convolution_arbitrary_mod.cpp
• algorithm/convolution_int.cpp
• algorithm/convolution_mod.cpp
• internal/modulo_transform.cpp
• math/dynamic_modint.cpp
• math/mod_pow.cpp
• math/primitive_root.cpp

Verified with

• test/convolution_arbitrary_mod.test.cpp
• test/convolution_mod.test.cpp

Code

#pragma once
#include "../utility/int_alias.cpp"

namespace proconlib {

class BarretReduction {
    u32 mod;
    u64 near_inv;

  public:
    explicit constexpr BarretReduction(const u32 mod) noexcept : mod(mod), near_inv((u64)(-1) / mod + 1) {}
    constexpr u32 product(const u32 a, const u32 b) const noexcept {
        const u64 z = (u64)a * b;
        const u64 x = ((u128)z * near_inv) >> 64;
        const u32 v = z - x * mod;
        return v < mod ? v : v + mod;
    }
    constexpr u32 get_mod() const noexcept { return mod; }
};

}  // namespace proconlib

#line 2 "utility/int_alias.cpp"
#include <cstdint>

using i32 = std::int32_t;
using u32 = std::uint32_t;
using i64 = std::int64_t;
using u64 = std::uint64_t;
using i128 = __int128_t;
using u128 = __uint128_t;
#line 3 "internal/barret_reduction.cpp"

namespace proconlib {

class BarretReduction {
    u32 mod;
    u64 near_inv;

  public:
    explicit constexpr BarretReduction(const u32 mod) noexcept : mod(mod), near_inv((u64)(-1) / mod + 1) {}
    constexpr u32 product(const u32 a, const u32 b) const noexcept {
        const u64 z = (u64)a * b;
        const u64 x = ((u128)z * near_inv) >> 64;
        const u32 v = z - x * mod;
        return v < mod ? v : v + mod;
    }
    constexpr u32 get_mod() const noexcept { return mod; }
};

}  // namespace proconlib

Back to top page