雷鋒網(wǎng)按：本文為 AI 研習社編譯的技術博客，原標題 Mathemagic: Full Multiplication，作者為 Remco Bloemen。

翻譯 | 余杭      校對 | 醬番梨      審核 | 醬番梨

大量的智能合約使用 SafeMath 庫，以確保合約的結(jié)果正確，但它是通過使交易失敗，而不是矯正它們。讓我們嘗試進行正確的數(shù)學運算。在本系列中，我會對一些先進的技術進行推導。今天，我會改良 safeMul 庫。

如果對兩個數(shù)值進行相乘，結(jié)果會是之前的兩倍大小。在以太坊中，對兩個數(shù)值進行相乘，結(jié)果最高會是 512 位。但以太坊僅僅給出結(jié)果的下半部分，它會忽略剩余部分。這在數(shù)學中稱作模數(shù)運算。

然而，省略數(shù)字在會計中是不可接受的。因此必須想辦法避免這種情況的發(fā)生，不然會導致某些人失去非常有價值的東西。一個非常受歡迎的庫叫做 SafeMath 。

當這種情況發(fā)生時 SafeMath 就會檢測到然后終止交易，但如果你不希望交易終止又該如何呢？

如果你想要對任意數(shù)值進行想成并且想要得到一個完整的結(jié)果又該怎么辦呢？

溫馨提示：這是能實現(xiàn)上述功能的 Solidity 高亮代碼。

經(jīng)過優(yōu)化的在 Solidity 中完整的 512 位乘法。

在我們深入了解之前，先正確定義問題：即已知兩個無符號數(shù)值 a 和 b ，并且它們的長度都是 256 位，并且希望得到它們的乘積，即 512 位數(shù)字 x 。 

因為數(shù)值過于龐大以至于無法在代碼中呈現(xiàn)，所以我們將其拆分成最低有效 256 位和最高有效 256 位，即 r0 和 r1。對應地：

左邊方括號帶下標的表示模運算，右邊帶下半括號的表示下取整運算。

教科書算法

解決這個問題的經(jīng)典方法是長乘，這個方法我們在學校已經(jīng)學習過了。把大數(shù)拆分成較小的數(shù)，乘以對應位的數(shù)值，然后把結(jié)果相加。這個方法同樣適用于二進制和其他進制。讓我快速地向你們展示在這里如何使用它.

因為支持 256 位內(nèi)置乘法，所以我們可以對任意兩個 128 位數(shù)相乘然后得到全部的結(jié)果。因此如果把大數(shù)拆分成每組 128 位，那么我們可以計算出所有的結(jié)果。取 a0 和 a1 分別對應于 a 的最低有效 128 位和最高有效 128 位，對 b 也是類似的操作：

現(xiàn)在原始數(shù)值 a 和 b 可以等同地寫作 ：

如果我們將其替換進結(jié)果等式，那么原等式可寫作：

忽略常數(shù)部分，我們得到了四個乘式而不是之前的一個。因為四個乘式的數(shù)值都小于 2 的 128 次方，因此可以被直接計算。但結(jié)果依然過于龐大，因此仍然需要用兩個數(shù) r0 和 r1 來表示它。

我會跳過如何從這個表達式中獲取 r0 和 r1 的部分，因為它雖然直接，但是轉(zhuǎn)換和代入過程非常惱人。最終的結(jié)果是： 

支持 512 位的教科書算法

（請注意如果 Solidity 編譯器的版本為 0.4.18，那么在編譯上述實例時會失敗，因為編譯器無法處理過多的本地變量。但這可以通過內(nèi)聯(lián)表達式很輕松地解決，但因為這會降低可讀性所以我沒有選擇在本例中使用內(nèi)聯(lián)表達式。）

i01 以及 i10 兩個乘式可以通過 Karatsuba 算法合并成一個乘式，這是在消耗額外的 gas 為代價的前提下。因為額外的 gas 量為 3，而整個乘式消耗的 gas 量為 5，因此并不值得使用 Karatsuba 算法。但是如果想要做更大位數(shù)的乘法（比如 4096 位），那么值得使用 Karastuba 算法。

通過使用兩個取模運算，四個除法，六個加法，兩個條件分支，以及不少于六個乘法，我們已經(jīng)解決了這個問題。整個函數(shù)總消耗超過 300 gas。這似乎還不錯，但是 gas 的消耗量已經(jīng)超過正常乘法 5 gas 消耗的 2 個數(shù)量級，或是標準 safeMul 的 90 倍。我們可以做得更好。

中國的余數(shù)定理

技巧部分：使用 mulmod 指令以及中國的余數(shù)定理，簡而言之，定理闡述的是如果已知一個數(shù)的模是 2 的 256 次方 以及 2 的 256 次方 -1，那么我們可以計算出它的 512 位表示方法，使用的函數(shù)是 ChineseRemainder , 在 a previous post 中有過相關描述。我們首先需要計算出兩個取模運算的結(jié)果：

......

想要繼續(xù)閱讀，請移步至我們的AI研習社社區(qū)：http://www.gair.link/page/TextTranslation/702

更多精彩內(nèi)容盡在 AI 研習社。

不同領域包括計算機視覺，語音語義，區(qū)塊鏈，自動駕駛，數(shù)據(jù)挖掘，智能控制，編程語言等每日更新。

雷鋒網(wǎng)(公眾號：雷鋒網(wǎng))

                   

雷峰網(wǎng)原創(chuàng)文章，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。