(a*b)/c MulDiv и борьба с переполнением при промежуточном умножении ⇐ JAVA

[Anonymous]

Мне нужно выполнить следующую арифметику:

Код: Выделить всё

long a,b,c;
long result = a*b/c;

Хотя результат гарантированно умещается в длину, умножение — нет, поэтому оно может переполниться.

Я пытался сделать это шаг за шагом (сначала умножить, а затем разделить), одновременно имея дело с переполнением, разделив промежуточный результат a*b на массив int размером максимум 4 (очень похоже на BigInteger использует свою переменную int[] mag).

Здесь я застрял с делением. Я не могу уяснить себе побитовые сдвиги, необходимые для точного деления. Все, что мне нужно, это частное (остаток не нужен).

Гипотетический метод будет следующим:

Код: Выделить всё

public static long divide(int[] dividend, long divisor)

Кроме того, я не рассматриваю возможность использования BigInteger, поскольку эта часть кода должна быть быстрой (я бы хотел придерживаться использования примитивов и примитивных массивов) .

Буду очень признателен за любую помощь!

Изменить:
Я не пытаюсь реализовать весь BigInteger сам. Я пытаюсь решить конкретную проблему (

Код: Выделить всё

a*b/c

, где a*b может переполниться) быстрее, чем использование общего BigInteger.

Edit2: было бы идеально, если бы это можно сделать умным способом, вообще не допуская переполнения, в комментариях появилось несколько советов, но я все еще ищу правильный.

Обновление:
Я пытался портировать код BigInteger под свои конкретные нужды, без создания объекта, и в первой итерации я получил улучшение скорости примерно на 46 % по сравнению с использованием BigInteger (на моем компьютере для разработки).

Затем я попробовал немного модифицированное решение @David Eisenstat, которое дало мне ~ 56 % (я выполнил 100_000_000_000 случайных входных данных из Long.MIN_VALUE до Long.MAX_VALUE) сократило время выполнения (более чем в 2 раза) по сравнению с BigInteger (то есть примерно на 18 % по сравнению с моим адаптированным алгоритмом BigInteger).

Будут еще итерации по оптимизации и тестированию, но на данный момент я думаю, что должен признать этот ответ лучшим.

Подробнее здесь: https://stackoverflow.com/questions/542 ... iplication