Simple Swift Fibonacci program crashing (Project Euler 2)

Question

I am trying to solve the second problem on Project Euler. The problem is as follows:

---

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

---

I think I've written a solution, but when I try to run my code it crashes my Swift playground and gives me this error message:

Playground execution aborted: Execution was interrupted, reason: EXC_BAD_INSTRUCTION (code=EXC_I386_INVOP, subcode=0x0)

---

var prev = 0
var next = 1
var num = 0
var sum = 0

for var i = 1; i < 400; i++ {
    num = prev + next
    if next % 2 == 0 {
        sum += next
    }
    prev = next
    next = num
}
print(sum)

---

The weird thing is, if I set the counter on my loop to less than 93, it works fine. Explicitly setting the variable names to Double does not help. Anyone know what's going on here?

Answer 1

There is nothing weird about this at all. Do you know how large the 400 fibonacci number is?

176023680645013966468226945392411250770384383304492191886725992896575345044216019675

Swift Int64 or UInt64 simply cannot handle that large of a number. The later can go up to 18446744073709551615 at max - not even close.

If you change your variables to be doubles it works but will be inaccurate:

var prev : Double = 0
var next : Double = 1
var num : Double = 0
var sum : Double = 0

will yield

2.84812298108489e+83

which is kind of close to the actual value of

1.76e+83

Luckily you do not need to get values that big. I would recommend not writing a for loop but a while loop that calculates the next fibonacci number until the break condition is met whose values do not exceed four million.

Answer 2

The Fibonacci numbers become very large quickly. To compute large Fibonacci numbers, you need to implement some kind of BigNum. Here is a version the makes a BigNum that is implemented internally as an array of digits. For example, 12345 is implemented internally as [1, 2, 3, 4, 5]. This makes it easy to represent arbitrarily large numbers.

Addition is implemented by making the two arrays the same size, then map is used to add the elements, finally the carryAll function restores the array to single digits.

For example 12345 + 67:

[1, 2, 3, 4, 5] + [6, 7]            // numbers represented as arrays
[1, 2, 3, 4, 5] + [0, 0, 0, 6, 7]   // pad the shorter array with 0's
[1, 2, 3, 10, 12]                   // add the arrays element-wise
[1, 2, 4, 1, 2]                     // perform carry operation

Here is the implementation of BigNum. It is also CustomStringConvertible which makes it possible to print the result as a String.

struct BigNum: CustomStringConvertible {
    var arr = [Int]()

    // Return BigNum value as a String so it can be printed
    var description: String { return arr.map(String.init).joined() }

    init(_ arr: [Int]) {
        self.arr = carryAll(arr)
    }

    // Allow BigNum to be initialized with an `Int`
    init(_ i: Int = 0) {
        self.init([i])
    }

    // Perform the carry operation to restore the array to single
    // digits
    func carryAll(_ arr: [Int]) -> [Int] {
        var result = [Int]()

        var carry = 0
        for val in arr.reversed() {
            let total = val + carry
            let digit = total % 10
            carry = total / 10
            result.append(digit)
        }

        while carry > 0 {
            let digit = carry % 10
            carry = carry / 10
            result.append(digit)
        }

        return result.reversed()
    }

    // Enable two BigNums to be added with +
    static func +(_ lhs: BigNum, _ rhs: BigNum) -> BigNum {
        var arr1 = lhs.arr
        var arr2 = rhs.arr

        let diff = arr1.count - arr2.count

        // Pad the arrays to the same length
        if diff < 0 {
            arr1 = Array(repeating: 0, count: -diff) + arr1
        } else if diff > 0 {
            arr2 = Array(repeating: 0, count: diff) + arr2
        }

        return BigNum(zip(arr1, arr2).map { $0 + $1 })
    }
}

// This function is based upon this question:
// https://stackoverflow.com/q/52975875/1630618

func fibonacci(to n: Int) {
    guard n >= 2 else { return }
    var array = [BigNum(0), BigNum(1)]
    for i in 2...n {
        array.append(BigNum())
        array[i] = array[i - 1] + array[i - 2]
        print(array[i])
    }
}

fibonacci(to: 400)

Output:

1
2
3
5
8
...
67235063181538321178464953103361505925388677826679492786974790147181418684399715449
108788617463475645289761992289049744844995705477812699099751202749393926359816304226
176023680645013966468226945392411250770384383304492191886725992896575345044216019675