8
\$\begingroup\$

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.

\$\endgroup\$
17
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ That is elegant. \$\endgroup\$ – jsanc623 Mar 5 '14 at 17:33
  • \$\begingroup\$ 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. \$\endgroup\$ – gyre May 10 '14 at 13:12
  • \$\begingroup\$ @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. \$\endgroup\$ – amon May 10 '14 at 13:42
  • \$\begingroup\$ 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 \$\endgroup\$ – gyre May 10 '14 at 15:26
  • \$\begingroup\$ 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. \$\endgroup\$ – George Mauer Aug 20 '17 at 1:26
4
\$\begingroup\$

Your Fibonacci generator works (and looks) great but only for values below 2147483647 (i.e. 231-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

\$\endgroup\$
  • 1
    \$\begingroup\$ 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? \$\endgroup\$ – Sᴀᴍ Onᴇᴌᴀ Dec 5 '17 at 16:30
  • \$\begingroup\$ Yes, great addition! \$\endgroup\$ – aerth Dec 7 '17 at 1:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.