## 一步步实现比例计算的“完全体”

``````function mulDiv (uint x, uint y, uint z)
public pure returns (uint)``````

``````function mulDiv (uint x, uint y, uint z)
public pure returns (uint)
{
return x * y / z;
}``````

## 我们该如何避免溢出?

``````function mulDiv (uint x, uint y, uint z)
public pure returns (uint)
{
return mul (x, y) / z;
}``````

## 如何在保持精度的同时避免假溢出?

\$\$ x×y÷z= (a×z+b)×(c×z+d)÷z= (a×c×z^2+(a×d+b×c)×z+b×d)÷z= a×b×z+a×d+b×c+b×d÷z \$\$

\$a，b，c\$ 和 \$d\$ 的值可分别用 \$x\$ 和 \$y\$ 对 \$z\$ 求余来计算。

``````function mulDiv (uint x, uint y, uint z)
public pure returns (uint)
{
uint a = x / z; uint b = x % z; // x = a * z + b
uint c = y / z; uint d = y % z; // y = c * z + d
return a * b * z + a * d + b * c + b * d / z;
}``````

## 我们到底如何才能彻底避免假溢出?

``````function mulDiv (uint x, uint y, uint z)
public pure returns (uint)
{
(uint l, uint h) = fullMul (x, y);
return fullDiv (l, h, z);
}``````

``````function fullMul (uint x, uint y)
public pure returns (uint l, uint h)
{
uint xl = uint128 (x); uint xh = x >> 128;
uint yl = uint128 (y); uint yh = y >> 128;

uint xlyl = xl * yl; uint xlyh = xl * yh;
uint xhyl = xh * yl; uint xhyh = xh * yh;

uint ll = uint128 (xlyl);
uint lh = (xlyl >> 128) + uint128 (xlyh) + uint128 (xhyl);
uint hl = uint128 (xhyh) + (xlyh >> 128) + (xhyl >> 128);
uint hh = (xhyh >> 128);

l = ll + (lh << 128);
h = (lh >> 128) + hl + (hh << 128);
}``````

``````function fullDiv(uint l, uint h, uint z) public pure returns (uint r) {
require (h < z);

uint zShift = mostSignificantBit (z);
uint shiftedZ = z;
if (zShift <= 127) zShift = 0;
else
{
zShift -= 127;
shiftedZ = (shiftedZ - 1 >> zShift) + 1;
}

while (h > 0)
{
uint lShift = mostSignificantBit (h) + 1;
uint hShift = 256 - lShift;

uint e = ((h << hShift) + (l >> lShift)) / shiftedZ;
if (lShift > zShift) e <<= (lShift - zShift);
else e >>= (zShift - lShift);

r += e;

(uint tl, uint th) = fullMul (e, z);
h -= th;
if (tl > l) h -= 1;
l -= tl;
}
r += l / z;
}``````

``````function mostSignificantBit (uint x) public pure returns (uint r) {
require (x > 0);

if (x >= 2**128) { x >>= 128; r += 128; }
if (x >= 2**64) { x >>= 64; r += 64; }
if (x >= 2**32) { x >>= 32; r += 32; }
if (x >= 2**16) { x >>= 16; r += 16; }
if (x >= 2**8) { x >>= 8; r += 8; }
if (x >= 2**4) { x >>= 4; r += 4; }
if (x >= 2**2) { x >>= 2; r += 2; }
if (x >= 2**1) { x >>= 1; r += 1; }
}``````

## 我们可以把它弄得便宜一点吗?

``````function fullMul (uint x, uint y)
public pure returns (uint l, uint h)
{
uint mm = mulmod (x, y, uint (-1));
l = x * y;
h = mm - l;
if (mm < l) h -= 1;
}``````

``````function mulDiv(uint x, uint y, uint z) public pure returns (uint) {
(uint l, uint h) = fullMul (x, y);
require (h < z);

uint mm = mulmod (x, y, z);
if (mm > l) h -= 1;
l -= mm;

uint pow2 = z & -z;
z /= pow2;
l /= pow2;
l += h * ((-pow2) / pow2 + 1);

uint r = 1;
r *= 2 - z * r;
r *= 2 - z * r;
r *= 2 - z * r;
r *= 2 - z * r;
r *= 2 - z * r;
r *= 2 - z * r;
r *= 2 - z * r;
r *= 2 - z * r;

return l * r;
}``````

## 在 Solidity 中使用浮点数

``````function mulDiv (uint x, uint y, uint z)
public pure returns (uint) {
return
),
)
);
}``````

## 结论

• 发表于 2020-08-24 09:54
• 阅读 ( 566 )
• 学分 ( 212 )
• 分类：Solidity

Johnathan

PHD

10 篇文章, 1302 学分