Tuesday, December 01, 2009

Fibonacci in Go

I've been playing around with Go a bit. Here's what I think is the most Go-like solution to producing the Fibonacci sequence.
package main

import "fmt"

func dup3(in <-chan int) (<-chan int,<-chan int,<-chan int) {
a,b,c := make(chan int,2),make(chan int,2),make(chan int,2);
go func() { for { x := <-in; a <- x; b <- x; c <- x } }();
return a,b,c
}

func fib() <-chan int {
x := make(chan int,2);
a,b,out := dup3(x);
go func() { x<-0; x<-1; <-a; for { x<- <-a + <-b } }();
return out
}

func main() {
x := fib();
for i:=0; i<10; i++ { fmt.Println(<-x) }
}
I like it because I only ever declare a single integer variable, and the rest goes through chans. This solution is inspired by Haskell's concise "fib = 0:zipWith (+) fib (1:fib)". Any comments are most welcome. In particular, if there were a way to accomplish it (in the same style) without the buffered chans, that would be pretty cool (though I'd be a bit surprised, since it doesn't seem possible at first glance).

2 comments:

Frakturfreund said...

I’m sorry for commenting here, but since i can’t comment at “Happy Pi Day!” and there’s no other contact chance: I just reblogged it (on German), and put the source code at Gist.GitHub. I hope that’s okay for you (you can delete this post if you want, since it under the wrong post).

Micky said...

Here's the simple way to do it with unbuffered channels.

http://play.golang.org/p/cyXPCb_j70

Benchmarking it appears to have same performance as yours algorithm, i.e. slower than traditional non-channel fibonacci calculation, which makes me curious that why concurrent programming is slow in some cases.