当x * n溢出时，如何按n/d对x进行缩放? [英] How can I descale x by n/d, when x*n overflows?

问题描述

我的问题仅限于256位无符号整数.

My problem is limited to unsigned integers of 256 bits.

我有一个值 x ，我需要按比例 n/d 对其进行除垢，其中 n<d .

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

简单的解决方案当然是 x * n/d ，但是问题是 x * n 可能溢出.

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.

在计算 x * n/d 之前，将 n 和 d 分别除以 gcd(n，d)>不能保证成功.

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.

推荐答案

注意:使用整数除法而不是普通除法让我们假设

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

x = ad + b
n = cd + e

然后找到a，b，c，e如下:

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

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(位数)执行

这篇关于当x * n溢出时，如何按n/d对x进行缩放?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！