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...
CodePudding user response:
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.