关于 StaticModInt64 乘法精度问题

bandiaoz commented 3 weeks ago

#include <bits/stdc++.h>
#include "MATH/StaticModInt64.h"

using ll = long long;
using mint = OY::mint4611686018427387847;

int main() {
    ll a = 2, b = 1e9;
    std::cout << mint(a).pow(b) << "\n";

    return 0;
}

对于这份代码，正确的结果应该是 4580536984246035897，但是我运行得到的结果是 132756071612728298。我将 StaticModInt64.h 文件中的 34 行的 int64_t res = a * b - mod_type((long double)(a)*b / mod()) * mod(); 修改为 int64_t res = __int128(a) * b % mod(); 后可以得到正确的结果。但是我无法在除了我的电脑以外的环境复现这个问题，我使用的是 brew 下的 gcc-14，具体信息如下：

brew info gcc
==> gcc: stable 14.2.0 (bottled), HEAD
GNU compiler collection
https://gcc.gnu.org/
Installed
/opt/homebrew/Cellar/gcc/14.1.0_2 (1,913 files, 473.3MB) *
  Poured from bottle using the formulae.brew.sh API on 2024-07-23 at 11:54:53
From: https://github.com/Homebrew/homebrew-core/blob/HEAD/Formula/g/gcc.rb
License: GPL-3.0-or-later WITH GCC-exception-3.1

虽然我在本地环境中遇到了这个问题，但在其他环境包括各种 oj 的在线测试中没有复现。

old-yan commented 3 weeks ago

能否提供关于您的环境的 long double 的位数大小？运行如下代码后，我发现在能够得出正确取模结果的环境下， long double 的输出结果为 16 3.6452e-4951 3.3621e-4932 1.18973e+4932 或 12 3.6452e-4951 3.3621e-4932 1.18973e+4932 （ codeforces, GNU G++17 7.3.0）。

而 MSVC 对你给出的代码的计算结果为 1620087239801630312 。 MSVC 给出的环境参数为 8 4.94066e-324 2.22507e-308 1.79769e+308 。

#include <cstdint>
#include <iostream>
#include <limits>

int main() {
    std::cout << sizeof(long double) << " "
        << std::numeric_limits<long double>::denorm_min() << " "
        << std::numeric_limits<long double>::min() << " "
        << std::numeric_limits<long double>::max() << "\n";
}

因此，我猜测是您的编译器的 long double 只达到了双精度，而没有采用更高精度的数据类型，而导致的计算错误。

bandiaoz commented 3 weeks ago

原来是这样，我的运行结果和 MSVC 环境运行结果一致，非常感谢您的解答！

old-yan / CP-template

关于 StaticModInt64 乘法精度问题 #5