goo*_*ion 5 algorithm math division integer-arithmetic
我的问题仅限于 256 位无符号整数。
我有一个值x，我需要按比率对其进行除垢n / d，其中n < d。
简单的解决方案当然是x * n / d，但问题是x * n可能会溢出。
我正在寻找任何可能有助于获得尽可能准确的结果的算术技巧。
在计算之前将每个 和 除以n并d不能保证成功。gcd(n, d)x * n / d
我可以使用任何流程（迭代或其他）来解决这个问题吗？
请注意，我愿意选择不准确的解决方案，但我需要能够估计错误。
注意：使用整数除法而不是普通除法让我们假设
x = ad + b
n = cd + e
然后求a、b、c、e如下：
a = x/d
b = x%d
c = n/d
e = n%d
然后，
nx/d = acd + ae + bc + be/d
计算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
例子：
e = 101 in binary = 4+1
be/d = (b/d + 4b/d) + (b%d + 4b%d)/d
发现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
执行时间为 O（位数）