MSVC Compiler intrinsics _umul128 and _udiv128

Правка en7, от JaroPaska, 2022-08-28 11:23:44

For some algorithms it is necessary to calculate the modulo of the product of two 64-bit integers (rho algorithm, polynomial rolling hash with a 64-bit modulo). This can be done easily on GCC and Clang using the built-in type __int128.

However, on MSVC this type is not available. This blog post explores the options for implementing fast modular multiplication across various platforms. The author presents several approaches to modular multiplication, but only two of those actually work properly on the MSVC compiler. Those implementations are fine, but one of them is somewhat slow while the other uses a Karatsuba-like approach and I found it too complex to be comfortable with simply copy-pasting it into my template.

I did a bit of googling and stumbled across the compiler intrinsics umul128 and udiv128, which can be used to implement modular multiplication in a way that is fairly straightforward.

Note that both __int128 and the MSVC compiler intrinsics are only supported on 64-bit architectures. They don't seem to be available on the Codeforces MSVC compiler, but they work fine for me locally. This is good enough for me as I have a cross platform coding environment and I want my code to work when on Windows machines with the Microsoft compiler.

Here is the snippet that I use for modular multiplication. Feel free to share any micro-optimizations you might have.

template <class T>
constexpr int sgn(T x) {
    return (x > 0) - (x < 0);
}

long long mod_mul(long long a, long long b, long long m = MOD) {
#ifdef _MSC_VER
    unsigned long long h, l, r;
    l = _umul128(llabs(a), llabs(b), &h);
    _udiv128(h, l, m, &r);
    return sgn(a) * sgn(b) >= 0 ? r : m - r;
#else
    long long r = a * static_cast<__int128>(b) % m;
    return r >= 0 ? r : r + m;
#endif
}
Теги number theory, compilers, msvc, msvc++, c++, modular arithmetic

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en7 Английский JaroPaska 2022-08-28 11:23:44 82
en6 Английский JaroPaska 2022-08-28 11:23:21 2 Tiny change: '128(llabs((a)), llabs(b' -> '128(llabs(a), llabs(b'
en5 Английский JaroPaska 2022-08-28 11:22:56 178
en4 Английский JaroPaska 2022-08-28 11:14:33 109
en3 Английский JaroPaska 2022-08-28 04:19:06 16 Tiny change: 'integers (Pollard Rho, polynomi' -> 'integers (rho algorithm, polynomi'
en2 Английский JaroPaska 2022-08-28 04:15:24 2
en1 Английский JaroPaska 2022-08-28 04:14:38 2020 Initial revision (published)