Умножение фракций фиксированного размера без использования контейнера большего размера

Question

Мне дано три числа без знака размером 128 бит: a, b и c, где a и b <= <code>c. Я хочу иметь возможность вычислить (a * b) / c смаксимально возможная точность.

Если бы a, b и c были 64-битными целыми числами, я сначала вычислил бы a * b в 128-битном числе, а затем разделил бы его на c, чтобыполучить точный результат.Тем не менее, я имею дело со 128-битными числами, и у меня нет собственного 256-битного типа для выполнения умножения a * b.

. Есть ли способ вычислить (a * b) / c с высокой точностью, оставаясь вмир 128 бит?

Мои (неудачные) попытки:

1. Расчет a / (c / b).Это выглядит несколько несимметрично, и, как и ожидалось, я не получил очень точных результатов.

2. Расчет: ((((a+b)/c)^2 - ((a-b)/c)^2)*c)/4 = ((a*b)/c^2) * c = a*b/c Это также дало мне довольно неточные результаты.

Answer 1

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

Как уже говорили другие в комментариях,вам всегда придется увеличивать размер, иначе вы рискуете переполнить умножение, если только у вас нет каких-либо гарантий относительно границ размеров этих чисел.В Rust нет примитивного типа большего размера, чем u128.

Обычным решением является переключение на структуры, поддерживающие арифметику произвольной точности , часто называемую "bignums" или "bigints".».Однако они значительно менее производительны, чем при использовании собственных целочисленных типов.

В Rust вы можете использовать num-bigint ящик:

extern crate num_bigint;

use num_bigint::BigUint;

fn main() {
    let a: u128 = 234234234234991231;
    let b: u128 = 989087987;
    let c: u128 = 123;

    let big_a: BigUint = a.into();
    let big_b: BigUint = b.into();
    let big_c: BigUint = c.into();

    let answer = big_a * big_b / big_c;

    println!("answer: {}",  answer);
    // answer: 1883563148178650094572699
}