go - 在 Golang 中计算大幂

Question

我一直在尝试用 Golang 计算 2^100。我了解 limit of numeric type并尝试使用 math/big 包。这是我尝试过的方法，但我不明白为什么它不起作用。

我用过 computation by powers of two计算指数的方法。

package main

import (
    "fmt"
    "math/big"
)

func main() {
    two := big.NewInt(2)
    hundred := big.NewInt(50)
    fmt.Printf("2 ** 100    is %d\n", ExpByPowOfTwo(two, hundred))
}

func ExpByPowOfTwo(base, power *big.Int) *big.Int {
    result := big.NewInt(1)
    zero := big.NewInt(0)
    for power != zero {
        if modBy2(power) != zero {
            multiply(result, base)
        }
        power = divideBy2(power)
        base = multiply(base, base)
    }
    return result
}

func modBy2(x *big.Int) *big.Int {
    return big.NewInt(0).Mod(x, big.NewInt(2))
}

func divideBy2(x *big.Int) *big.Int {
    return big.NewInt(0).Div(x, big.NewInt(2))
}

func multiply(x, y *big.Int) *big.Int {
    return big.NewInt(0).Mul(x, y)
}

Answer 1

BigInt 包允许您calculate x^y in log time (出于某种原因，它被称为 exp)。您只需将 nil 作为最后一个参数传递即可。

package main

import (
    "fmt"
    "math/big"
)

func main() {
    fmt.Println(new(big.Int).Exp(big.NewInt(5), big.NewInt(20), nil))
}

如果你对如何自己计算感兴趣，可以看看我的实现:

func powBig(a, n int) *big.Int{
    tmp := big.NewInt(int64(a))
    res := big.NewInt(1)
    for n > 0 {
        temp := new(big.Int)
        if n % 2 == 1 {
            temp.Mul(res, tmp)
            res = temp
        }
        temp = new(big.Int)
        temp.Mul(tmp, tmp)
        tmp = temp
        n /= 2
    }
    return res
}

或在 go playground 上使用它.