主页 / 问题 / 1597505
Accepted
Mastas
Asked:2024-10-22 22:36:46 +0000 UTC2024-10-22 22:36:46 +0000 UTC

获取范围 int 后面的乘积的整数余数

  • 772

假设有 2 个随机数的乘积，每个随机数的长度为 10 到 16 个字符：

1 - 6545134143
2 - 3272567071

在 PHP 8+ 版本中正常工作时，会产生小数点后 14 位的 Float 类型数字：

6545134143 * 3272567071 = 2.1419390471659606E+19

如果通过 GMP 执行相同的操作，您已经获得了所需的小数点后完整位数的数字：

gmp_strval(gmp_mul(6545134143 , 3272567071)) = 21419390471659605153

请注意，对于 GMP，结尾不会四舍五入（从 5 到 6），而是完整呈现 - 605153。

完成运算后，您需要找出这个长数字除以数字 4294967296 的余数，该数字是通过数字与超出标准 64 位整数和 14 个字符的标准精度相乘得到的。

如果您通过 gmp_mod() 执行此操作，那么您将得到您所需要的 - 816336033。我的猜测是，这是某种将这个巨大数字转换为 32 位格式的尝试，因为它与格式非常相似 (& 0xFFFFFFFF) 。

实际上，问题是这样的 - 考虑到 PHP 可能的数值范围的所有细微差别和限制（我们正在谈论 x64 8.3） - 是否有可能以某种方式避免这种巨大的乘法，从整数除法中获得相同的余数（指的是数字本身，而不是特定操作的结果）？我尝试将每个数字分别除以 4294967296，然后将所得余数相乘，但所有数字都归结为 14 位数字，结果纯粹是无意义的。还有一种假设认为这可以通过操纵数字系统来实现......

我想用纯 PHP 来完成它，因为理论上它比调用 GMP 扩展更快，并且在几百万次操作的距离上它应该节省很多秒......

我尝试通过配置将精度移至 16 和 -1 - 结果完全为零，这个词根本没有任何变化。请帮忙和指教）

php

2 个回答

  1. Best Answer

    要解决您的问题，关键是正确处理大整数，避免将它们转换为浮点类型。由于 PHP 在处理非常大的数字时默认使用浮点数，因此有必要使用一种方法直接获取余数，从而绕过数字本身相乘的步骤。

    <?php

/**
 * Вычисляет остаток от деления произведения двух больших чисел на 2^32
 * используя свойства модульной арифметики
 */
class ModularMultiplier
{
    private const MODULUS = 4294967296; // 2^32
    private const HALF_BITS = 16;
    private const HALF_MASK = 65535; // 2^16 - 1

    public static function multiplyMod(int $a, int $b): int
    {
        // Разбиваем числа на старшую и младшую части по 16 бит
        $a1 = ($a >> self::HALF_BITS) & self::HALF_MASK;
        $a0 = $a & self::HALF_MASK;
        $b1 = ($b >> self::HALF_BITS) & self::HALF_MASK;
        $b0 = $b & self::HALF_MASK;

        // Вычисляем компоненты произведения
        // (a1 * 2^16 + a0)(b1 * 2^16 + b0) = 
        // (a1*b1 * 2^32) + (a1*b0 + a0*b1) * 2^16 + a0*b0

        // Нам нужен только остаток от деления на 2^32, поэтому:
        // 1. a1*b1 * 2^32 mod 2^32 = 0
        // 2. Для средних членов нужно умножить на 2^16
        // 3. Младшие разряды просто перемножаем

        // Вычисляем средние члены
        $middle = ($a1 * $b0 + $a0 * $b1) & self::HALF_MASK;
        $middle = ($middle << self::HALF_BITS) % self::MODULUS;

        // Вычисляем младшие разряды
        $lower = ($a0 * $b0) % self::MODULUS;

        // Складываем результаты и берем остаток
        return ($middle + $lower) % self::MODULUS;
    }
}

// Тестирование
$a = 6545134143;
$b = 3272567071;

$result = ModularMultiplier::multiplyMod($a, $b);
echo "Результат: " . $result . "\n";

// Проверка с помощью GMP для сравнения
if (extension_loaded('gmp')) {
    $gmp_result = gmp_strval(gmp_mod(gmp_mul($a, $b), 4294967296));
    echo "GMP результат: " . $gmp_result . "\n";
    echo "Совпадает: " . ($result == $gmp_result ? "да" : "нет") . "\n";
}
    • 2

  2. 您需要找到一个因子除以给定数字的余数，将其乘以第二个因子，然后再次找到除法的余数。这将是您要查找的号码。但由于你给定的数字也很大，所以你在这里不会获得太多收益。

    但鉴于 4294967296 是 2^32，您只需始终保留最低有效的 32 位数字即可。这将是该部门的剩余部分。

    @eminsk 在那里写道...它需要分成 16 位字。

    prod = ((msw1 * lsw2 + msw2 * lsw1) << 16) + lsw2 * lsw1，但 msw1 * msw2 << 32 可以省略。

    • 1

相关问题