ちょっと速いかもしれないローリングハッシュ

追記：速くなってませんでした！sorry https://x.com/yosupot/status/1689337328547016704?s=20

競技プログラミングではmod 261 - 1のローリングハッシュが安全性と速度のバランスが良く、広く使われています。　詳しくは https://qiita.com/keymoon/items/11fac5627672a6d6a9f6 などの記事が有用です。

このmod 261 - 1のmodintをより高速化することを試みます。先ほどの記事や、適当にライブラリを確認すると*1*2、乗算は以下の実装方法が広く使われています

using u64 = unsigned long long;
using u128 = unsigned __int128;

const u64 MOD = (1ULL << 61) - 1;

u64 mul(u64 a, u64 b) {
    u128 t = (u128)(a) * b;
    t = (t >> 61) + (t & MOD);

    return (t >= MOD) ? t - MOD : t;    
}

ここで、値をそのままではなく8倍して管理することを考えます。こうするとif (t >= MOD)相当の処理がoverflow checkになり、雰囲気的に良さそうな気がします。

u64 mul2(u64 a8, u64 b8) {
    u128 c = (u128)(a8) * b8;

    u64 x = (c >> 67 << 3), y = (c << 61 >> 64);

    u64 z;
    if (__builtin_uaddll_overflow(x, y, &z)) z -= MOD << 3;

    return z;
}

u64 mul(u64 a, u64 b) {
    u64 t = mul2(a * 8, b * 8) / 8;
    if (t == MOD) t = 0;
    return t;
}

実際に確認してみましょう。

godbolt.org

mul2のほうがめちゃくちゃすっきりしているのが確認できます。マジックナンバーがなく、本当に正しいのかこれという感じですが、読むと正しそうに思えます。

実際に O(N log2 N) SAを実装してみます

2割ほど早くなりました

注記

  • まだあんまり使ってないので、バグってるかも
  • そもそも従来のmodintのほうに改善の余地がありそう？tweet
  • 値を[0, MOD]で管理する都合上比較が汚くなってしまう　これなんとかなるのかな？ -> https://twitter.com/noshi91/status/1688130780718092288

*1:https://nyaannyaan.github.io/library/internal/internal-hash.hpp

*2:https://hitonanode.github.io/cplib-cpp/number/modint_mersenne61.hpp.html