swiftalgorithmfibonaccibottom-up

Runtime Error when Trying Bottom Up Approach to Implement Fibonacci function in Swift?


I am trying to implement a Fibonacci function in Swift 5. While I was implementing the function on Xcode Playground (I took the code for the function from CSDojo's youtube video), I was encountered with this error message

error: Execution was interrupted, reason: EXC_BAD_INSTRUCTION (code=EXC_I386_INVOP, subcode=0x0)

Initially, I thought the error must come from subscript index out of range. So I checked my code again and it seems there is no issue. Now I wonder why I get this error message from Xcode Playground when I try to run computeFiboBottomUp(n: 100)? It works fine until computeFiboBottomUp(n:35).

Is it because there are too many recursive calls on the stack for the compiler to process? Or does my code possibly contain an error?

func computeFiboBottomUp(n: Int) -> Int {
    var bottom_up: [Int?] = []
    if bottom_up.isEmpty {
        for _ in 0...n {
            bottom_up.append(nil)
        }
    }
    if n == 1 || n == 2 { return 1 }
    bottom_up[1] = 1
    bottom_up[2] = 1
    for i in 3...n {
        bottom_up[i] = bottom_up[i-1]! + bottom_up[i-2]!
    }
    return bottom_up[n]!
}

computeFiboBottomUp(n: 5)
computeFiboBottomUp(n: 35)
computeFiboBottomUp(n: 100) // error...

Solution

  • You have no recursion in your code.

    Note that Fib(35) is too small for integer overflow, but Fib(100) definitely is too large both for 32-bit and for 64-bit integers, so your compiler catches integer overflow error.

    You may set limit n=41 for 32-bit signed ints and n=92 for 64-bit signed ints.

    Higher values require using of long/arbitrary precision integer arithmetics.