Finding the longest Collatz sequence using Go, concurrently
Longest Collatz sequence
  
  Problem 14
  
  The following iterative sequence is defined for the set of positive
  integers:

n → n/2 (n is even)
n → 3n + 1 (n is odd)

  
  Although it has not been proved yet (Collatz Problem), it is thought
  that all starting numbers finish at 1.
  
  Which starting number, under one million, produces the longest chain?




In Go, the testing package includes a benchmark facility. Therefore, if we are concerned about performance, as we often are, we start with a simple implementation and benchmark it. Starting number 837799 produces the longest chain of 525 elements. When I ran a Go benchmark, it took 231,949,902 nanoseconds, about one-quarter of a second.

BenchmarkEuler14-8   5   231949902 ns/op   0 B/op   0 allocs/op


euler14a_test.go:

package main

import "testing"

func lenChain(n int) int {
    c := 1
    for ; n &gt; 1; c++ {
        if n&amp;1 == 0 {
            n &gt;&gt;= 1
        } else {
            n += n&lt;&lt;1 + 1
        }
    }
    return c
}

func euler14() (maxn, maxc int) {
    maxs := 1000000 - 1
    for n := 1; n &lt;= maxs; n++ {
        c := lenChain(n)
        if maxc &lt; c {
            maxn = n
            maxc = c
        }
    }
    return maxn, maxc
}

func BenchmarkEuler14(b *testing.B) {
    for N := 0; N &lt; b.N; N++ {
        euler14()
    }
}


If you you want it to be faster, perhaps we could remember some intermediate results. When I ran a Go benchmark, it took 16.979.849 nanoseconds, about than one-sixtieth of a second.

BenchmarkEuler14-8  100  16979849 ns/op  4005900 B/op  1 allocs/op


euler14b_test.go:

package main

import (
    "testing"
)

func lenChain(n int, a []int) int {
    if n &lt; 1 {
        return 0
    }

    c := 1
    for m := n; m &gt; 1; {
        if m &lt; len(a) &amp;&amp; a[m] &gt; 0 {
            c += a[m] - 1
            break
        }

        if m&amp;1 == 1 {
            // m is odd:
            // m = 3*m + 1
            m += m&lt;&lt;1 + 1
            c++
        }
        // m is even:
        // m = m/2
        m &gt;&gt;= 1
        c++
    }

    if n &lt; len(a) &amp;&amp; a[n] &lt; c {
        a[n] = c
    }

    return c
}

func euler14() (maxn, maxc int) {
    maxs := 1000000 - 1
    a := make([]int, maxs/2)
    for n := 1; n &lt;= maxs; n++ {
        c := lenChain(n, a)
        if maxc &lt; c {
            maxn = n
            maxc = c
        }
    }
    return maxn, maxc
}

func BenchmarkEuler14(b *testing.B) {
    for N := 0; N &lt; b.N; N++ {
        euler14()
    }
}


When I ran your "concurrent" program, using eight threads, it took 639,898,032 nanoseconds, about two-thirds of a second.



Some real-world code review questions: What is concurrency? What is parallelism? What do you expect to accomplish? What is your plan?

In your earlier Go performance question, Finding all prime numbers within a range, I pointed ot the importance of benchmarking and algorithms.

You only timed your program. You did not run Go benchmarks. You have no detail. You only used one simple algorithm. My benchmarks allowed me to peer into my code, often line by line. My code, using an optimized memoization algorithm, runs around nearly forty times faster than your concurrent code.

Efficient solutions to the problem exhibit little concurrency and little parallelism. Using concurrency tools adds overhead without any corresponding benefit.




  Comment:
  You compute a lot of intermediate values in the sequence, yet only
  cache the first (being m). I'd imagine your solution would be a lot
  faster if you made a second pass in lenChain that filled all the
  misses into a. If you bite the bullet with function call overhead for
  a recursive implementation, this change would even be trivial. –
  Dillon Davis




When I ran benchmarks, your idea, despite using more memory, was slower: 22,234,021 versus 16.979.849 nanoseconds.

euler14c_test.go:
BenchmarkEuler14-8   50  22234021 ns/op  8003587 B/op  1 allocs/op

euler14b_test.go:
BenchmarkEuler14-8  100  16979849 ns/op  4005900 B/op  1 allocs/op


euler14c_test.go:

package main

import (
    "testing"
)

func lenChain(n int, a []int) int {
    if n &lt;= 1 {
        if n != 1 {
            return 0
        }

        c := 1
        if n &lt; len(a) {
            if a[n] == 0 {
                a[n] = c
            }
        }
        return c
    }

    if n &lt; len(a) {
        if a[n] &gt; 0 {
            return a[n]
        }
    }

    m := n
    if m&amp;1 == 0 {
        // m is even:
        // m = m/2
        m &gt;&gt;= 1
    } else {
        // m is odd:
        // m = 3*m + 1
        m += m&lt;&lt;1 + 1
    }
    c := 1 + lenChain(m, a)

    if n &lt; len(a) {
        a[n] = c
    }

    return c
}

func euler14() (maxn, maxc int) {
    maxs := 1000000 - 1
    a := make([]int, maxs+1)

    for n := 1; n &lt;= maxs; n++ {
        c := lenChain(n, a)
        if maxc &lt; c {
            maxn = n
            maxc = c
        }
    }

    return maxn, maxc
}

func BenchmarkEuler14(b *testing.B) {
    for N := 0; N &lt; b.N; N++ {
        euler14()
    }
}