Berechnung großer Potenzierung in Golang

Question

Ich habe versucht, 2^100 in Golang zu berechnen. Ich verstehe die limit of numeric type und versuchte mit math/big Paket. Hier ist, was ich versucht habe, aber ich kann nicht herausfinden, warum es nicht funktioniert.

Ich habe computation by powers of two Methode verwendet, um die Exponentiation zu berechnen.

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-Paket ermöglicht Ihnen calculate x^y in log time (aus irgendeinem Grund heißt es exp). Alles, was Sie brauchen, ist nil als letzten Parameter zu übergeben.

package main 

import (
    "fmt" 
    "math/big" 
) 

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

Wenn Sie daran interessiert sind, wie es selbst zu berechnen, werfen Sie einen Blick auf meine Umsetzung:

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 
} 

oder mit ihm auf go playground spielen.

Answer 2

Sie kehren sofort, wenn power % 2 == 0. Stattdessen möchten Sie nur die result von base ** (power /2) erhalten. Dann multiplizieren Sie result * result, und wenn power gerade ist, dann multiplizieren Sie base damit.

Answer 3

Zum Beispiel

package main 

import (
    "fmt" 
    "math/big" 
) 

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

Ausgang:

1267650600228229401496703205376 

Da es sich um eine Zweierpotenz ist, können Sie auch eine Bitverschiebung tun:

package main 

import (
    "fmt" 
    "math/big" 
) 

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

Ausgang:

1267650600228229401496703205376 

Answer 4

berechnen 2^100

package main 

import (
    "fmt" 
    "math/big" 
) 

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

Playground