2

I was just trying to check the execution speed of Fiboncci number generation in R vs Rcpp. To my surprise, my R function was faster(also, linearly growing) than my Rcpp function. What is wrong here.

The R code:

fibo = function (n){
    x = rep(0, n)
    x[1] = 1
    x[2] = 2

    for(i in 3:n){
        x[i] = x[i-2] + x[i-1]
    }
    return(x)
}

The Rcpp code:

#include <Rcpp.h>

using namespace Rcpp;
// [[Rcpp::export]]
IntegerVector fibo_sam(int n){
    IntegerVector x;
    x.push_back(1);
    x.push_back(2);
    for(int i =2; i < n; i++){
        x.push_back(x[i - 2] + x[i-1]);
    }
    return(x);
}
alistaire
  • 42,459
  • 4
  • 77
  • 117
Madhuresh
  • 49
  • 5
  • Binet's formula is a nice approach: `fibonacci <- function(n, u0 = 0, u1 = 1){ phi <- (1 + sqrt(5)) / 2; psi <- 1 - phi; a <- (u1 - u0 * psi) / sqrt(5); b <- (u0 * phi - u1) / sqrt(5); a * phi^n + b * psi^n }` – alistaire Jan 08 '18 at 08:47

1 Answers1

9

The problem with your Rcpp code is that you are growing the vector instead of allocating the size at the beginning. Try with:

// [[Rcpp::export]]
IntegerVector fibo_sam2(int n) {
  IntegerVector x(n);
  x[0] = 1;
  x[1] = 2;
  for (int i = 2; i < n; i++){
    x[i] = x[i-2] + x[i-1];
  }
  return(x);
}

Benchmark:

Unit: microseconds
            expr     min       lq      mean  median       uq      max neval cld
      fibo(1000)  99.989 102.6375 157.42543 103.962 106.9415 4806.395   100  a 
  fibo_sam(1000) 493.320 511.8615 801.39046 534.044 590.4945 2825.168   100   b
 fibo_sam2(1000)   2.980   3.3110  10.18763   3.642   4.3040  573.443   100  a

PS1: check your first values

PS2: beware large numbers (see this)

F. Privé
  • 11,423
  • 2
  • 27
  • 78