aboutsummaryrefslogtreecommitdiffstats
path: root/common
diff options
context:
space:
mode:
authorJeffrey Wilcke <jeffrey@ethereum.org>2016-11-02 19:43:15 +0800
committerPéter Szilágyi <peterke@gmail.com>2016-11-02 19:43:15 +0800
commit1b73c79234a1597f1f8b11cff5e01b935f6817a2 (patch)
tree7ef33a6db6a9c4cb906246423c61166479241570 /common
parent36956da4d2a9e5d9099179f9ce8690b2775b560a (diff)
downloadgo-tangerine-1b73c79234a1597f1f8b11cff5e01b935f6817a2.tar.gz
go-tangerine-1b73c79234a1597f1f8b11cff5e01b935f6817a2.tar.zst
go-tangerine-1b73c79234a1597f1f8b11cff5e01b935f6817a2.zip
common/math, core/vm: implement fast EXP (#3214)
* common/math, core/vm: implement fast EXP. Courtesy @chfast & @karalabe * common/math: fix go vet issues on exp calculation
Diffstat (limited to 'common')
-rw-r--r--common/math/exp.go28
1 files changed, 28 insertions, 0 deletions
diff --git a/common/math/exp.go b/common/math/exp.go
new file mode 100644
index 000000000..bd6eeb031
--- /dev/null
+++ b/common/math/exp.go
@@ -0,0 +1,28 @@
+package math
+
+import (
+ "math/big"
+
+ "github.com/ethereum/go-ethereum/common"
+)
+
+// wordSize is the size number of bits in a big.Int Word.
+const wordSize = 32 << (uint64(^big.Word(0))>>63)
+
+// Exp implement exponentiation by squaring algorithm.
+//
+// Courtesy @karalabe and @chfast
+func Exp(base, exponent *big.Int) *big.Int {
+ result := big.NewInt(1)
+
+ for _, word := range exponent.Bits() {
+ for i := 0; i < wordSize; i++ {
+ if word&1 == 1 {
+ common.U256(result.Mul(result, base))
+ }
+ common.U256(base.Mul(base, base))
+ word >>= 1
+ }
+ }
+ return result
+}