Простой сбой программы Swift Фибоначчи (Project Euler 2)

Question

Я пытаюсь решить вторую проблему на Project Euler. Проблема заключается в следующем:

---

Каждый новый член в последовательности Фибоначчи генерируется путем добавления двух предыдущих членов. Начиная с 1 и 2, первые 10 слагаемых будут: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... Рассматривая слагаемые в последовательности Фибоначчи, значения которых не превышают четыре миллиона, найти сумму четных членов.

---

Я думаю, что написал решение, но когда я пытаюсь запустить мой код, он ломает мою игровую площадку Swift и выдает мне следующее сообщение об ошибке:

Выполнение на детской площадке прервано: выполнение было прервано, причина: EXC_BAD_INSTRUCTION (код =EXC_I386_INVOP, субкод =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)

---

Странная вещь, если я установлю счетчик на моем цикле меньше 93, он будет работать нормально. Явное задание двойных имен переменных не помогает. Кто-нибудь знает, что здесь происходит?

Answer 1

В этом нет ничего странного. Вы знаете, насколько велико число 400 Фибоначчи?

176023680645013966468226945392411250770384383304492191886725992896575345044216019675

стриж Int64 или же UInt64 просто не может справиться с таким большим числом. Чем позже можно подняться на 18446744073709551615 на максимуме - даже не близко.

Если вы измените ваши переменные на двойные, это сработает, но будет неточным:

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

даст

2.84812298108489e+83

что-то вроде близко к фактической стоимости

1.76e+83

К счастью, вам не нужно получать такие большие значения. Я бы рекомендовал не писать цикл for, а цикл while, который вычисляет следующее число Фибоначчи, пока не будет выполнено условие разрыва , значения которого не превышают четырех миллионов.

Answer 2

Числа Фибоначчи быстро становятся очень большими. Чтобы вычислить большие числа Фибоначчи, вам нужно реализовать BigNum, Вот версия, которая делает BigNum это реализовано внутри как массив цифр. Например, 12345 реализуется внутренне как [1, 2, 3, 4, 5], Это позволяет легко представлять произвольно большие числа.

Добавление осуществляется путем создания двух массивов одинакового размера, а затем map используется для добавления элементов, наконец, carryAll функция восстанавливает массив до одной цифры.

Например 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

Вот реализация BigNum, Это также CustomStringConvertible что позволяет напечатать результат в виде 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://stackru.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)

Выход:

1
2
3
5
8
...
67235063181538321178464953103361505925388677826679492786974790147181418684399715449
108788617463475645289761992289049744844995705477812699099751202749393926359816304226
176023680645013966468226945392411250770384383304492191886725992896575345044216019675