Every Fibonacci number is the two before it added together. Two variables and one loop produce any of them, and the squares tile into a spiral.
Strategy
Dynamic programming, bottom up
Build up from the two numbers you already know, so nothing is worked out twice.
- Base: start from 0 and 1.
- Build: add the last two together to get the next one.
- Carry: keep only the two most recent values, and repeat n times.
Press Add square to lay down the next number as a square. Each one is as wide as the two before it stacked together, which is why they tile with no gaps and the spiral comes out.
Purpose
Get the nth number in the Fibonacci sequence.
Input
An int n, counting from 0.
Output
The nth number, with F(0) = 0 and F(1) = 1.
Constraints
- n has to be zero or more. A negative n falls straight out of the loop and returns
0. - The numbers grow fast. F(92) is the last one that fits in a 64-bit int.
- Two values are held at a time, so memory stays flat however large n gets.
How the sequence is built
The Fibonacci sequence starts 0, 1, and from there every number is the two before it added together.
So 0 and 1 make 1, then 1 and 1 make 2, then 1 and 2 make 3, then 2 and 3 make 5. Keep going and you get 8, 13, 21, 34, 55.
Lay those out as squares and they tile perfectly into a spiral, which is why the pattern turns up in sunflower heads and pine cones. It is also the standard example for showing how a loop can beat a recursive function by an enormous margin.
Divide any number by the one before it and the answer settles on the golden ratio. That is where the spiral comes from.
What the loop keeps track of
| Name | Type | What it is for |
|---|---|---|
| n | int | Which number in the sequence you want. |
| a | int | The current number. Starts at 0 and holds the answer at the end. |
| b | int | The next number along. Starts at 1. |
| i | int | Counts the passes, so the loop knows when to stop. |
Walk through it
1 Choose which number you want
Counting starts at zero, so n = 10 asks for the eleventh number in the sequence.
n := 102 Hold the first two numbers
Two variables are all the memory you need. There is no need to keep the whole sequence.
a, b := 0, 13 Shuffle both along by one
The next number becomes the current one, and the sum of the pair becomes the next. Go evaluates the right side first, so the old a is still available for the addition.
a, b = b, a+b
// 0,1 -> 1,1 -> 1,2 -> 2,3 -> 3,5 -> 5,84 Repeat n times
The loop counter only decides when to stop. It never appears in the arithmetic.
for i := 0; i < n; i++ {
a, b = b, a+b
}5 Read the answer from a
After n passes, a is holding the number you asked for.
return a // 55The whole program
Put it together and any number in the sequence comes back in a single pass.
package main
import "fmt"
// Fib returns the nth Fibonacci number, counting from F(0) = 0.
func Fib(n int) int {
a, b := 0, 1
for i := 0; i < n; i++ {
a, b = b, a+b
}
return a
}
func main() {
for i := 0; i <= 10; i++ {
fmt.Print(Fib(i), " ")
}
fmt.Println()
fmt.Println(Fib(50))
fmt.Println(Fib(90))
}$ go run main.go
0 1 1 2 3 5 8 13 21 34 55
12586269025
2880067194370816120Fib(90) is close to the ceiling. One more and a 64-bit int overflows, so past that you need math/big.