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

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
+}