Fibonacci generator with Golang

Question

This is my Fibonacci generator:

package main
import "fmt"
func main() {
 for i, j := 0, 1; j < 100; i, j = i+j,i {
 fmt.Println(i)
 }
}

It's working, but I don't know how I can improve it, so I'd like more expert approaches to solving it.

Answer 1

Your code is quite nice, and can't really be improved. However, let's put the "generator" back into the code.

Go has channels which can be used to write elegant generators/iterators. We spawn of a goroutine that fills the channel with the fibonacci sequence. The main thread then takes as many fibonacci numbers as it needs.

So let's write a function fib_generator that returns a channel to the fibonacci sequence:

func fib_generator() chan int {
 c := make(chan int)
 go func() { 
 for i, j := 0, 1; ; i, j = i+j,i {
 c <- i
 }
 }()
 return c
}

We return a chan int. Here, we use an unbuffered channel. You may want to introduce a bit of buffering, e.g. make(chan int, 7).

Next, we spawn a goroutine. This contains your code, but instead of printing the numbers, we fill the channel with them. Note that the generator does not have a termination condition.

The unusual syntax

go func() { ... }()

is the standard way to start a goroutine. Because the function literal is a closure over the channel c, we can run multiple generators concurrently.

Our main will look like

func main() {
 c := fib_generator()
 for n := 0; n < 12 ; n++ {
 fmt.Println(<- c)
 }
}

That is, we create a new generator, and then pull the first 12 values from the channel. We cannot write for i := range c { ... }, because the fibonacci generator does not terminate.

As I said, we can have multiple generators concurrently:

func main() {
 c1 := fib_generator()
 c2 := fib_generator()
 // read first 12 numbers from 1st channel
 for n := 0; n < 10 ; n++ { fmt.Print(" ", <- c1) }
 fmt.Println()
 // read first 12 numbers from 2nd channel. The same.
 for n := 0; n < 10 ; n++ { fmt.Print(" ", <- c2) }
 fmt.Println()
 // read next 5 numbers from 1st channel.
 for n := 0; n < 5 ; n++ { fmt.Print(" ", <- c1) }
 fmt.Println()
}

Output:

 0 1 1 2 3 5 8 13 21 34
 0 1 1 2 3 5 8 13 21 34
 55 89 144 233 377

• jsanc623: That is elegant.
• milosgajdos: I think the most elegant solution would be to use select on the created fibonacci channels and either append the latest generated fibonacci number to particular slice or print it per channel on which it was received. @amon 's example above is imho seemingly concurrent as particular fmt.Print() functions will be blocking until the number is generated so the particular generator loops will be done sequentially one after another.
• amon: @gyre Yes, but do note that generating the next number is so cheap that there is no blocking to seriously consider. Anyway, I was not trying to achieve true parallelism here, but only to show a way to easily handle infinite streams with Go. Coroutines are a natural choice for implementing a generator abstraction. As a result the control flow is in fact concurrent (whenever an item is consumed, control is transferred to the generator), but it does not execute in parallel – these are different things.
• milosgajdos: I totally agree with you. And I'm sorry if my comment made you feel otherwise! I just wanted to make sure that whoever reads this answer has a bigger picture - thanks to your answer to my comment all should be clear now. As for concurrency vs. parallelism we could spend ages about arguing what means what. I tend to agree with Rob Pike's interpretation which he explained in one of his excellent talks
• George Mauer: me: wtf, how does go not have a concept of generators/iterables? How do you generate an infinite sequence?! Outrageous! (does googling finds this) ... ok, that's cool.

Answer 2

Your Fibonacci generator works (and looks) great but only for values below 2147483647 (i.e. 2³¹-1).

To work with larger numbers, we can use the math/big package:

package main
import (
 "fmt"
 "math/big"
)
func main() {
 F1 := big.NewInt(0)
 F2 := big.NewInt(1)
 for {
 F1.Add(F1, F2)
 F1, F2 = F2, F1
 // print to standard output
 fmt.Printf("%v\n", F1)
 }
}

Run in Playground

• Sᴀᴍ Onᴇᴌᴀ: Does it make sense to explain that 2,147,483,647 is the 8th Mersenne prime number, and the maximum positive value for 32-bit signed binary integers?
• aerth: Yes, great addition!