計算Golang中的大冪求數

我一直試圖計算Golang中的2^100。我瞭解limit of numeric type並嘗試使用math/big包。這是我試過的，但我不明白爲什麼它不起作用。計算Golang中的大冪求數

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) 
}

來源

2015-05-12 Ye Lin Aung

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用它玩。

來源

2015-05-12 05:17:28

的確如此。以兩個'big.Int'作爲參數並沒有什麼意義。我喜歡你的方法。 –

@YeLinAung其實如果在某個時間點你需要大整數，你可以很容易地修改它來做到這一點。我寫這個函數只是爲了作爲一個玩具的例子，以確保我理解算法，但如果需要在生產代碼中的某處使用它，而是使用默認的Exp方法。 –

'new（big.Int）.Exp（big.NewInt（int64（a）），big.NewInt（int64（n）），nil）'更快（並且可以改進爲不重新分配結果，的'數學/大'例程）。 –

如果power % 2 == 0您正在返回。相反，您只需要獲取base ** (power /2)的result。然後乘以result * result，如果power是偶數，那麼就乘以base。

來源

2015-05-12 05:04:39 Santiago

糟糕。這是一個錯誤。我不是故意立即回來。我會更新這個問題。 –

例如，

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

來源

2015-05-12 05:14:09 peterSO

這是一個很好的。在查看'math/big'包時，我沒有看到這一點。 –

爲了計算2^100

package main 

import (
    "fmt" 
    "math/big" 
) 

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

Playground

來源

2015-05-12 06:05:45 user4890052

計算Golang中的大冪求數

回答

相關問題