How can I descale x by n/d, when x*n overflows?

Question

My problem is limited to unsigned integers of 256 bits.

I have a value x, and I need to descale it by the ratio n / d, where n < d.

The simple solution is of course x * n / d, but the problem is that x * n may overflow.

I am looking for any arithmetic trick which may help in reaching a result as accurate as possible.

Dividing each of n and d by gcd(n, d) before calculating x * n / d does not guarantee success.

Is there any process (iterative or other) which i can use in order to solve this problem?

Note that I am willing to settle on an inaccurate solution, but I'd need to be able to estimate the error.

Homoeo

The simple answer is to use more bits. To get 256 bits, you must already be using extended precision math, so just do the multiplication into a 512 bit temporary variable. – Coon

@user3386109: "you must already be using extended precision math" - that's wrong. I'm using the language's native uint256 (and there is no larger native type in case you're still wondering). – Homoeo

You can of course make your own extended precision by doing "long" multiplication and division. But there probably is something less tedious. – Birkner

It takes four 128-bit multiplications to compute a 512 bit product, and then the division can be done base 2^128. – Coon

@user3386109: that's sounds like an "ah piece of cake" answer. if you have a solution, can you please post it? – Homoeo

Here's the multiplication part. Division is left as an exercise for the reader. I'll simply note that you are dividing a 4-digit number by a 2-digit number, and that you know that the quotient will be a 2-digit number. – Coon

@user3386109: no, you mentioned something about a 512-bit number, which i don't have in the platform that i'm working on! – Homoeo

The answer I linked shows how to multiply two 64-bit numbers to find a 128-bit product, on a platform that doesn't support 128-bit numbers. That's easily adapted to your use case. – Coon

Does this answer your question? How to multiply a 64 bit integer by a fraction in C++ while minimizing error? – Bodgie

(a * b) / c MulDiv and dealing with overflow from intermediate multiplication, Most accurate way to do a combined multiply-and-divide operation in 64-bit?, How can I multiply and divide 64-bit ints accurately? – Bodgie

Answer 1

NOTE: Using integer division instead of normal division Let us suppose

x = ad + b
n = cd + e

Then find a,b,c,e as follows:

a = x/d
b = x%d
c = n/d
e = n%d

Then,

nx/d = acd + ae + bc + be/d

CALCULATING be/d

1. Represent e in binary form
2. Find b/d, 2b/d, 4b/d, 8b/d, ... 256b/d and their remainders
3. Find be/d = b*binary terms + their remainders

Example:

e = 101 in binary = 4+1
be/d = (b/d + 4b/d) + (b%d + 4b%d)/d

FINDING b/d, 2b/d, ... 256b/d

quotient(2*ib/d) = 2*quotient(ib /d) + (2*remainder(ib /d))/d
remainder(2*ib/d) = (2*remainder(ib/d))%d

Executes in O(number of bits)

Redman

TX. Is acd not susceptible to overflow just as much as xn is? – Homoeo

BTW, according to the definition in my question, n/d = 0 and n%d = d. So I doubt that your answer is correct. – Homoeo

@Homoeo If n/d=0 then n=0 implying c and e are both 0. So output is correct. If acd overflows, then mathematically, the exact value of (n*x/d) overflows. You won't be able to store it – Redman

acd can't overflow because c is 0. The problem is that be may overflow. – Birkner

@NateEldredge b and e are both less than d. So the product is less than d^2 – Redman

Sure, and d^2 could also overflow. We have no information on the maximum size of d except that it is at most 256 bits. – Birkner

(For the thing about n/d, I assume you're using integer division which rounds down. n/d=0 does not imply that n=0, only that n < d, and this was indeed one of the assumptions.) – Birkner

@NateEldredge Yeah I was using integer division. I'll fix that in the answer. My point is, if be overflows, the exact value of (xn/d) overflows. So it isn't possible to store the answer – Redman

@NateEldredge: I wrote that my problem is limited to unsigned integers at the top of my question. So of course I'm relying on integer division here. – Homoeo

@AbhayAravinda: The exact value of x*n/d cannot overflow because n < d! The only overflow that I'm worried about is in the intermediate result of x*n. – Homoeo

@AbhayAravinda: I think you are mistaken. Let's try an example with 8 bits instead of 256 to make the numbers smaller. Suppose d=32, n=19, x=191, so a=5, b=31, c=0, e=19. The result of x*n/d should be 113 which does not overflow. But b*e=589 which does overflow. – Birkner

I completely agree that the result of b*e/d fits within 8 bits. But how do you compute it without first computing b*e, which needs more than 8 bits? – Birkner

Repeating anything b times is not going to be very practical, as b could be as large as d which is 256 bits. You are asking for up to 2^256 iterations of your loop and that will not finish before the sun goes out. – Birkner

@NateEldredge How about now. Got it to O(log d) – Redman