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.
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).
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))
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))
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.)
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
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
}
}
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
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
}
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
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.)
