Расчет большого возведения в степень в Голанге

Question

Я пытался рассчитать 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.

Answer 2

Вы возвращаетесь немедленно, если power % 2 == 0. Вместо этого вы просто хотите получить result от base ** (power /2). Затем умножьте result * result, и если power даже тогда умножьте base на это.

Answer 3

Например,

package main 

import (
    "fmt" 
    "math/big" 
) 

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

Выход:

1267650600228229401496703205376 

Поскольку это сила двух, вы могли бы также сделать немного сдвиг:

package main 

import (
    "fmt" 
    "math/big" 
) 

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

Выход:

1267650600228229401496703205376 

Answer 4

Для вычисления 2^100

package main 

import (
    "fmt" 
    "math/big" 
) 

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

Playground