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

user_7400903 0
Viewed 132

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.

integer-arithmetic math division algorithm
1 Answers

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)

user_102814560
Related