# The Fibonacci SequenceType

Swift sequences with a mathematical motive

Say you just learned about Swift for the first time. You’re so excited that you spend the next whole day practicing Swift. (Who wouldn’t?) By the following day you’ve become an expert, so you start offering daily Swift lessons to share your wisdom.

What’s that? Of course, I’d gladly be your first student! I catch on quickly, and after a day of practice, I’m ready to start teaching Swift lessons myself. We both keep teaching, and our students pick it up — and start teaching their own students — just as fast as we did.

What an exciting world to live in! But it poses a bit of a logistical problem. If Swift learners keep pouring into the city, the infrastructure will start to falter.

The mayor calls in her very best scientists. *“We need accurate models! How many people will be using Swift each day? WHEN WILL THE MADNESS END?”*

## Modeling the Swiftening

To get a feel for the problem, let’s draw a diagram of what happens in the first few days:

It’s not really practical to keep doing this by hand, since the tree keeps branching quickly — we’d run out of space to keep adding new Swifters. But looking closely, a simple pattern emerges. On any particular day, the total number of Swifters (we’ll call it S_\text{today}) is whatever it was yesterday (S_\text{yesterday}), plus a new student for every available teacher.

But what’s the number of available teachers? Remember, it takes a day of learning and a day of practice for someone to become an expert in Swift.^{1} So **everybody who’s been present** since the day before yesterday can take on a new student: \color{red}{S_\text{today}} = \color{blue}{S_\text{yesterday}} + \color{green}{S_\text{day before yesterday}}.

Now we’re getting somewhere! That formula is so simple, we can calculate it by hand:

(You can confirm that these numbers match our diagram above.) Now, I’ll let you in on a secret: if this sequence looks familiar, that’s because these are the **Fibonacci numbers**.

Like it or not, they’re everywhere — whether it’s flowers growing Fibonacci numbers of petals, trees with Fibonacci branches, or someone complaining it’s all just confirmation bias. As we discovered, the sequence is based on a simple pattern, and it’s easy to compute^{2}:

```
var i = 0
var j = 1
while true {
(i, j) = (j, i + j)
print(i) // prints 1, then 1, then 2, 3, 5, 8, 13, 21, 34, 55...
}
```

Nothing more to see here — we’ve done it!

Haha, gotcha. We’ve just begun. The beauty of computers is that they can quickly answer questions that would be tedious for us to do by hand. Let’s try a few.

### How many Swifters are there after 42 days?

We almost answered this question already; we just need to stop at 42 instead of going on forever.

```
var i = 0
var j = 1
</span>for _ in 0..<42 {
(i, j) = (j, i + j)
}
i // returns 267914296
```

That wasn’t so bad. We can handle something a little more complicated:

### What about the nth day?

In a way, this is the exact same question. We just need to generalize a little. We’ll pull out 42 from our last answer, and replace it with a variable called

:`n`

```
func nthFibonacci(n: Int) -> Int
{
var i = 0
var j = 1
for _ in 0..<n {
(i, j) = (j, i + j)
}
return i
}
nthFibonacci(42) // returns 267914296
nthFibonacci(64) // returns 10610209857723
```

### How much Swift was written in the first week?

For simplicity, assume everybody writes Swift at about the same rate. Then to find the number of **person-days** of Swift written, we just need to add up the Fibonacci numbers each day:

```
func fibonacciSumUpTo(n: Int) -> Int
{
var sum = 0
for i in 0..<n {
sum += nthFibonacci(i) // the number of people writing Swift on day i
}
return sum
}
fibonacciSumUpTo(7) // returns 33
```

## Better Living through Gradual Simplification

Hold the phone! Swift’s standard library already has a function called `reduce`

which can add numbers together. What are we doing writing our own?

`[1, 1, 2, 3, 5, 8, 13].reduce(0, combine: +) // returns 33`

That works nicely, but we had to write out the Fibonacci numbers 1, 1, 2, 3, 5, 8, 13 by hand. Wouldn’t it be better to use the `nthFibonacci()`

function we wrote already?

Well, since these are **successive** Fibonacci numbers, we can start with a simple range of numbers from 1 through 7:

```
[1, 2, 3, 4, 5, 6, 7].map(nthFibonacci) // returns [1, 1, 2, 3, 5, 8, 13]
[1, 2, 3, 4, 5, 6, 7].map(nthFibonacci).reduce(0, combine: +) // returns 33
```

Or here’s a further simplification using Swift’s inclusive range operator (`...`

):

`(1...7).map(nthFibonacci).reduce(0, combine: +) // returns 33`

This is equivalent to `fibonacciSumUpTo`

.

### Performance Considerations

Looks great, but remember that `nthFibonacci(i)`

starts from 0 and works its way up to i, so the amount of work required scales up linearly with i.

And since our summing-doohickey `(1...n).map(nthFibonacci).reduce(0, combine: +)`

runs the `nthFibonacci`

function on *every number* from 1 to n, the **total work grows quadratically** with n.

If we didn’t have to start over at 1 for each successive Fibonacci number, we could add them together with much less work. Let’s combine the `nthFibonacci`

and `fibonacciSumUpTo`

functions we had previously, and build up the total while calculating the numbers themselves at the same time:

```
func fastFibonacciSumUpTo(n: Int) -> Int
{
var sum = 0
var i = 0
var j = 1
for _ in 0..<n {
(i, j) = (j, i + j) // calculate the next number
sum += i // update the sum
}
return sum
}
fastFibonacciSumUpTo(7) // returns 33
```

Now, we’ve achieved linear instead of quadratic time complexity for `fastFibonacciSumUpTo`

.

But in order to do this, we had to make a more complicated, specialized function. We’ve made a trade-off between **separation of concerns** (calculating the Fibonacci numbers and adding them together as separate steps) and **performance**.

The plan is to use the Swift standard library to simplify and untangle our code. First, let’s summarize what we’d like to do.

the first n Fibonacci numbers in linear time and constant space.*Sum*Sum

Fibonacci numbers*the first n*.*in linear time and constant space*Sum the first n

in linear time and constant space.*Fibonacci numbers*

Luckily, Swift has just the features we need!

The

`reduce`

function, combined with the`+`

operator.The

`prefix`

function and lazy evaluation.Custom sequences, via the

`SequenceType`

protocol.

## The Custom Sequence

The foundation of Swift’s `for`

–`in`

loops is the `SequenceType`

protocol. Anything that adopts `SequenceType`

can be looped over.

To be a `SequenceType`

there is only one requirement, and that’s providing a `Generator`

:

```
protocol SequenceType {
typealias Generator: GeneratorType
func generate() -> Generator
}
```

And for `GeneratorType`

s, there’s only one requirement, which is to produce `Element`

s.

```
protocol GeneratorType {
typealias Element
mutating func next() -> Element?
}
```

So a **sequence** is something which can provide **generators** of **elements**.

The quickest way to make a custom sequence in Swift is with `AnySequence`

. It’s a built-in struct that responds to `generate()`

by calling a closure you give it at initialization.

```
struct AnySequence<Element>: SequenceType {
init<G: GeneratorType where G.Element == Element>(_ makeUnderlyingGenerator: () -> G)
}
```

And similarly, to make the generator, we can make use of `AnyGenerator`

and the `anyGenerator`

function:

`func anyGenerator<Element>(body: () -> Element?) -> AnyGenerator<Element>`

So writing a Fibonacci sequence is really quite simple:

```
let fibonacciNumbers = AnySequence { () -> AnyGenerator<Int> in
// To make a generator, we first set up some state...
var i = 0
var j = 1
return anyGenerator {
// ...and the generator modifies its state for each call to next().
// (Does this look familiar?)
(i, j) = (j, i + j)
return i
}
}
```

That’s it.

Now, since `fibonacciNumbers`

is a `SequenceType`

, we can use it in a `for`

loop:

```
for f in fibonacciNumbers {
print(f) // prints 1, then 1, then 2, 3, 5, 8, 13, 21, 34, 55...
}
```

And, we get `prefix`

for free:

```
for f in fibonacciNumbers.prefix(7) {
print(f) // prints 1, 1, 2, 3, 5, 8, 13, then stops.
}
```

Finally, let’s chain it with `reduce`

:

`fibonacciNumbers.prefix(7).reduce(0, combine: +) // returns 33`

Great! This is linear-time, constant-space, and importantly it **clearly** communicates what we’re trying to do, without the noise from `...`

and `map`

.

## Flexibility

The goal so far has been to give ourselves better tools to answer specific questions about the Fibonacci numbers, as they pertain to people learning Swift (at frankly alarming rates).

Delving deeper, it might be natural to ask: **why** are we dealing with Fibonacci numbers in the first place? The sequence just so happens to match the scenario of The Swiftening, because of the pattern we discovered:

This formula does appear in our code as `(i, j) = (j, i + j)`

. But it’s buried deep inside `AnySequence`

and `anyGenerator`

. If we’re trying to write code that is clear — code that describes the problem it’s trying to solve and doesn’t require dissecting — we’d better make this a little more obvious.

The Fibonacci sequence is commonly written as

This is exactly the same as our S_\text{today} version, just with numbers for indices instead of words. Importantly, it alludes to the more general notion of **recurrence relations**. That’s fancy math talk for a sequence whose next value depends on some of its previous values. Other examples might be T_{n} = 3T_{n-1} - 2T_{n-2}, or x_n = rx_{n-1}(1-x_{n-1}).

When defining a recurrence relation, it’s also crucial to provide **initial terms**. We can’t simply proceed to calculate the Fibonacci numbers with `(i, j) = (j, i + j)`

if we don’t know what `i`

and `j`

started at. In this case, our initial terms were `i = 0`

and `j = 1`

— or, since we waited to perform the calculation once before returning our first value, the initial terms are 1 and 1.

The **order** of a recurrence relation is the number of previous terms needed at each step. And there must be exactly that many initial terms given (otherwise, we wouldn’t have enough information to calculate the very next term).

That’s enough for us to design an API! To create a recurrence relation, you’d just need to provide initial terms and an actual recurrence:

```
struct RecurrenceRelation<Element>
{
/// - Parameter initialTerms: The first terms of the sequence.
/// The `count` of this array is the **order** of the recurrence.
/// - Parameter recurrence: Produces the `n`th term from the previous terms.
init(_ initialTerms: [Element], _ recurrence: (T: UnsafePointer<Element>, n: Int) -> Element)
}
```

(We’re using `UnsafePointer<Element>`

instead of just `[Element]`

so that we can make `T[n]`

work without actually storing all previously calculated terms.)

Now, our initial task gets even easier. **How many people are writing Swift?** Just plug in the formula.

```
let peopleWritingSwift = RecurrenceRelation([1, 1]) { T, n in T[n-1] + T[n-2] }
peopleWritingSwift.prefix(7).reduce(0, combine: +) // returns 33
```

### So, how about that implementation?

Let’s get down to it.

```
struct RecurrenceRelation<Element>: SequenceType, GeneratorType
{
```

First we need some storage for elements, and a reference to the closure we’re being given.

```
private let recurrence: (T: UnsafePointer<Element>, n: Int) -> Element
private var storage: [Element]
/// - Parameter initialTerms: The first terms of the sequence.
/// The `count` of this array is the **order** of the recurrence.
/// - Parameter recurrence: Produces the `n`th term from the previous terms.
init(_ initialTerms: [Element], _ recurrence: (T: UnsafePointer<Element>, n: Int) -> Element)
{
self.recurrence = recurrence
storage = initialTerms
}
```

To keep things relatively simple, we’re going to adopt both `SequenceType`

and `GeneratorType`

at the same time. For `generate()`

, we’ll just return `self`

.^{3}

```
// SequenceType requirement
func generate() -> RecurrenceRelation<Element> { return self }
```

Now, the meat of it — for each call to `next()`

, we produce the next value by calling the `recurrence`

, and then save it in `storage`

.

```
// GeneratorType requirement
private var iteration = 0
mutating func next() -> Element?
{
// Produce all the initial terms first.
if iteration < storage.count { return storage[iteration++] }
let newValue = storage.withUnsafeBufferPointer { buf in
// Call the closure with a pointer offset from the actual memory location,
// so that T[n-1] is the last element in the array.
return recurrence(T: buf.baseAddress + storage.count - iteration, n: iteration)
}
// Store the next value, dropping the oldest one.
storage.removeAtIndex(0)
storage.append(newValue)
iteration++
return newValue
}
}
```

Keep in mind: there are many other ways to define custom sequences. `CollectionType`

, `SequenceType`

, and `GeneratorType`

are just protocols, so you can adopt them in a way that suits your needs. That said, you probably won’t need to do it very often in practice — Swift’s standard library has got you covered most of the time. But if you feel the need for a custom data structure, the rest of your code will thank you if you make it conform to `CollectionType`

or `SequenceType`

.

## More Examples

Now that we’ve got a generalized recurrence relation, we can calculate lots of things without much effort. How about the Lucas Numbers? Just the same as Fibonacci, but with different initial terms:

```
// 2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521...
let lucasNumbers = RecurrenceRelation([2, 1]) { T, n in T[n-1] + T[n-2] }
```

Or the “Tribonacci Numbers”, a third-order recurrence with some interesting properties:

```
// 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504...
let tribonacciNumbers = RecurrenceRelation([1, 1, 2]) { T, n in T[n-1] + T[n-2] + T[n-3] }
```

With a little more work, we can visualize the chaotic bifurcation of the logistic map:

```
func logisticMap(r: Double) -> RecurrenceRelation<Double>
{
return RecurrenceRelation([0.5]) { x, n in r * x[n-1] * (1 - x[n-1]) }
}
for r in stride(from: 2.5, to: 4, by: 0.005) {
var map = logisticMap(r)
for _ in 1...50 { map.next() } // consume some values to let it settle
Array(map.prefix(10))[Int(arc4random_uniform(10))] // choose one of the next 10 values
}
```

Isn’t math neat?

### Further Recommendations

TED talk, The magic of Fibonacci numbers, by Arthur Benjamin.

Binet’s Formula, for a nearly constant-time formula to calculate Fibonacci numbers.

Arrays, Linked Lists, and Performance at Airspeed Velocity, with other interesting approaches to sequences, including discussion of

`ManagedBuffer`

.

Your mileage may vary. ↩︎

I’m glossing over the fact that the Fibonacci numbers quickly become too large for Swift’s native

`Int`

. Larger values are definitely attainable, but beyond the scope of this article. ↩︎Since the sequence is computed on-demand, this has the side effect that getting a new generator will effectively “branch off”, and further

`next()`

calls won’t affect other generators. This is also due to the value semantics of`Array`

— each time our sequence gets copied, so does its`storage`

array. ↩︎