Factorial Code

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

library(purrr)
library(microbenchmark)
library(ggplot2)

Factorial_loop: a version that computes the factorial of an integer using looping (such as a for loop)

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

Factorial_loop(10)

## [1] 3628800

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.

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

Factorial_reduce(10)

## [1] 3628800

Factorial_func: a version that uses recursion to compute the factorial.

Factorial_func <- function(x){
    if (x == 0)
        return (1)
    factorial = x * Factorial_func(x-1)
    return(factorial)
}

Factorial_func(10)

## [1] 3628800

Factorial_mem: a version that uses memoization to compute the factorial.

Factorial_tbl <- c(0, 1, rep(NA, 1000))
Factorial_mem  <- function(x){
    if (x == 0)
    return(1)
    
    if(!is.na(Factorial_tbl[x]))
        return(Factorial_tbl[x])
    Factorial_tbl[x] <<- x * Factorial_mem(x - 1)
    Factorial_tbl[x]
}

Factorial_mem(10)

## [1] 1814400

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.

Performance1 <- microbenchmark(a <- 10,
                        b <- Factorial_mem(10),
                        c <- Factorial_reduce(10),
                        d <- Factorial_func(10),
                        e <- Factorial_mem (10))
Performance1

## Unit: nanoseconds
##                       expr   min    lq      mean median      uq     max neval
##                    a <- 10     0     0     19.68      0    41.0     246   100
##     b <- Factorial_mem(10)   410   451    603.93    533   656.0    5207   100
##  c <- Factorial_reduce(10) 85567 86182 107269.53  86510 87186.5 2027532   100
##    d <- Factorial_func(10)  3813  3936   4085.65   4018  4141.0    7011   100
##     e <- Factorial_mem(10)   410   451    571.54    492   656.0    2173   100

autoplot(Performance1)

Performance2 <- microbenchmark(a <- 100,
                               b <- Factorial_mem(100),
                               c <- Factorial_reduce(100),
                               d <- Factorial_func(100),
                               e <- Factorial_mem (100))
Performance2

## Unit: nanoseconds
##                        expr    min     lq      mean median       uq    max
##                    a <- 100      0      0     14.76      0     41.0    164
##     b <- Factorial_mem(100)    451    492   1273.87    574    697.0  64780
##  c <- Factorial_reduce(100) 257562 260637 269396.24 263425 271358.5 387573
##    d <- Factorial_func(100)  38950  40057  41637.14  40713  42578.5  49856
##     e <- Factorial_mem(100)    410    492    639.60    615    738.0   2788
##  neval
##    100
##    100
##    100
##    100
##    100

autoplot(Performance2)

Performance3 <- microbenchmark(a <- 1000,
                               b <- Factorial_mem(1000),
                               c <- Factorial_reduce(1000),
                               d <- Factorial_func(1000),
                               e <- Factorial_mem (1000))
Performance3

## Unit: nanoseconds
##                         expr     min        lq       mean    median        uq
##                    a <- 1000       0       0.0      33.21       0.0      41.0
##     b <- Factorial_mem(1000)     451     533.0    6802.31     656.0     799.5
##  c <- Factorial_reduce(1000) 1944548 1960066.5 2084563.00 1977327.5 2058200.0
##    d <- Factorial_func(1000)  395240  397884.5  418225.01  401861.5  440114.5
##     e <- Factorial_mem(1000)     410     533.0     747.43     697.0     861.0
##      max neval
##      533   100
##   611351   100
##  3882003   100
##   637960   100
##     2706   100

autoplot(Performance3)