Golang斐波那契計算出現關閉

我目前對我的斐波那契計算有以下代碼。我試圖計算大量數據，但是一旦它達到100，就會出現計算結果。對於fib（100），我的代碼返回3736710778780434371，但是當我查看其他來源時，它告訴我正確的計算應該是354224848179261915075.我的代碼中是否存在問題，還是與我的計算機硬件或其他問題有關？Golang斐波那契計算出現關閉

package main 
import "fmt" 

func fib(N uint) uint{ 


    var table []uint 
    table = make([]uint, N+1) 
    table[0] = 0 
    table[1] = 1 


    for i := uint(2); i <= N; i += 1 { 

    table[i] = table[i-1] + table[i-2] 


    } 

    return table[N] 

} 

func main() { 
    fmt.Println(fib(100)) 
}

來源

2014-11-08 freetoplay

您遇到了整數溢出！您只能使用uint來計算，最大爲uint;一旦你超越界限，它會（默默地）再次迴繞。

在你的情況下，它看起來好像一個uint是64位長。（它的大小取決於你運行的平臺。）這意味着你將能夠存儲高達2 -1的值。如果你再添加一個，它會回到0，並且不會返回錯誤。

如果轉換你得到的答案和正確答案，爲十六進制，然後你會看到這種情況。你跟

33DB76A7C594BFC3

結束了，而正確答案是

1333DB76A7C594BFC3

請注意，你的答案是正確的，只要它去......它只是不走的不夠遠。你只有答案的低64位;你錯過了其他13 * 2 。

要糾正它，您需要使用Package big中的任意大小整數，而不是uint。

來源

2014-11-08 21:48:00

只是一個額外的例子，使用'檢查階乘代碼數學/ big' @ HTTPS ：//github.com/OneOfOne/go-utils/blob/master/math/fact.go。 – OneOfOne 2014-11-08 22:49:55

下面是使用big.Int版本產生正確答案（playground）

package main 

import (
    "fmt" 
    "math/big" 
) 

func fib(N uint) *big.Int { 
    var table []*big.Int 
    table = make([]*big.Int, N+1) 
    table[0] = new(big.Int).SetInt64(0) 
    table[1] = new(big.Int).SetInt64(1) 

    for i := uint(2); i <= N; i += 1 { 
     table[i] = new(big.Int).Add(table[i-1], table[i-2]) 
    } 

    return table[N] 
} 

func main() { 
    fmt.Println(fib(100)) 
}

將會產生

354224848179261915075

來源

2014-11-09 10:24:50

Golang斐波那契計算出現關閉

回答

相關問題