c++ - 负斐波那契项 F(50) 与 R 包 "Rcpp"

Question

我使用了 R 包“Rcpp”提供的示例并获得了负的第 50 斐波那契项:

fib <- Rcpp::cppFunction(
  'int fibonacci(const int x) {
      if (x == 0) return(0); 
      if (x == 1) return(1);
      return (fibonacci(x - 1)) + fibonacci(x - 2);
  }')

fib(50)
# [1] -298632863

这让我好奇地检查了直到 F(50) 的整个序列:

sapply(seq(50), fib)

事实证明，否定词以 F(47) 开头出现:

[1]   1  1  2  3  5  8  13  21  34
.
.
[10]  55  89 144 . . .
.
.
[46]  1836311903 -1323752223   512559680  -811192543  -298632863

欢迎任何见解!

sessionInfo()
R version 3.4.0 (2017-04-21)
Platform: x86_64-w64-mingw32/x64 (64-bit)
Running under: Windows 10 x64 (build 14393)

Matrix products: default

locale:
[1] LC_COLLATE=English_United States.1252  LC_CTYPE=English_United States.1252   
[3] LC_MONETARY=English_United States.1252 LC_NUMERIC=C                          
[5] LC_TIME=English_United States.1252    

attached base packages:
[1] stats     graphics  grDevices utils     datasets  methods   base     

loaded via a namespace (and not attached):
[1] compiler_3.4.0 tools_3.4.0    inline_0.3.14  Rcpp_0.12.10  

Answer 1

就像 MrFlick 评论的那样，这可能与 int 的范围有关。

如果我们假设这是一个 32 位整数，则该整数的最大值为 2^31 - 1，即 2,147,483,647，最小值为 -2^31，第 32 位用于符号 (正面或负面)。

对于斐波那契数列，第一个大于 32 位整数可以处理的数字是第 47 项，它应该是 2,971,215,073，超过了最大值 2,147,483,647。

在十六进制中，第 47 项将是 0xB11924E1，它被解释为设置了符号位的整数，因此被解释为负数，-1323752223。

查看此插图的一种简单方法是在程序员模式下使用 Windows 计算器，它可以显示哪些位设置为哪些数字，您可以在 Qword(64 位)和 Dword(32 位)之间切换以查看32 位的限制。

See this link for expected Fibonacci values