Получение целочисленного остатка от произведения за диапазоном int

Question

Предполагается, что есть некое произведение 2-х случайных чисел, каждое из которых в длину от 10 до 16 знаков:

1 - 6545134143
2 — 3272567071

При обычном произведении на PHP 8+ версии выбивает число типа Float с 14 цифрами после запятой:

6545134143 * 3272567071 = 2.1419390471659606E+19

Если выполнять эту же операцию через GMP — получаем уже нужное число c полным количеством цифр после запятой:

gmp_strval(gmp_mul(6545134143 , 3272567071)) = 21419390471659605153

Обратите внимание, что в случае с GMP окончание не округлено в большую сторону (с 5 до 6), а представлено в полном виде — 605153.

После выполненных операций требуется узнать остаток от деления этого длиннющего числа, полученного путём перемножения чисел и выходящего за рамки стандарта 64bit integer и стандартной точности в 14 символов, на число 4294967296.

Если это делать через gmp_mod(), то получается именно то, что надо — 816336033.

У меня такое предположение, что это какая-то попытка перевести это огромное число в формат 32bit, потому что это очень похоже на формат (& 0xFFFFFFFF).

Собственно, вопрос такой:

Учитывая все нюансы и пределы возможного числового диапазона PHP (речь идёт про х64 8.3) можно ли как-то, избегая этого огромного умножения, получить такой же остаток от целочисленного деления (имеется ввиду само число, а не результат конкретной операции)?

Я пробовал каждое число по отдельности делить на 4294967296 и потом полученные остатки перемножать, но там опять всё упирается в 14 цифр, и получается сущая бредятина.

Есть ещё предположение, что это можно как-то провернуть, манипулируя системой исчисления...

Хочется сделать именно на чистом PHP, потому что, по идее, он быстрее, чем вызов расширения GMP, и на дистанции в пару млн операций это должно экономить доброе кол-во секунд...

Я пробовал двигать через конфиг точность до 16 и -1 — результат вообще нулевой, ничего не поменялось от слова совсем.

Прошу помочь и подсказать)

Answer 1

Нужно найти остаток от деления одного сомножителя на заданное число, умножить его на второй сомножитель и снова найти остаток от деления. Это будет искомое число. Но поскольку у вас заданное число тоже большое, особо вы ничего тут не выиграете.

Но с учётом того, что 4294967296 — это 2³², вам просто нужно всё время оставлять 32 младших разряда, и всё. Это и будет остаток от деления.

@eminsk там пишет... Нужно разбивать на 16-битовые слова.

prod = ((msw1 * lsw2 + msw2 * lsw1) << 16) + lsw2 * lsw1

А вот msw1 * msw2 << 32 можно и не добавлять.

Answer 2

Для решения твоей задачи, ключевым является правильная работа с целыми числами больших размеров, избегая их преобразования в тип float. Так как 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";
}

БЛОГ НА HUSL

Получение целочисленного остатка от произведения за диапазоном int

Собственно, вопрос такой:

Ответы (2 шт):