CODEWITHSUNDEEP
c++r
Dragos Bandur
Dragos Bandur

Reputation: 301

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

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

Upvotes: 0

Views: 129

Answers (2)

A. Blodgett
A. Blodgett

Reputation: 136

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

Upvotes: 2

jdobres
jdobres

Reputation: 11957

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

Upvotes: 0

Related Questions