fibonacci algorithms in swift

fibonacci.swift

// https://medium.com/swlh/fibonacci-swift-playground-f56d1ff3ea99
// recursive approach
// time: O(n^2)
// space: O(n^2)
func fib1(_ n: Int) -> Int {
    guard n > 2 else { return n }
    return fib(n-1) + fib(n-2)
}

////////////////////////////////////////////////
// Iterative approach
// time: O(n)
// space: O(n)
func fib2(_ n: Int) -> Int {
    var fibs: [Int] = [0, 1]
    (2...n).forEach { i in fibs.append(fibs[i - 1] + fibs[i - 2]) }
    return fibs.last!
}

////////////////////////////////////////////////
// Iterative approach -- Space optimized
// time: O(n)
// space: O(1)
func fib3(_ n: Int) -> Int {
    var a = 1
    var b = 1
    guard n > 1 else { return a }

    (2...n).forEach { _ in (a, b) = (a + b, a) }
    return a
}

////////////////////////////////////////////////
// Matrix approach
// time: O(n)
// space: O(1)
func fib4(_ n: Int) -> Int {
    let M = [[1, 1], [1, 0]]
    guard n > 2 else { return n }

    var result: [[Int]] = M
    (1..<n).forEach { _ in result = multiply(result, M) }
    return result[0][0]
}

////////////////////////////////////////////////
// Matrix approach -- Optimized
// time: O(log n)
// space: O(log n)
func fib5(_ n: Int) -> Int {
    var M = [[1, 1], [1, 0]]
    guard n > 2 else { return n }
    
    power(&M, n)
    return M[0][0]
}

func power(_ matrix: inout [[Int]], _ n: Int) {
    guard n > 1 else { return }
    
    power(&matrix, n/2)
    matrix = multiply(matrix, matrix)
    
    if n % 2 != 0 {
        let M = [[1, 1], [1, 0]]
        multiply(matrix, M)
    }
}