Calcolo grande elevazione a potenza in Golang

Question

ho cercato di calcolare 2^100 in Golang. Comprendo lo limit of numeric type e ho provato ad usare il pacchetto math/big. Ecco cosa ho provato ma non riesco a capire perché non funzioni.

ho usato computation by powers of two metodo per calcolare l'elevamento a potenza.

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

pacchetto BigInt consente di calculate x^y in log time (per qualche motivo si chiama exp). Tutto ciò che serve è passare nil come ultimo parametro.

package main 

import (
    "fmt" 
    "math/big" 
) 

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

Se siete interessati come calcolare da soli, dare un'occhiata a mia implementazione:

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 
} 

o giocare con esso su go playground.

Answer 2

Si ritorna immediatamente se power % 2 == 0. Invece, vuoi solo ottenere il result di base ** (power /2). Quindi moltiplicare result * result, e se è ancora power quindi moltiplicare base a quello.

Answer 3

Per esempio,

package main 

import (
    "fmt" 
    "math/big" 
) 

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

uscita:

1267650600228229401496703205376 

Dal momento che è una potenza di due, si potrebbe anche fare uno spostamento di bit:

package main 

import (
    "fmt" 
    "math/big" 
) 

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

uscita:

1267650600228229401496703205376 

Answer 4

Per calcolare 2^100

package main 

import (
    "fmt" 
    "math/big" 
) 

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

Playground