Fibonacci Calculator Stack Overflows at 93Nd Number in Swift

Fibonacci Calculator stack overflows at 93nd number in Swift

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.

Fibonacci in swift playground

The issue is that Int can only store 64bit numbers (on 64bit platforms) and Fibonacci 95 is bigger than the maximum number that can be stored on 64bits.

Fibonacci 95 is 31 940 434 634 990 099 905, while the biggest number Int64 can hold is 2^63-1 = 9 223 372 036 854 775 807.

You can use Decimal for storing larger numbers than what Int can hold Decimal.greatestFiniteMagnitude is 3.4028236692093865e+165.

However, Swift doesn't have a built-in type for storing arbitrarily large numbers, so if you want to do that you'll either need to use a 3rd party library or implement an appropriate data type yourself.

using for loop for fibonacci series to print values it will print up to 47 values above that it shows error

Fib(47) is 2,971,215,073.

2,971,215,073 is larger than 2³¹ - 1 ... which is the largest 32 bit signed integer.

Hence your calculation is overflowing. (In a lot of programming languages, you wouldn't have gotten an error. You would have just gotten the wrong answer.)

How i find the fibonacci series for number 100.

You can't use simple integer arithmetic. You will need to use the Swift equivalent of Java's BigInteger class.

• BigInteger equivalent in Swift?

Swift illegal hardware instruction in while loop

Your algorithm is right, but the problem is that Swift 64 bit integers can only hold values up to 9,223,372,036,854,775,807, i.e. 9.22e+18. Unsigned integers can be twice as large, but still nowhere close to 1,000 digits. Decimal/NSDecimalNumber gets you up to 38 digits, which still is not sufficient.

You probably want to create/use a library that can represent arbitrarily large integers. Just search the interwebs for "swift arbitrarily large integer" or "swift biginteger".

Then your routine will correctly calculate the result.

Finding out nth fibonacci number for very large 'n'

You can use the matrix exponentiation method (linear recurrence method).
You can find detailed explanation and procedure in this or this blog. Run time is O(log n).

I don't think there is a better way of doing this.

Number at f(93) in fibonacci series has negative value, how?

You've encountered an integer overflow:

 4660046610375530309 <-- term 91
+7540113804746346429 <-- term 92
====================
12200160415121876738 <-- term 93: the sum of the previous two terms
 9223372036854775808 <-- maximum value a long can store

To avoid this, use BigInteger, which can deal with an arbitrary number of digits.

Here's your implementation converted to use BigDecimal:

public String fibo(int x){
    BigInteger[] arr = new BigInteger[x+1];
    arr[0]=BigInteger.ZERO;
    arr[1]=BigInteger.ONE;
    for (int i=2; i<=x; i++){
        arr[i]=arr[i-2].add(arr[i-1]);
    }
    return arr[x].toString();u
}

Note that the return type must be String (or BigInteger) because even the modest value of 93 for x produces a result that is too great for any java primitive to represent.

---

Related Topics