Factorial Function with four techniques

overview

After writing your four versions of the Factorial function, use the microbenchmark package to time the operation of these functions and provide a summary of their performance. In addition to timing your functions for specific inputs, make sure to show a range of inputs in order to demonstrate the timing of each function for larger inputs.

1. Factorial_loop: Computes the factorial of an integer using looping.

fac_loop <- function(n){
  stopifnot(n>=0)
  if (n == 0){
    return(1)
  }
  else {
    res <- 1
    for (i in 1:n){
      res <- res * i
    }
    return(res)
  }
}

fac_loop(4)

[1] 24

2. Factorial_reduce: Computes the factorial using the reduce().

fac_Reduce <- function(n){
  stopifnot(n>=0)
  # because factoriel(0)=1, it's important to make condition
  if (n==0){
    return(1)
  }
  else {
    reduce(1:n, function(x,y){
      x*y
    })
  }
}

fac_Reduce(4)

[1] 24

3. Factorial_func: Uses recursion to compute the factorial.

fac_Recursion <- function(n){
  stopifnot(n>=0)
  if (n==0){
    return(1)
  }
  else {
    return(n*fac_Recursion(n-1))
  }
}

fac_Recursion(4)

[1] 24

4. Factorial_mem: Uses memorization to compute the factorial.

fac_table <- c(1)
fac_Mem <- function(n){
  # Because factorial of negatif number does not exist we stop if n<0
  stopifnot(n>=0)
  if (n==0){
    return(1)
  }
  else {
    if (!is.na(fac_table[n])){
      return(fac_table[n])
    } else {
      fac_table[n-1] <<- fac_Mem(n-1)
      return(n*fac_table[n-1])
    }
  }
  
}

fac_Mem(4)

[1] 24

5. use the microbenchmark package:

to time the operation of these functions and provide a summary of their performance.In addition to timing your functions for specific inputs, make sure to show a range of inputs in order to demonstrate the timing of each function for larger inputs.

the function below “compare_time” is intuitive. Given n it print a dataframe where we can see the summary of 100 time of computing of facotrial(n) using the 4 differents technique. And by looking the result we can get insight about the time consuming of differents techniques.

compare_time <- function(n){
  as.data.frame(summary(microbenchmark(fac_loop(n), 
                                       fac_Mem(n),
                                       fac_Recursion(n),
                                       fac_Reduce(n))))
}

range_time() function below takes a given factorial function and a range of integer (n_min:n_max), then computes the median times of 100 computing of each integer with the given factorial function.

range_time <- function(f, n_min = 1, n_max = 10){
  df_func <- map(seq(n_min, n_max), function(x){microbenchmark(f(x))$time})
  names(df_func) <- paste0("X",".", n_min:n_max)
  df_func <- as.data.frame(df_func)
  df_func %<>%
    gather(num, time) %>%
    group_by(num) %>%
    summarise(med_time = median(time))
  return(df_func)
}

range_time(fac_loop, 1, 5)

data4 function() below combines the results of range_time for the 4 techniques

data4 <- function(n_min, n_max){
  data_loop <- range_time(fac_loop, n_min, n_max)[,2]
  data_Mem <- range_time(fac_Mem, n_min, n_max)[,2]
  data_Reduce <- range_time(fac_Reduce, n_min, n_max)[,2]
  data_Recursion <- range_time(fac_Recursion, n_min, n_max)[,2]
  data <- cbind(data_loop, data_Mem, data_Reduce, data_Recursion)
  names(data) <- c("Median_Loop_Time", "Median_Mem_Time", "Median_Redu_Time", "Median_Recu_Time")
  data$n <- n_min:n_max
  return(data)
}

data4(1,5)

Plot to take a look of the difference between the 4 techniques

plotTimeComparison <- function(n_min, n_max){
  df <- data4(n_min, n_max)
  df <- melt(df, id.vars = "n")
  df$n <- as.numeric(df$n)
  p <- ggplot(data = df, aes(x=n, y=value, colour = variable)) + geom_line()
  show(p)
  #return(df)
  }

plotTimeComparison(1,10)

#plotTimeComparison(10, 20)