斐波納契計算器堆棧溢出在斯威夫特

Question

93nd數

我的斐波那契計算器似乎在相同數量的

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] 
    } 
} 

我試圖遞歸地做它的第一個堆棧溢出真神速，總是，但我當每次有一個EXC_BAD_INSTRUCTION我試圖獲得第91個值。然後，我嘗試按照上述方式進行，迭代而不是遞歸，並且每次嘗試訪問第93個值時都會得到一個EXC_BAD_INSTRUCTION。如果我從開始而不是從2開始填充10個值，它在嘗試獲得第93個時仍然失敗。如果我拆分堆棧（解決n/2而緩存計數< n/2，然後繼續）它仍然失敗在93.我也只在模擬器上測試。我錯過了爲什麼這是失敗的東西？

Answer 1

第93 Fibonacci數是12,200,160,415,121,876,738這超過2 − 1，因此它不能被表示爲Int反正。

如果你真的想支持一個很大的數字，你應該使用BigInteger library。

Answer 2

你四溢Int數據類型，因爲FIB（93）的結果（12,200,160,415,121,876,738，大致1.22 x 10^19）大於Int64.max（9,223,372,036,854,775,807，大約9.22 x 10^18）。因爲Int是32位機器上的32位類型，所以在32位機器上，這將在更早的時間崩潰，在fib（47）（2,971,215,073）處。 Int32.max只是2,147,483,647。