Tính toán lũy thừa lớn trong Golang

Question

Tôi đã cố gắng tính toán 2^100 trong Golang. Tôi hiểu số limit of numeric type và đã thử sử dụng gói math/big. Đây là những gì tôi đã thử nhưng tôi không thể tìm ra lý do tại sao nó không hoạt động.

Tôi đã sử dụng phương pháp computation by powers of two để tính toán lũy thừa.

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

Gói BigInt cho phép bạn calculate x^y in log time (vì một số lý do nó được gọi là điểm kinh nghiệm). Tất cả bạn cần là để vượt qua nil làm tham số cuối cùng.

package main 

import (
    "fmt" 
    "math/big" 
) 

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

Nếu bạn quan tâm làm thế nào để tính toán nó bằng chính mình, hãy nhìn vào thực hiện của tôi:

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 
} 

hoặc chơi với nó trên go playground.

Answer 2

Bạn sẽ quay lại ngay lập tức nếu power % 2 == 0. Thay vào đó, bạn chỉ muốn nhận được result của base ** (power /2). Sau đó nhân result * result và nếu power thậm chí nhâncho điều đó.

Answer 3

Ví dụ,

package main 

import (
    "fmt" 
    "math/big" 
) 

func main() { 
    z := new(big.Int).Exp(big.NewInt(2), big.NewInt(100), nil) 
    fmt.Println(z) 
} 

Output:

1267650600228229401496703205376 

Kể từ đó là một sức mạnh của hai, bạn cũng có thể làm một sự thay đổi chút:

package main 

import (
    "fmt" 
    "math/big" 
) 

func main() { 
    z := new(big.Int).Lsh(big.NewInt(1), 100) 
    fmt.Println(z) 
} 

Output:

1267650600228229401496703205376 

Answer 4

Để tính 2^100

package main 

import (
    "fmt" 
    "math/big" 
) 

func main() { 
    n := big.NewInt(0) 
    fmt.Println(n.SetBit(n, 100, 1)) 
} 

Playground