5

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.

halfer
  • 19,824
  • 17
  • 99
  • 186
goodvibration
  • 5,980
  • 4
  • 28
  • 61
  • 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. – user3386109 Jul 25 '20 at 19:32
  • @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). – goodvibration Jul 25 '20 at 19:47
  • You can of course make your own extended precision by doing "long" multiplication and division. But there probably is something less tedious. – Nate Eldredge Jul 25 '20 at 19:50
  • It takes four 128-bit multiplications to compute a 512 bit product, and then the division can be done base 2^128. – user3386109 Jul 25 '20 at 19:57
  • @user3386109: that's sounds like an "ah piece of cake" answer. if you have a solution, can you please post it? – goodvibration Jul 25 '20 at 20:08
  • [Here's the multiplication part](https://stackoverflow.com/a/26855440/3386109). 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. – user3386109 Jul 25 '20 at 20:12
  • @user3386109: no, you mentioned something about a 512-bit number, which i don't have in the platform that i'm working on! – goodvibration Jul 25 '20 at 20:15
  • 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. – user3386109 Jul 25 '20 at 20:18
  • Does this answer your question? [How to multiply a 64 bit integer by a fraction in C++ while minimizing error?](https://stackoverflow.com/questions/25182577/how-to-multiply-a-64-bit-integer-by-a-fraction-in-c-while-minimizing-error) – phuclv Jul 26 '20 at 04:51
  • [(a * b) / c MulDiv and dealing with overflow from intermediate multiplication](https://stackoverflow.com/q/54232987/995714), [Most accurate way to do a combined multiply-and-divide operation in 64-bit?](https://stackoverflow.com/q/8733178/995714), [How can I multiply and divide 64-bit ints accurately?](https://stackoverflow.com/q/18022544/995714) – phuclv Jul 26 '20 at 04:52

1 Answers1

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)

Abhay Aravinda
  • 878
  • 6
  • 17
  • TX. Is `acd` not susceptible to overflow just as much as `xn` is? – goodvibration Jul 25 '20 at 18:51
  • BTW, according to the definition in my question, `n/d = 0` and `n%d = d`. So I doubt that your answer is correct. – goodvibration Jul 25 '20 at 18:53
  • @goodvibration 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 – Abhay Aravinda Jul 25 '20 at 18:55
  • `acd` can't overflow because `c` is 0. The problem is that `be` may overflow. – Nate Eldredge Jul 25 '20 at 18:56
  • @NateEldredge b and e are both less than d. So the product is less than d^2 – Abhay Aravinda Jul 25 '20 at 18:56
  • 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. – Nate Eldredge Jul 25 '20 at 18:58
  • (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.) – Nate Eldredge Jul 25 '20 at 19:00
  • @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 – Abhay Aravinda Jul 25 '20 at 19:02
  • @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. – goodvibration Jul 25 '20 at 19:02
  • @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`. – goodvibration Jul 25 '20 at 19:03
  • 1
    @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. – Nate Eldredge Jul 25 '20 at 19:07
  • 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? – Nate Eldredge Jul 25 '20 at 19:09
  • 2
    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. – Nate Eldredge Jul 25 '20 at 19:21
  • @NateEldredge How about now. Got it to O(log d) – Abhay Aravinda Jul 25 '20 at 20:22