Go implementation of Fibonacci - two ways

There are various ways how to go about the implementation of Fibonacci, or other series, in Go. Some are common to different languages, like a recursive function or using a closure. One approach is Go specific, taking advantage of its concept of channels. I shall be showing and explaining the closure based and channel based implementations.

Closure based implementation

Closures are functions that "close over"  the scope of the parent namespace and, as a result, have access to and remember variables in the parent scope, even after they finished running. As a result, closures have been used abundantly to implement, for instance, counter incrementing.

Channel based implementation

Go introduced a concept of channels, that serve for communication between goroutines, the Go approach to concurrency. If a channel is created without specifying its capacity, it is blocking and the processing will stop until the channel receives or can send data (depending on whether a sender or a receiver).

Full program

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64

package main import ( "fmt" "time" ) func main() { max := 15 fmt.Println("================== FIBONACCI CLOSURE implementation ==================") start := time.Now() fmt.Println("%s", start) f := fib_closure() for n := 0; n < max; n++ { fmt.Printf(">>> %d\n", n) fmt.Println(f(n)) } end := time.Now() fmt.Printf("Calculation finished in %s \n", end.Sub(start)) fmt.Println("================== FIBONACCI: CHANNEL implementation ==================") fmt.Println("%s", start) start = time.Now() c := fib_chan() for n := 0; n < max; n++ { fmt.Printf(">>> %d\n", n) fmt.Println(<-c) } end = time.Now() fmt.Printf("Calculation finished in %s \n", end.Sub(start)) } func fib_closure() func(int) int { i, j := 1, 1 return func(n int) int { switch { case n == 0 || n == 1: return 1 default: i, j = j, i+j } return i } } func fib_chan() chan int { c := make(chan int) go func() { for i, j := 0, 1; ; i, j = i+j, i { c <- i } }() return c }

Explanation

Shared by both approaches:

We decide how many Fibonnaci numbers we want calculated.

Performance comparison        max := 15

We are also interested in the performance of each approach, so we shall do some benchmaking using start := time.Now(), end :+ time.Now() and subtraction end.Sub(start).

Fibonacci - closure implementation

func fib_closure() func(int) int {

i, j := 1, 1 ..... for 0 and 1, the fibonnaci is 1

return func(n int) int { .... We are returning a closure, that on each subsequent invocation remembers the                                                            values  of i and j.

switch {
case n == 0 || n == 1:
return 1
default:
i, j = j, i+j  ........ The previous state is remembered (i, j) and the new one calculated (j, i+j)
}

return i
}
}

Then doing the calculations: 

fmt.Println("================== FIBONACCI CLOSURE implementation ==================")
start := time.Now()
fmt.Println("%s", start)

f := fib_closure() ............ We initialize the state by running the fib_closure()  and creating a reference to its                                                        return function/closure.

for n := 0; n < max; n++ {
fmt.Printf(">>> %d\n", n)
fmt.Println(f(n)) ..... The closure f(n) remembers calculations of < n
}
end := time.Now()
fmt.Printf("Calculation finished in %s \n", end.Sub(start))

Fibonacci - channel implementation

func fib_chan() chan int {
c := make(chan int)

go func() {
for i, j := 0, 1; ; i, j = i+j, i { ..... the logic of the fibonnaci calculation
c <- i  ................................. the result is sent to the channel
}
}()

return c
}

Then doing the calculations:

fmt.Println("================== FIBONACCI: CHANNEL implementation ==================")
fmt.Println("%s", start)

start = time.Now()
c := fib_chan() ................ Go channel which returns the Fibonacci result sent to it

for n := 0; n < max; n++ {
fmt.Printf(">>> %d\n", n)
fmt.Println(<-c) ...... the channel returns received the calculated value
}
end = time.Now()
fmt.Printf("Calculation finished in %s \n", end.Sub(start)) 

Performance comparison

On different runs, I got the following runtimes:

Closure - Channel

      222 - 140 us
      253 - 168 us
      255 - 175 us

The difference is due to what else the OS was doing at the time when the program ran. The closure implementation is roughly 1.5 times slower. (The recursive approach is the slowest.)