Как сделать muldiv для больших лонгов на java?

Question

[pqgg7nwkd4]

Добрый день.

Предлагается написать функцию которая выполнит следующее арифметическое действие:
V * A / B.

Требования:
1. Все значения имеют тип long, результат должен быть типом long.
2. Если результат не вмещается в long, функция должна "выбросить" исключение.
3. Функция должна вернуть верное значение, в случае, если V * A не вмещается в long.
4. Функция должна иметь точность как и обычное целочисленное умножение и деление небольших величин.
5. Самое главное. Функция не должна создавать объекты (кроме исключений), не должна использовать числа с плавающей точкой. BigDecimal, BigInteger использовать нельзя. Создание массивов скалярных величин не приветствуется.
6. Задача со звездочкой. Функция не должна содержать циклов.

Вся проблема именно 3 и 5 пункте.

Пример для тестирования:

import java.math.BigInteger;
import java.util.Objects;

public class XP {

    /**
     * Требуемая функция, для расчета value * mul / div.
     */
    public static long mulDiv (long value, long mul, long div) {
        return value * mul / div;
    }

    /**
     * Тест функции. Выводит в консоль результат и ожидаемый результат.
     */
    public static void mulDivTest (long value, long mul, long div) {
        System.out.printf("%d * %d / %d = ", value, mul, div);
        try {
            Long expected;
            try {
                expected = BigInteger.valueOf(value)
                                     .multiply(BigInteger.valueOf(mul))
                                     .divide(BigInteger.valueOf(div))
                                     .longValueExact();
            } catch (Throwable t) {
                expected = null;
            }
            Long got;
            try {
                got = mulDiv(value, mul, div);
            } catch (Throwable t) {
                got = null;
            }
            if (Objects.equals(got, expected)) {
                System.out.printf("%d  OK%n", got);
            } else {
                System.out.printf("%d  !!! FAILED, expected: %d%n", got, expected);
            }
        } catch (Throwable t) {
            System.out.println(t.getMessage());
        }
    }

    public static void main (String[] args) {
        mulDivTest(1, 2, 3);
        mulDivTest(10, 2, 3);
        mulDivTest(10, -2, 3);
        mulDivTest(10, -2, -3);
        mulDivTest(10, 2, -3);
        mulDivTest(1, 3, 3);
        mulDivTest(1, -3, 3);
        mulDivTest(1, 3, -3);
        mulDivTest(1, -3, -3);
        mulDivTest(1000_000_000_000_000_000L, 2_000_000_000L, 3_000_000_000L);
        mulDivTest(1000_000_000_000_000_000L, -2_000_000_000L, 3_000_000_000L);
        mulDivTest(1000_000_000_000_000_000L, 2_000_000_000L, -3_000_000_000L);
        mulDivTest(Long.MIN_VALUE, Long.MAX_VALUE, Long.MAX_VALUE);
        mulDivTest(Long.MAX_VALUE, Long.MAX_VALUE, Long.MIN_VALUE);
        mulDivTest(Long.MAX_VALUE, Long.MAX_VALUE, 100);

        // Задержка для IDEA, чтобы вмешивала в вывод свою информацию.
        try {
            Thread.sleep(100);
        } catch (InterruptedException e) {
        }
    }
}

Вывод примера:

1 * 2 / 3 = 0  OK
10 * 2 / 3 = 6  OK
10 * -2 / 3 = -6  OK
10 * -2 / -3 = 6  OK
10 * 2 / -3 = -6  OK
1 * 3 / 3 = 1  OK
1 * -3 / 3 = -1  OK
1 * 3 / -3 = -1  OK
1 * -3 / -3 = 1  OK
1000000000000000000 * 2000000000 / 3000000000 = 1528315472  !!! FAILED, expected: 666666666666666666
1000000000000000000 * -2000000000 / 3000000000 = -1528315472  !!! FAILED, expected: -666666666666666666
1000000000000000000 * 2000000000 / -3000000000 = -1528315472  !!! FAILED, expected: -666666666666666666
-9223372036854775808 * 9223372036854775807 / 9223372036854775807 = -1  !!! FAILED, expected: -9223372036854775808
9223372036854775807 * 9223372036854775807 / -9223372036854775808 = 0  !!! FAILED, expected: -9223372036854775806
9223372036854775807 * 9223372036854775807 / 100 = 0  !!! FAILED, expected: null

UPD:
Относительно близкий вариант найден в интернете:

/**
     * Требуемая функция, для расчета value * mul / div.
     */
    public static long mulDiv (long a, long b, long c) {
        long whole = a / c * b;
        long fraction1 = (a % c) * (b / c);
        long fraction2 = (a % c) * (b % c) / c;
        return whole + fraction1 + fraction2;
    }

Результат теста:

1 * 2 / 3 = 0  OK
10 * 2 / 3 = 6  OK
10 * -2 / 3 = -6  OK
10 * -2 / -3 = 6  OK
10 * 2 / -3 = -6  OK
1 * 3 / 3 = 1  OK
1 * -3 / 3 = -1  OK
1 * 3 / -3 = -1  OK
1 * -3 / -3 = 1  OK
1000000000000000000 * 2000000000 / 3000000000 = 666666666666666666  OK
1000000000000000000 * -2000000000 / 3000000000 = -666666666666666666  OK
1000000000000000000 * 2000000000 / -3000000000 = -666666666666666666  OK
999000000000000000 * 1000000000000000000 / -1000000000000000000 = -999000000000000000  OK
-9223372036854775808 * 9223372036854775807 / 9223372036854775807 = -9223372036854775808  OK
9223372036854775807 * 9223372036854775807 / -9223372036854775808 = 0  !!! FAILED, expected: -9223372036854775806
9223372036854775807 * 9223372036854775807 / 100 = 553402322211286548  !!! FAILED, expected: null

Answer 1

[Алексей Черемисин]

Ну так ведь V*A/B = (V/B)*(A/B)
Я неправ! Без бумажки плохо...

=(V/B)*A или =V*(B/A)

Соответственно, находим большее из V и A, его и делим, потом умножаем. Ну, там остаток от деления может где взять..

Comments

[pqgg7nwkd4]

Если не обращать внимания на то, что при отрицательном B вы потеряете его знак, то все-равно потеряете точность. Например, V = 2, A = 2, B = 3. Получаем слева: 2 * 2 / 3 = 4 / 3 = 1. Справа: (2 / 3) * (2 / 3) = 0 * 0 = 0. Итого: 1 != 0.

[pqgg7nwkd4]

Хотя, вообще не верно: (V/B) * (A/B) равняется V * A / (B * B).

[Алексей Черемисин]

Упс! Неправ! Исправляюсь.