Barrett Reduction

Assembly Level에서 가장 느린 Arithmetic 연산을 꼽으라고 한다면, modular 연산일 것이다. 보통 PS에서는 나눗셈 연산이 소수값이 나오지 않도록 하기 위해서 modular 연산을 한 값을 출력하도록 하는 경우가 많은데, 이 경우 일단 modular 연산 자체를 줄이는게 첫번째고, 도저히 안될 경우 차선책으로 사용할 수 있는 방법이다.

이 방법은 modular 연산을 곱셈과 if 분기로 처리하게 된다. 단, modular를 수행할 값을 미리 알고 있어야 한다. (즉, MOD가 계속 바뀌면 안된다.) 또한, 이 MOD는 32비트 자료형 안에 들어갈 수 있는 자료형이어야 한다고 한다.

그리고, 비트연산을 활용하는 기법이기 때문에 128비트 자료형이 잠시 사용된다. MSVC에서는 변경이 필요할 것이다.

constexpr ll MOD = 1000000007;
constexpr ll IMOD = 0xFFFFFFFFFFFFFFFF / MOD + 1;
inline ll modular(ull n) {
    ull x = ull((__uint128_t(n) * IMOD) >> 64);
    unsigned int r = n - x * m;
    return m <= r ? x - 1 : x;
}

실제로 사용할 때는

a = b % MOD;

위 코드가

a = modular(b);

가 될 것이다. 물론 서두에 말한 것처럼 IMOD 값은 미리 계산되어 있어야 한다.

놀라운 점은 함수 안의 모양이 저렇게 복잡한데도 일반 modular 연산보다 빠른 결과가 나온다는 것..

참고자료

• NyaanNyaan의 Library: https://github.com/NyaanNyaan/library/blob/master/modint/barrett-reduction.hpp