0
\$\begingroup\$

I am working through this problem on project euler.

Basic purpose of the code:

/*
if n is even n -> n/2
if n is odd n -> 3n + 1
which starting number under 1 million produces the longest sequence?
*/

The trouble with the code is that when I implement concurrency as I have, the program runs considerably more slowly than when I am just returning values directly from the get_seq_len function. Am I implementing concurrency incorrectly? Or is the program just not complex enough that there is speed to be gained from concurrency or something?

package main

import ("fmt";"math";"time")

This function takes a number x and then using the formula described in the above comment block creates a sequence of numbers from it until the number 1 is reached. Originally I had the function simply returning the length of the sequence, but now I have it sending the length to the specified channel.

func get_seq_len(x int, c chan int) {
    var count int = 1
    for {
        if x == 1 {
            break
        } else if x%2 == 0 {
            x = x / 2
        } else {
            x = 3 * x + 1
        }
        count++
    }
    // return count + 1
    c <- count + 1
}

Here the main function just step through every number from 1 to whatever the max is and then tests the length of the sequence for that number. I use channel c to pass the sequenced length back to main().

func main() {
    start := time.Now()
    var max int = int(math.Pow(10,6))
    // var max int = int(math.Pow(3,3))
    var max_length int = 0
    var max_num int = 0
    c := make(chan int, 50)

    for i:=1; i<max; i++ {
        // length := get_seq_len(i, c)
        go get_seq_len(i, c)
        length := <-c

        if length > max_length { max_length = length; max_num = i }
    }

    fmt.Println(max_num)
    t := time.Now()
    elapsed := t.Sub(start)
    fmt.Println(elapsed)

}
\$\endgroup\$
1
\$\begingroup\$

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 > 1; c++ {
        if n&1 == 0 {
            n >>= 1
        } else {
            n += n<<1 + 1
        }
    }
    return c
}

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

func BenchmarkEuler14(b *testing.B) {
    for N := 0; N < 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 < 1 {
        return 0
    }

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

        if m&1 == 1 {
            // m is odd:
            // m = 3*m + 1
            m += m<<1 + 1
            c++
        }
        // m is even:
        // m = m/2
        m >>= 1
        c++
    }

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

    return c
}

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

func BenchmarkEuler14(b *testing.B) {
    for N := 0; N < 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 <= 1 {
        if n != 1 {
            return 0
        }

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

    if n < len(a) {
        if a[n] > 0 {
            return a[n]
        }
    }

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

    if n < len(a) {
        a[n] = c
    }

    return c
}

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

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

    return maxn, maxc
}

func BenchmarkEuler14(b *testing.B) {
    for N := 0; N < b.N; N++ {
        euler14()
    }
}
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Dillon Davis Mar 8 at 5:07
  • \$\begingroup\$ Thanks for the followup. That's interesting that it actually took longer. I could understand if may it took a negligible about less time due to memory fetching bottlenecks, but to actually be slower is surprising. I guess function call overhead + writing to more memory addresses offset any gains from caching these values. \$\endgroup\$ – Dillon Davis Mar 10 at 1:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.