CODEWITHSUNDEEP
mathlanguage-agnosticnumerical-methods
real
real

Reputation: 669

Multiplying fixed size fractions without using a larger container

I am given three unsigned numbers of size 128 bits: a, b, and c where a and b <= c I want to be able to calculate (a * b) / c with the highest possible precision.

If a, b, and c were 64 bit integers, I would first calculate a * b in a 128 bit number and then divide it by c to obtain an accurate result. However, I am dealing with 128 bit numbers and I don't have a native 256 bit type to perform the multiplication a * b.

Is there is a way to compute (a * b) / c with high precision while staying in the world of 128 bits?

My (failed) attempts:

  1. Calculating a / (c / b). This looks somewhat unsymmetrical, and as expected I didn't get very accurate results.

  2. Calculating: ((((a+b)/c)^2 - ((a-b)/c)^2)*c)/4 = ((a*b)/c^2) * c = a*b/c This also gave me pretty inaccurate results.

Upvotes: 1

Views: 161

Answers (1)

Peter Hall
Peter Hall

Reputation: 58735

The question was originally tagged as , so I've assumed that in my answer, even though the tag has now been removed.

As others have said in the comments, you'll always have to step up a size or else you run the risk of an overflow on the multiplication, unless you have some guarantees about the bounds on the sizes of those numbers. There is no larger primitive type than u128 in Rust.

The usual solution is to switch to structures that support arbitrary-precision arithmetic, often referred to as "bignums" or "bigints". However, they are significantly less performant than using native integer types.

In Rust, you can use the num-bigint crate:

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
}

Upvotes: 2

Related Questions