Parallel brute-force solution for Project Euler 4 (Largest palindrome product)

The pe4Concurrent.go file given below is my first attempt at writing a concurrent programme, pe4.go is a non-concurrent implementation of the same algorithm for comparison purposes.

The algorithm itself is a simple, brute force solution to one of the Project Euler problems.

Basically, I'm very new to both Go and concurrency and would appreciated any suggestions as to how the efficiency or elegance of my use of channels and goroutines in pe4Concurrent.go might be improved.

Non-concurrent brute force solution (included for comparison purposes):

pe4.go

//Project Euler: Problem 4

//Largest palindrome product

//A palindromic number reads the same both ways. The largest
//palindrome made from the product of two 2-digit numbers is
//9009 = 91 × 99.

//Find the largest palindrome made from the product of two
//3-digit numbers.

package main

import "fmt"
import "time"

func isPalindrome(s string) bool {
    if len(s) = lowerLimit; i-- {

        for j := i - 1; j > 0; j-- {

            candidate := i * j

            s := fmt.Sprintf("%d", candidate)

            if isPalindrome(s) {

                if candidate > highestPal {

                    highestPal = candidate
                }
            }
        }
    }

    elapsed := time.Since(start)

    //num := 1000 * 999
    //s := fmt.Sprintf("%d", num)
    //output := isPalindrome(s)
    //fmt.Println(output)
    //output = isPalindrome("101")
    //fmt.Println(output)
    //output = isPalindrome("9")
    fmt.Println(highestPal)
    fmt.Println("Programme execution time %s", elapsed)
}

Concurrent brute force solution:

pe4Concurrent.go

```
//Project Euler: Problem 4

//Largest palindrome product

//A palindromic number reads the same both ways. The largest
//palindrome made from the product of two 2-digit numbers is
//9009 = 91 × 99.

//Find the largest palindrome made from the product of two
//3-digit numbers.

// Note:
// Brute force solution launching 900 goroutines outperforms
// the same algo

Brute Force.

Your use of go-routines is pretty simple, but effective. The part I don't think is best, is the use of the channel. The channel itself is good, but the control structures you have to read content from the channel, could be better. In fact, you have a bug in them (although you are lucky that the data means you don't encounter the bug).

Let me describe the bug, first. You assume that every go-routine is going to add a value to the channel (there will be at least one palindrome). You also assume there is at most one palindrome. If there end up being fewer palindromes than routines, you may end up "hanging" on the channel when all routines are done, but no values are coming. If there are more palindromes than routines, you may have the "max" palindrome happen later in the channel than you read.

I would recommend using a wait-group for the go-routine, and then closing the channel in the completion. In essence, I would restructure the code:

lowerLimit := 100

upperLimit := 1000

c := make(chan int)

for i := upperLimit - 1; i >= lowerLimit; i-- {

    go getHighestPal(i, c)
}

for i := 0; i  highestPal {

        highestPal = candidate
    }
}

to be:

lowerLimit := 100
upperLimit := 1000

count := upperLimit - 1 - lowerLimit

palindromes := make(chan int, 1024)

var wg sync.WaitGroup
wg.Add(count)
for i := 0; i  highestPal {
        highestPal = candidate
    }
}

Note how the internals of the getHighestPal no longer affect the reading of the channel? Also note how Ihave to create the closure parameter i + lowerLimit inside the go-routine call in order to have the right context for each routine.

A second bug you have is the elimination of square numbers. Again, it does not affect the results in this instance, but the code in getHighestPal should be for j := i and not j := i - 1. All squares of values containing only 1 digits are famously palindromes: 1111 * 1111 is 1234321 for example.

Finally, your method getHighestPal implies it gets the highest palindrome, but it gets all palindromes..... not just the highest.
Non-Brute-Force

So, a couple of other things to consider.

The fmt.Sprintf is slower than strconv.Itoa. Consider that change (it's 2 to 3 times slower in my tests).

Also, you can be creative about what you do in your algorithm to improve performance. I took your code and ran it my way.....

func isPalindrome(v int) bool {
    str := strconv.Itoa(v)
    right := len(str) - 1
    left := 0
    for left = minlow; low-- {
        for high := maxfact; high >= low; high-- {
            prod := low * high
            if prod <= max {
                // no need to keep looking for things that can't possibly be larger than previous max.
                break
            }
            if isPalindrome(prod) {
                max = prod
                // limit how far we search back to things that would exceed the smallest factor
                minlow = max / maxfact
            }
        }
    }

    return max
}

When run in the same way as your code:

func main() {
    start := time.Now()

    maxp := maxPalindrome(999)

    elapsed := time.Since(start)
    fmt.Println(maxp)
    fmt.Println("Programme execution time %s", elapsed)

}

I was substantially faster.

On my machine, your sequential code returned:

906609
Programme execution time %s 99.33103ms

your concurrent code returned:

906609
Programme execution time %s 26.010698ms

And the above code returned:

906609
Programme execution time %s 206.964µs

• about 100 times faster than your concurrent code.

StackExchange Code Review Q#153787, answer score: 3