数学魔法：（以太坊中的）乘法部分

雷锋网按：本文为 AI 研习社编译的技术博客，原标题 Mathemagic: Full Multiplication，作者为 Remco Bloemen。

翻译 | 余杭      校对 | 酱番梨      审核 | 酱番梨

大量的智能合约使用 SafeMath 库，以确保合约的结果正确，但它是通过使交易失败，而不是矫正它们。让我们尝试进行正确的数学运算。在本系列中，我会对一些先进的技术进行推导。今天，我会改良 safeMul 库。

如果对两个数值进行相乘，结果会是之前的两倍大小。在以太坊中，对两个数值进行相乘，结果最高会是 512 位。但以太坊仅仅给出结果的下半部分，它会忽略剩余部分。这在数学中称作模数运算。

然而，省略数字在会计中是不可接受的。因此必须想办法避免这种情况的发生，不然会导致某些人失去非常有价值的东西。一个非常受欢迎的库叫做 SafeMath 。

当这种情况发生时 SafeMath 就会检测到然后终止交易，但如果你不希望交易终止又该如何呢？

如果你想要对任意数值进行想成并且想要得到一个完整的结果又该怎么办呢？

温馨提示：这是能实现上述功能的 Solidity 高亮代码。

经过优化的在 Solidity 中完整的 512 位乘法。

在我们深入了解之前，先正确定义问题：即已知两个无符号数值 a 和 b ，并且它们的长度都是 256 位，并且希望得到它们的乘积，即 512 位数字 x 。 

因为数值过于庞大以至于无法在代码中呈现，所以我们将其拆分成最低有效 256 位和最高有效 256 位，即 r0 和 r1。对应地：

左边方括号带下标的表示模运算，右边带下半括号的表示下取整运算。

教科书算法

解决这个问题的经典方法是长乘，这个方法我们在学校已经学习过了。把大数拆分成较小的数，乘以对应位的数值，然后把结果相加。这个方法同样适用于二进制和其他进制。让我快速地向你们展示在这里如何使用它.

因为支持 256 位内置乘法，所以我们可以对任意两个 128 位数相乘然后得到全部的结果。因此如果把大数拆分成每组 128 位，那么我们可以计算出所有的结果。取 a0 和 a1 分别对应于 a 的最低有效 128 位和最高有效 128 位，对 b 也是类似的操作：

现在原始数值 a 和 b 可以等同地写作 ：

如果我们将其替换进结果等式，那么原等式可写作：

忽略常数部分，我们得到了四个乘式而不是之前的一个。因为四个乘式的数值都小于 2 的 128 次方，因此可以被直接计算。但结果依然过于庞大，因此仍然需要用两个数 r0 和 r1 来表示它。

我会跳过如何从这个表达式中获取 r0 和 r1 的部分，因为它虽然直接，但是转换和代入过程非常恼人。最终的结果是： 

支持 512 位的教科书算法

（请注意如果 Solidity 编译器的版本为 0.4.18，那么在编译上述实例时会失败，因为编译器无法处理过多的本地变量。但这可以通过内联表达式很轻松地解决，但因为这会降低可读性所以我没有选择在本例中使用内联表达式。）

i01 以及 i10 两个乘式可以通过 Karatsuba 算法合并成一个乘式，这是在消耗额外的 gas 为代价的前提下。因为额外的 gas 量为 3，而整个乘式消耗的 gas 量为 5，因此并不值得使用 Karatsuba 算法。但是如果想要做更大位数的乘法（比如 4096 位），那么值得使用 Karastuba 算法。

通过使用两个取模运算，四个除法，六个加法，两个条件分支，以及不少于六个乘法，我们已经解决了这个问题。整个函数总消耗超过 300 gas。这似乎还不错，但是 gas 的消耗量已经超过正常乘法 5 gas 消耗的 2 个数量级，或是标准 safeMul 的 90 倍。我们可以做得更好。

中国的余数定理

技巧部分：使用 mulmod 指令以及中国的余数定理，简而言之，定理阐述的是如果已知一个数的模是 2 的 256 次方 以及 2 的 256 次方 -1，那么我们可以计算出它的 512 位表示方法，使用的函数是 ChineseRemainder , 在 a previous post 中有过相关描述。我们首先需要计算出两个取模运算的结果：

......

想要继续阅读，请移步至我们的AI研习社社区：http://www.gair.link/page/TextTranslation/702

更多精彩内容尽在 AI 研习社。

不同领域包括计算机视觉，语音语义，区块链，自动驾驶，数据挖掘，智能控制，编程语言等每日更新。

雷锋网(公众号：雷锋网)