Wsrtjtyk

The Java Code I'm attempting to translate. I've been trying to implement this java method of getting the nth Fibonacci number in Go but I can't seem to get my code past the number Fibonacci number 35 before it crashes. This method is supposed to be very inefficient but not so inefficient that it doesn't complete.

package main



import (

    "fmt"

    "time"

)



type Fibonacci struct {

    num    float64

    answer float64

}



func newFibonacci(n float64) *Fibonacci {



    f := new(Fibonacci)

    f.num = n

    c1 := make(chan float64)

    c2 := make(chan float64)



    if f.num <= 1 {

        f.answer = n

    } else {

        go func() {

            fib1 := newFibonacci(n - 1)

            c2 <- fib1.answer

        }()

        go func() {

            fib2 := newFibonacci(n - 2)

            c1 <- fib2.answer   

        }()



        f.answer = <-c2 + <-c1

    }

    close(c1)

    close(c2)



    return f

}



func main() {



    numbers := float64{30, 35, 36, 37, 38, 39, 40}

    for _, value := range numbers{

        start := time.Now()

        fmt.Println("getting the ", value, " fibonacci number")

        f := newFibonacci(value)

        fmt.Println(f.answer)

        end := time.Now()

        totalTime := end.Sub(start)

        fmt.Println("Fibonacci number: ", value, " took ", totalTime, "n")

    }



}

I suggest you do the math behind how many goroutines you're actually launching.

Your first call spawns two goroutines. Each of those spawn two further goroutines. The total number of goroutines spawned will be 2^1 + 2^2 + 2^3 + ... + 2^n. While a lot of these will exit before you reach the number below, it's still a lot of goroutines.

You program create exponential number of go routines. That comes with context switching latency. Try to run it for limited number of go routines. See following code where i run it for limited number of go routines:

package main



import (

    "fmt"

    "time"

)



type Fibonacci struct {

    num    float64

    answer float64

}



type goRoutineManager struct {

    goRoutineCnt chan bool

}



func (g *goRoutineManager) Run(f func()) {

    select {

    case g.goRoutineCnt <- true:

        go func() {

            f()

            <-g.goRoutineCnt

        }()

    default:

        f()

    }

}



func NewGoRoutineManager(goRoutineLimit int) *goRoutineManager {

    return &goRoutineManager{

        goRoutineCnt: make(chan bool, goRoutineLimit),

    }

}



func newFibonacci(n float64, gm *goRoutineManager) *Fibonacci {



    f := new(Fibonacci)

    f.num = n

    c1 := make(chan float64, 1)

    c2 := make(chan float64, 1)



    if f.num <= 1 {

        f.answer = n

    } else {



        gm.Run(func() {

            fib1 := newFibonacci(n-1, gm)

            c2 <- fib1.answer

        })



        gm.Run(func() {

            fib2 := newFibonacci(n-2, gm)

            c1 <- fib2.answer

        })



        f.answer = <-c2 + <-c1

    }

    close(c1)

    close(c2)



    return f

}



func main() {



    numbers := float64{30, 35, 36, 37, 38, 39, 40} //{30, 35, 36, 37, 38, 39, 40}

    for _, value := range numbers {

        start := time.Now()

        fmt.Println("getting the ", value, " fibonacci number")



        gm := NewGoRoutineManager(3)



        f := newFibonacci(value, gm)

        fmt.Println(f.answer)



        end := time.Now()

        totalTime := end.Sub(start)

        fmt.Println("Fibonacci number: ", value, " took ", totalTime, "n")

    }



}