Assignment Factorial Function

The objective of Part 1 is to write a function that computes the factorial of an integer greater than or equal to 0. Recall that the factorial of a number n is n * (n-1) * (n - 2) * . * 1. The factorial of 0 is defined to be 1. Before taking on this part of the assignment, you may want to review the section on Functional Programming in this course (you can also read that section here).

For this Part you will need to write four different versions of the Factorial function:

  1. Factorial_loop: a version that computes the factorial of an integer using looping (such as a for loop)
  2. Factorial_reduce: a version that computes the factorial using the reduce() function in the purrr package. Alternatively, you can use the Reduce() function in the base package.
  3. Factorial_func: a version that uses recursion to compute the factorial.
  4. Factorial_mem: a version that uses memoization to compute the factorial.
    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.

In order to submit this assignment, please prepare two files:

  1. factorial_code.R: an R script file that contains the code implementing your classes, methods, and generics for the longitudinal dataset.
  2. factorial_output.txt: a text file that contains the results of your comparison of the four different implementations.

Approach 1: Factorial loop

The facturial loop is a loop that repeats itself n times where the loop is repeated n times and he result after each loop occurance is the result of multiplying with n.

Factorial_loop <- function (x) {
        result <- 1
        if (x == 0) return(1)
        for (i in 1:x) {
                result <- result * i
                }
        return(result)
}  

occurance <- 100
resultaat <- Factorial_loop(occurance)
cat ("The result is:", resultaat)
## The result is: 9.332622e+157

Approach 2: Factorial reduce

The facturial reduce function is implemented. There was a problem with integer size above x is 15. This was solved with transforming the integers to numeric.

Factorial_reduce <- function (x){
        if (x == 0) return(1)
        result <- reduce(as.numeric(1:x), `*`)
        return(result)
}

resultaat <- Factorial_reduce(100)
cat ("The result is:", resultaat)
## The result is: 9.332622e+157

Approach 3: Factorial function

This is the implementation with the function that calls itself with the argument x - 1. When x = 0 the result of 1 is returned.

Factorial_funct <- function (x) {
        if (x == 0) return(1)
        result <- x * Factorial_funct(x-1)
        return(result)
}

resultaat <- Factorial_funct(occurance)
cat ("The result is:", resultaat)
## The result is: 9.332622e+157

Approach 4: Memoization

This is the implementation of the Memoization approach. The results are placed in the tabel fact_tabel. This is a tabel with length of x and initial value NA.

Factorial_mem <- function(x) {
        if (x == 0) {
                return(1)
        } 
        fact_tabel[x] <<- x * Factorial_mem(x-1)
        return(fact_tabel[x])
}

fact_tabel <- c(rep(NA, occurance))
resultaat <- Factorial_mem(occurance)
cat ("The result is:", resultaat)
## The result is: 9.332622e+157

Comparison

In this part the comparison is made between the four different implementations with the microbenchmark package.

benchmark <- function (occurance) {
        microbenchmark(
                resultaat <- Factorial_loop(occurance),

                resultaat <- Factorial_reduce(occurance),

                resultaat <- Factorial_funct(occurance),

                resultaat <- Factorial_mem(occurance)
        )
}

Comparison factorial of 10

fact_tabel <- c(rep(NA, 10))
benchmark(10)
## Unit: nanoseconds
##                                      expr    min       lq       mean
##    resultaat <- Factorial_loop(occurance)      1    790.0    1342.72
##  resultaat <- Factorial_reduce(occurance) 132639 136586.0 1013404.94
##   resultaat <- Factorial_funct(occurance)   5527   6317.0    7303.51
##     resultaat <- Factorial_mem(occurance)   7106   7895.5    9324.66
##  median       uq      max neval
##     790   1580.0    10264   100
##  141324 145271.0 84368255   100
##    6317   7106.0    37897   100
##    8685   8685.5    38686   100

Comparison factorial of 100

fact_tabel <- c(rep(NA, 100))
benchmark(100)
## Unit: microseconds
##                                      expr     min       lq      mean
##    resultaat <- Factorial_loop(occurance)   5.527   6.3170   7.77724
##  resultaat <- Factorial_reduce(occurance) 261.329 271.5940 303.28444
##   resultaat <- Factorial_funct(occurance)  83.689  89.2160 104.44535
##     resultaat <- Factorial_mem(occurance)  94.742 100.6635 109.24552
##    median       uq     max neval
##    7.1065   7.8960  21.317   100
##  286.9885 311.8585 476.077   100
##   92.3730  96.3210 355.282   100
##  104.6110 108.5585 212.379   100

Comparison factorial of 1000

fact_tabel <- c(rep(NA, 1000))
benchmark(1000)
## Unit: microseconds
##                                      expr      min       lq       mean
##    resultaat <- Factorial_loop(occurance)   47.371   52.108   57.20871
##  resultaat <- Factorial_reduce(occurance)  947.417 1072.950 1287.49251
##   resultaat <- Factorial_funct(occurance)  930.048 1042.948 1313.86226
##     resultaat <- Factorial_mem(occurance) 1061.107 1182.693 1433.10267
##    median        uq      max neval
##    54.477   58.8195  176.852   100
##  1194.929 1337.0425 2786.195   100
##  1257.696 1419.1520 2608.555   100
##  1301.909 1487.8395 5360.800   100