I'm not completely sure what's going on here so it's hard to generalize my question, but I'm going to try my very best.
In a video from a few years ago Matt Parker dared his viewers to find a power of two, which does not contain any digits which are a power of two. (For example, 2^16 = 65536. None of these digits individually are a power of two). Recently I got into learning Go and I thought it would be a nice introductory exercise to get used to the language.
I created this pretty quickly and then I decided to try to make it concurrent to make full use of my quad core processor. This is where things went downhill.
The goal here is to run a constant amount of goroutines each of which processes a different batch of numbers. I implemented the program like so:
package main
import (
"log"
"math/big"
"runtime"
)
//The maximum amount of goroutines
const routineAmt int = 3
//The amount of numbers for each routine to check
const rangeSize int64 = 5000
//The current start of the range to start checking
var rangeIndex int64 = 0
func main() {
//loop forever
for {
//if we have less routines running than the maximum
if runtime.NumGoroutine() < routineAmt {
c := make(chan bool)
// start a new one to check the next range:
go checkRange(rangeIndex, rangeIndex+rangeSize, c)
// wait for the signal that the values have been copied to the function, so that we can increment them safely:
<-c
close(c)
// increment the rangeIndex for the next routine which will start:
rangeIndex += rangeSize
}
}
}
// Function to check a range of powers of two, whether they contain any power-of-two-digits
func checkRange(from, to int64, c chan bool) {
c <- true // signal to the main routine that the parameter values have been copied
// Loop through the range for powers of two, which do not contain any power-of-two-digits
for i := from; i < to; i++ {
num := big.NewInt(2)
num.Exp(num, big.NewInt(i), nil)
if !hasStringPowerOfTwo(num.String()) {
log.Println("Found 2 ^", i)
}
}
log.Printf("Checked range %d-%d
", from, to)
}
// Function to check if a string contains any number which is a power of two
func hasStringPowerOfTwo(input string) bool {
powersOfTwo := [4]rune{'1', '2', '4', '8'}
for _, char := range input {
if runeInArray(char, powersOfTwo) {
return true
}
}
return false
}
// Function to check if a list of runes contains a certain rune
func runeInArray(a rune, list [4]rune) bool {
for _, b := range list {
if b == a {
return true
}
}
return false
}
After waiting about 15 minutes or so, the program still did not finish a single go routine (that is, I did not see log.Printf("Checked range %d-%d
", from, to)
in the console)
I tried lowering the range size to 5, which resulted in a few goroutines to be completed but it abruptly stopped at the range 2840-2845. I thought this might be due to the numbers getting bigger and the calculation taking more time, but this doesn't make sense as the stop is very abrupt. If this were the case I would expect the slowdown to be at least a little gradual.