數學魔法：乘法部分

雷鋒網按：本文為 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 中有過相關描述。我們首先需要計算出兩個取模運算的結果：

......

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！