Negative Fibonacci term F(50) with R package "Rcpp"

Question

I have used the example provided with R package "Rcpp" and obtained a negative 50-th Fibonacci term:

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

which made me curios to check the entire sequence up to F(50):

sapply(seq(50), fib)

It turned out that negative terms show up starting with F(47):

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

Any insight is welcome!

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

Looks like you are returning an `int`. You might want to check out the range of values that a signed integer value can take. — MrFlick, May 02 '17 at 19:16
Could you try changing to `long long`? See [here](http://stackoverflow.com/questions/1819189/what-range-of-values-can-integer-types-store-in-c). — David Robinson, May 02 '17 at 19:33
Trying "long long" ended in error. I changed to "float" and the result was F(50) = 12586267648, with no other term up to F(50) being negative — Dragos Bandur, May 02 '17 at 19:41
@DragosBandur You've lost precision at that point. The 50th number is the sequence is actually 12,586,269,025. R doesn't natively support unsigned 4-byte integers. `.Machine$integer.max` is as high as it goes — MrFlick, May 02 '17 at 19:55

score 2 · Answer 1 · edited Jun 20 '20 at 09:12

Like MrFlick commented, this probably has to do with the range of an int.

If we assumed this was a 32 bit integer, the maximum value that the integer can have is 2^31 - 1, or 2,147,483,647, with a minimum value of -2^31, and the 32nd bit is for the sign (positive or negative).

With the Fibonacci sequence, the first number that is greater than a 32 bit integer can handle is the 47th term, which should be 2,971,215,073, which is over the 2,147,483,647 maximum.

In hexadecimal, the 47th term would be 0xB11924E1, which interpreted as an integer has the sign bit set, and so get interpreted as a negative number, -1323752223.

An easy way to see this illustrated is using the Windows calculator in programmer mode, it can show you which bits are set for what number, and you can switch between Qword (64 bits) and Dword (32 bits) to see the limitations of 32 bits.

See this link for expected Fibonacci values

See my last comment above – Dragos Bandur May 02 '17 at 19:53 — Dragos Bandur, May 02 '17 at 19:53

score 0 · Answer 2 · answered May 02 '17 at 19:28

Looks like you're exceeding the maximum value for C++ integers, which is 2147483647. Here's a more efficient implementation written in R itself that uses a loop rather than a recursive structure. This avoids growing a vector as well.

fibo <- function(x) {

    if (x == 0) {
        return(0)
    } else if (x %in% 1:2) {
        return(1)
    }

    the.seq <- rep(NA, x)
    the.seq[1:2] <- 1
    for (i in 3:x) {
        the.seq[i] <- the.seq[i - 1] + the.seq[i - 2]
    }

    return(the.seq[x])
}

I was trying to avoid iteration. I have caught this while trying to benchmark three recursions, using R, R+Rcpp and compiled R recursion (with compf()). It seems that using "float" helped. — Dragos Bandur, May 02 '17 at 20:00

Negative Fibonacci term F(50) with R package "Rcpp"

2 Answers2