CODEWITHSUNDEEP
swiftunsigned-integer
Abhishek Thapliyal
Abhishek Thapliyal

Reputation: 3708

UIint64 data overflow issue

I was solving a problem:

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.

and below is my solution:

class FB {
  static func run() {
    var a: UInt64 = 0
    var b: UInt64 = 1

    var c: UInt64 = 0

    var sum: UInt64 = 0

    for _ in 0..<4_000_000 {
      print(c)
      c = a + b // CRASHES
      if c % 2 == 0 {
        sum += c
      }

      a = b
      b = c
    }

    print("SUM: , \(sum)")
  }
}

But it crashes as mentioned in comment Thread 1: EXC_BAD_INSTRUCTION (code=EXC_I386_INVOP, subcode=0x0)

What data type should I use in order to avoid overflow for c variable?

Upvotes: 0

Views: 121

Answers (2)

Alexander
Alexander

Reputation: 63271

While Vadian's solution will fix your code as-is, I thought I would share how I would solve this, which uses a more functional approach.

fibSequence just returns an infinite sequence of Int. I call that function to make one such infinite sequence, I take its elements until they reach 4_000_000 (which is what prefix(while:) is doing), filter to get only those which are even, and then sum them using reduce, by starting with an accumulator of 0, and combining all element by addition (+).

There are several benefits to this approach, but the main one is that it properly separates various concerns into small modular pieces.

  • fibSequence() concerns itself only with fib sequences, and don't know anything about the specifics of your problem.
  • sumEvenFibs(upTo:) only concerns itself with filtering and summing according to your problems criteria, and returning the sum, without knowing anything about fib sequences or printing results.
  • The printing happens seperately, after the sum was cumputed by calling sumEvenFibs(upTo:). This allows you to easily change what you do with the result. Rather than printing it, you might want to do some other computation with it, e.g. comparing it against the sum obtained by odd fib numbers, to see which is greater.
func fibSequence() -> UnfoldSequence<Int, (Int, Int)> {
    return sequence(state: (0, 1), next: { (state) -> Int in
            state = (state.1, state.0 + state.1)
            return state.0
        })
}

func sumEvenFibs(upTo limit: Int) -> Int {      
    return fibSequence()
        .prefix(while: { $0 < limit })
        .filter { $0.isMultiple(of: 2) }
        .reduce(0, +)
}


let sum = sumEvenFibs(upTo: 4_000_000)
print("SUM: \(sum)")

Upvotes: 4

vadian
vadian

Reputation: 285082

.. whose values do not exceed four million

means that c must not be greater than 4 million.

Replace

for _ in 0..<4000000 {

with

while c < 4000000 {

Now the numeric type can even be UInt32 😉

Upvotes: 3

Related Questions