Fibonacci Calculator stack overflows at 93nd number in Swift

Question

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?

score 2 · Accepted Answer · edited May 23 '17 at 12:33

2

The 93rd Fibonacci number is 12,200,160,415,121,876,738 which is more than 2⁶³ − 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.

edited May 23 '17 at 12:33

Community

1
1

answered Oct 31 '16 at 15:21

kennytm

510,854
105
1,084
1,005

1

You can use the apparently little-known built-in `NSDecimalNumber`, too – vadian Oct 31 '16 at 15:33
@vadian NSDecimalNumber (called `Decimal` in Swift 3) is like `float` or `double`, while it will allow you to calculate up to 10^165 (F_791), the least significant digits will be lost. – kennytm Oct 31 '16 at 15:36
That's fib(792) which is at least *that big* ;-) – vadian Oct 31 '16 at 15:42

score 1 · Answer 2 · answered Oct 31 '16 at 15:21

You're overflowing the Int datatype, because the result of fib(93) (12,200,160,415,121,876,738, roughly 1.22 x 10^19) is larger than Int64.max (9,223,372,036,854,775,807, or roughly 9.22 x 10^18).

On 32 bit machines, this will crash even earlier, at fib(47) (2,971,215,073), because Int is a 32 bit type on 32 bit machines. Int32.max is only 2,147,483,647.

Fibonacci Calculator stack overflows at 93nd number in Swift

2 Answers2

Linked

Related