mcornell mcornell - 1 month ago 8
Swift Question

Fibonacci Calculator stack overflows at 93nd number in Swift

My Fibonacci Calculator seems to stack overflow really rapidly, always at the same number

class FiboCalculator {

private static let instance = FiboCalculator()
private var cache: [Int] = [1,1]
private init(){}

// get the nth fibo number
class func getZeroIndexed(n: Int) -> Int {
if n < 0 {
return 0
}
else if n < instance.cache.count {
return instance.cache[n]
}
while n >= instance.cache.count {
print("going down, right now i have \(instance.cache.count) values cached")
instance.cache.append( instance.cache[instance.cache.count-1] + instance.cache[instance.cache.count-2] )
}
return instance.cache[n]
}
}


I tried doing it recursively at first, but I got an EXC_BAD_INSTRUCTION every time when I tried to get the 91st value. Then I tried doing it the above way, iterative instead of recursive, and I get an EXC_BAD_INSTRUCTION every time I try and access the 93rd value. If I fill the cache up with 10 values from the start instead of 2, it still fails when trying to get the 93rd. If I split up the stack (resolve n/2 while cached count < n/2, then proceed) It still fails at 93. I'm also only testing this on a simulator. Am I missing something as to why this is failing?

Answer

The 93rd Fibonacci number is 12,200,160,415,121,876,738 which is more than 263 − 1, so it can't be represented as an Int anyway.

If you really want to support a number that big, you should use a BigInteger library.

Comments