afurlan's blog

Some days ago Google released Go, its own open source programming language. Go is intended to be a simple, fast and safe programming language that promotes the users to write programs through concurrent and communicating lightweight processes. If want to know more about how to install and how to use Go, please take a look at its official site: http://golang.org.

Today I installed Go to play with it a little bit and (as I use to), after the world famous "hello world" code, I wrote a program to generate the fibonacci's sequence. Actually I wrote two versions of the same program, the first one is the most common fibonacci code:

package main

import "os"
import "fmt"
import "strconv"

func fib1(n int) int {
    if n < 0 { return 0; }
    if n < 2 { return n; }
    return fib1(n-2) + fib1(n-1);
}

func main() {
    if len(os.Args) < 2 {
            fmt.Printf("Usage: %s NUM\n", os.Args[0]);
            os.Exit(1);
    }
    n, _ := strconv.Atoi(os.Args[1]);
    fmt.Printf("%d\n", fib1(n));
}

And the second version is basically the same code but keeping a history of the known results:

package main

import "os"
import "fmt"
import "strconv"

func fib2(n int, hist *map[int]int) int {
    if n < 0 { return 0; }
    if n < 2 { return n; }
    _, found := (*hist)[n];
    if !found {
            (*hist)[n] = fib2(n-2, hist) + fib2(n-1, hist)
    }
    return (*hist)[n];
}

func main() {
    if len(os.Args) < 2 {
            fmt.Printf("Usage: %s NUM\n", os.Args[0]);
            os.Exit(1);
    }
    n, _ := strconv.Atoi(os.Args[1]);
    hist := make(map[int]int);
    fmt.Printf("%d\n", fib2(n, &hist));
}

Once you have finished these codes, it's always nice to see how different their execution time are:

afurlan@merlin:~$ time ./fib1 45
1134903170

real    0m43.979s
user    0m43.887s
sys     0m0.008s
afurlan@merlin:~$ time ./fib2 45
1134903170

real    0m0.004s
user    0m0.004s
sys     0m0.000s

Go is a very nice language, let's go to Go. :)

As always: if you found some english bug, warn me and I'll be glad to fix it. :)