英文:
Golang Fibonacci calculation appears off
问题
我目前有以下代码用于斐波那契数列的计算。我试图计算较大的数字，但是一旦达到100，计算结果就不正确了。对于fib(100)，我的代码返回的是3736710778780434371，但是当我查看其他来源时，告诉我正确的计算结果应该是354224848179261915075。我的代码有问题还是与我的计算机硬件或其他因素有关？
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))
}
你的代码在计算fib(100)时返回的结果是正确的，即3736710778780434371。斐波那契数列的计算是递归的，对于较大的数字，计算量会非常大，可能会超出计算机的处理能力。因此，当计算较大的斐波那契数时，可能会出现精度问题。你可以尝试使用其他算法或库来处理更大的斐波那契数。
英文:
I currently have the following codes for my fibonacci calculations. I'm trying to calculate large numbers, but it appears once it gets to 100, the calculations are off. For fib(100), my code returns 3736710778780434371, but when I look at other sources, it tells me the correct calculation should be 354224848179261915075. Is there a problem in my code or does it have to do with my computer hardware or something else?
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))
}
答案1
得分: 10
你遇到了整数溢出问题！你只能使用uint进行计算，其大小最多为uint的大小；一旦超出其范围，它将（静默地）重新回到起点。
在你的情况下，看起来uint的长度为64位。（它的大小取决于你运行的平台。）这意味着你可以存储的值最大为2的64次方减1。如果你再加上一个值，它将回到0，而不会返回错误。
如果你将你得到的答案和正确答案转换为十六进制，你会发现情况就是这样的。你得到的结果是
33DB76A7C594BFC3
而正确答案是
1333DB76A7C594BFC3
请注意，你的答案在一定程度上是正确的...只是不够完整。你只得到了答案的低64位；你缺少了另外13*2的64次方。
要纠正这个问题，你需要使用big包中的任意大小整数，而不是uint。
英文:
You're hitting an integer overflow! You can only calculate using a uint up to the size of a uint; once you go beyond its bounds, it will (silently) wrap back round again.
In your case, it looks as though a uint is 64 bits long. (Its size depends on the platform you're running on.) That means that you will be able to store values up to 2<sup>64</sup>-1. If you then add one more, it'll wrap back to 0, and won't return an error.
If you convert the answer you're getting, and the right answer, into hex, then you'll see that this is the case. You're ending up with
33DB76A7C594BFC3
whereas the right answer is
1333DB76A7C594BFC3
Note that your answer is correct as far as it goes... it just doesn't go far enough. You've only got the lower 64 bits of the answer; you're missing the other 13*2<sup>64</sup>.
To correct it, you'll need to use an arbitrary size integer from Package big, instead of a uint.
答案2
得分: 3
这是使用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
英文:
Here is a version using big.Int which produces the correct answer (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))
}
Which produces
354224848179261915075
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论