1

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.

Shepmaster
  • 388,571
  • 95
  • 1,107
  • 1,366
real
  • 639
  • 1
  • 6
  • 15
  • Have you tried (a/c)*b? Or, e.g, divide both `a` and `b` by `c`c, then multiply by `c`, calculate minimal error and then do the real division: divide the number with smallest error and multiply by the other. Or implement f128 (if f64 is not enough precise). – Alexander Dmitriev May 30 '18 at 09:40
  • Unfortunately it is the way the integers work. I the general case you need a larger type for the intermediate results. In some circumstances smarter formula may help. – 0___________ May 30 '18 at 09:44
  • Do you have any constraints on the relative magnitude of a and b? If they're similar, something like (a/sqrt(c))*(b/sqrt(c)) seems plausible. – R.. GitHub STOP HELPING ICE May 30 '18 at 09:48
  • I'm surprised that *no one* has brought up integer division. `(a * b) / c` **is not equivalent** to `(a / c) * b` under integer division (try with `(a,b,c) = (1,2,2)`). I'm not surprised that any reorganization of the equation produces different results. – Shepmaster May 30 '18 at 13:36
  • There are quite a number of duplicates on this topic e.g. https://stackoverflow.com/questions/8733178/most-accurate-way-to-do-a-combined-multiply-and-divide-operation-in-64-bit/ which should be generalizable to 128-bit. – kennytm May 30 '18 at 14:22

1 Answers1

2

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
}
Peter Hall
  • 53,120
  • 14
  • 139
  • 204