Project Euler #2 (Even Fibonacci numbers) in Swift

Question

I figured working through Project Euler problems in Swift would be a good way to learn any tips or tricks. For example, tuples are something I'm not used to using, but they proved useful here. Using things makes me more confident with them, so perhaps this will help me find other uses for them in the future.

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.

Here is my solution:

func swap(inout left: Any, inout right: Any) {
 let swap = left
 right = left
 left = swap
}
func findNextEvenFibonacci(var firstFibonacci: Int = 0, var secondFibonacci: Int = 1) -> (Int, Int) {
 do {
 firstFibonacci += secondFibonacci
 swap(&firstFibonacci, &secondFibonacci)
 } while firstFibonacci % 2 != 0
 return (firstFibonacci, secondFibonacci)
}
let maxFibonacci: Int = 4_000_000
var fibonacci: (first: Int, next: Int) = (0,1)
var sumOfEvenFibonnaccis: Int = 0
while fibonacci.next < maxFibonacci {
 fibonacci = findNextEvenFibonacci(firstFibonacci: fibonacci.first, secondFibonacci: fibonacci.next)
 sumOfEvenFibonnaccis += fibonacci.first
}
let answer = sumOfEvenFibonnaccis

• Flambino: Isn't swap already built in? Quoting from the docs: "[...] you can use Swift’s existing swap function rather than providing your own implementation."
• nhgrif: Welp, apparently so. I just commented my swap function out and it still works just fine.

Answer 1

The following is similar to Flambino's approach, but creates a Swift SequenceType so that you can use the Swift library functions filter() and reduce() to iterate over the elements:

struct FibonacciSequence : SequenceType {
 let upperBound : Int
 func generate() -> GeneratorOf<Int> {
 var current = 1
 var next = 1
 return GeneratorOf<Int>() {
 if current > self.upperBound {
 return nil
 }
 let result = current
 current = next
 next += result
 return result
 };
 }
}
let fibseq = lazy(FibonacciSequence(upperBound: 4_000_000))
let sum = reduce(fibseq.filter { 0ドル % 2 == 0 }, 0) { 0ドル + 1ドル }

See here for more information about sequences and generators. This nice application made me actually understand how you can create your own sequences.

lazy() creates a LazySequence, whose filter() method returns the elements "on demand", e.g. as needed in the summation. The filter() function would return an array of all even Fibonacci numbers before starting the summation. (Kudos to @jtbandes for his suggestion).

---

Update: Due to major changes in the Swift programming language, the above code does not compile anymore with the current Swift 2.1/Xcode 7. Here is an updated version fore anybody's convenience:

struct FibonacciSequence : SequenceType {
 let upperBound : Int
 func generate() -> AnyGenerator<Int> {
 var current = 1
 var next = 1
 return anyGenerator {
 if current > self.upperBound {
 return nil
 }
 let result = current
 current = next
 next += result
 return result
 };
 }
}
let fibseq = FibonacciSequence(upperBound: 4_000_000).lazy
let sum = fibseq.filter { 0ドル % 2 == 0 }.reduce(0) { 0ドル + 1ドル }

• Flambino: Very nice. I reckoned there'd be a built-in "generator" type of some sort but I didn't know of it (and I failed to find it when I [quickly] looked, it seems)
• syb0rg: @MartinR Feel free to come join the regulars in the 2nd Monitor sometime!
• nhgrif: I really like this answer because generating sequences seems it will be very useful for the rest of the Project Euler problems plus outside of Project Euler--but for this specific question, won't this be quite slow comparatively? We generate all the Fibonacci numbers, then we filter down to the evens, then we add the evens up, rather than just adding as we go.
• jtbandes: Have you tried lazy()? There should be a version of filter which is lazy too.
• jtbandes: @MartinR Cool! I am working on a more general lazy solution which I'll post in a few minutes if I get it working.

Answer 2

I can only suggest a faster* math-based algorithm:

The fibonacci numbers are: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 and etc.

The even ones are: 0 at index 0, 2 at index 3, 8 at index 6, 34 at index 9 and so on.

This suggests that every third fibonacci number is even (starting from 0). Let's try and prove this by induction:

WARNING MATH AHEAD

We have already proved a few base cases: index 0 and 3 are even fibonacci numbers.

Suppose Fibonacci(3 * n) is even.

Fibonacci(3 * (n + 1)) = Fibonacci(3n + 3)
 = Fibonacci(3n + 2) + Fibonacci(3n + 1)
 = 2 * Fibonacci(3n + 1) + Fibonacci(3n)

Since 2 * Fibonacci(3n + 1) is even, and by the induction hypothesis, Fibonacci(3n) is even, which means the sum is even as well, and so Fibonacci(3 * (n+1)) must also be even. Thus induction is complete and we have proved that every third Fibonacci number is even.

Next we have to prove that all the other numbers are not even. Since we know Fibonacci(1) = 1 is odd, then using the same logic as previously, we can show that Fibonacci(3n + 1) = 2 * Fibonacci(3n - 1) + Fibonacci(3n + 1) which is guaranteed to be odd. Similarly the result will be obtained for all n = 2 mod 3.

END OF MATH

This simplifies your task to just summing every third fibonacci number, with no need to check if it is even or not, as we have just proved they are the only even fibonacci numbers.

• (DISCLAIMER) In the Python scripts I wrote to test this, the difference in time wasn't obvious until roughly 10¹⁰⁰⁰

• nhgrif: To be clear, this just eliminates checking whether or not the result is even, right?
• Flambino: Interesting. I suspected there was a pattern to the parity, but... math is hard (and I was lazy) :P
• Flambino: @nhgrif That's my understanding, although there are ways of generating the Nth number in the sequence that look interesting on their own. Of course, if you use an algorithm that still produces the entire sequence, uh, sequentially to find the Nth number, just checking parity along the way is no doubt simpler
• mleyfman: @nhgrif That is indeed correct. It saves on a few modulos. That is all.
• Martin R: Your statement about even Fibonacci numbers can also be deduced from the formula \$ \gcd(F_m, F_n) = F_{\gcd(m, n)} \$: \$ \gcd(F_m, 2) = \gcd(F_m, F_3) = F_{\gcd(m, 3)} \$ which is \$ F_3 = 2 \$ or \$ F_1 = 1 \,ドル depending on whether \$ m \$ is a multiple of 3 or not.

Answer 3

Disclaimer: This is the most I've ever written in Swift. In other words, I barely know what I'm doing.

My gut feeling, Swift or no Swift, is the the findNextEvenFibonacci function is a little too specific on its own. I'd probably have another function that just generates the next Fibonacci number - even or odd. Its parity is then checked when summing up.

Also, I don't know how to feel about the tuple. While it's a simple, direct solution a tuple also feels a little opaque. Given that structs are quite powerful in Swift, a fully declared struct with some functions might be better.

Here's my naïve attempt:

struct FibonacciPair {
 var current: Int
 var previous: Int
 // using the name successor, since that's what Int
 // calls its next-in-sequence function
 func successor() -> FibonacciPair {
 return FibonacciPair(current: current + previous, previous: current)
 }
}
var generator = FibonacciPair(current: 1, previous: 1)
var sum = 0
while generator.current < 4_000_000 {
 if generator.current % 2 == 0 {
 sum += generator.current
 }
 generator = generator.successor()
}
let answer = sum

This is of course the sort of task that can be accomplished in a hundred different ways - the above is just what came to my mind first.

Aside: A few of those hundred other ways would be wholly procedurally without any functions or structs or other such contraptions - just a while loop and some variables. But I figure the idea here is also to play around with Swift.

Perhaps it'd be reasonable to extend Int with an isEven function, while we're at it. It's basic enough to be of general use as a core type extension, and it'd clean up the while loop above a little bit

extension Int {
 func isEven() -> Bool {
 return self % 2 == 0
 }
}

An alternative approach might be a Fibonacci-number generator that takes a closure. If only a closure could break the loop in which it's called instead of returning a bool... oh, well

func eachFibonacciNumber(iterator: (Int) -> (Bool)) {
 var current = 1
 var previous = 0
 while iterator(current + previous) {
 swap(&previous, &current)
 current += previous
 }
}
var sum = 0
eachFibonacciNumber() {
 // note: I definitely should be checking 0ドル < limit *before*
 // incrementing the sum... but it looks prettier if I don't :P
 if 0ドル.isEven() { sum += 0ドル }
 return 0ドル < 4_000_000
}
let answer = sum

eachFibonacciNumber is a terrible Ruby'esque-but-not-really name, but you get the idea.

The limit could also just be an argument of course, which would avoid the bool return:

func fibonacciNumbersUpTo(limit: UInt, iterator: (Int) -> ()) {
 var current = 1
 var previous = 0
 while current < limit {
 iterator(current)
 swap(&previous, &current)
 current += previous
 }
}
var sum = 0
fibonacciNumbersUpTo(4_000_000) {
 if 0ドル.isEven() { sum += 0ドル }
}

That's is probably the nicest, most straightforward of the bunch, in my opinion.

In either case, though, the idea is to have a way to get the regular Fibonacci sequence, and then deciding what to do with each number, rather than using a specific "only even Fibonacci numbers" device. Of course, either of the above could be form the basis for such a device.

In any case, going through Project Euler with Swift is a nice idea - I'll probably do the same :)

• syb0rg: Regarding your disclaimer: I think that can be said for most Swift developers.
• Flambino: @syb0rg Heh, yeah, I guess so. But considering I was quick to install the Xcode beta, but haven't gotten around to actually using it, I'm a little embarrassed nonetheless :)

Answer 4

Here is an approach using a general RecurrenceRelation struct which can be used to write any recurrence, not just the Fibonacci sequence (the Fibonacci sequence is defined by initial conditions (1,1) and the relation T[n] = T[n-1] + T[n-2]). I also define takeWhile as an extension to LazySequence so the functionality doesn't have to be built into RecurrenceRelation — Swift has a built-in prefix but it seems to be designed for random-access collections only.

struct RecurrenceRelation<E> : SequenceType {
 let initialCondition: [E]
 let relation: (T: [E], n: Int) -> E
 init(_ initialCondition: [E], relation: (T: [E], n: Int) -> E) {
 self.initialCondition = initialCondition
 self.relation = relation
 }
 func generate() -> GeneratorOf<E> {
 var memory = initialCondition
 var i = 0
 return GeneratorOf<E> {
 if i < memory.count { return memory[i++] }
 memory.append(self.relation(T: memory, n: memory.count))
 memory.removeAtIndex(0)
 return memory.last
 }
 }
}
extension LazySequence {
 func takeWhile(pred: S.Generator.Element -> Bool) -> LazySequence<SequenceOf<S.Generator.Element>> {
 return lazy(SequenceOf { () -> GeneratorOf<S.Generator.Element> in
 var g = self.generate()
 return GeneratorOf<S.Generator.Element> {
 let n = g.next()
 if n == nil || !pred(n!) { return nil }
 return n
 }
 })
 }
}
let fib = RecurrenceRelation([1, 1]) { (T, n) in T[n-1] + T[n-2] }
let n = reduce(lazy(fib).takeWhile { 0ドル < 4_000_000 }.filter { 0ドル % 2 == 0 }, 0, +)