Automating Advent of Code 2017 Day 23 Part 2

After thinking about it for a while, here's what I came up with as a series of semi-plausible automated compiler optimizations that would untangle the Day 23 inner loop.

Let's start with the raw loop. I wrote it in Go, because reasons. The f flag is set to false iff b is composite. This is what I call "trial multiplication": try every product 2..b-1 × 2..b-1 to see if it is b.

f := true
d := 2
for {
        e := 2
        for {
                if d * e == b {
                        f = false
                }
                e++
                if e == b {
                        break
                }
        }
        d++
        if d == b {
                break
        }
}

First, an easy optimization: f is monotonic inside the loop, so break all the way out anytime it becomes false.

f := true
d := 2
for {
        e := 2
        for {
                if d * e == b {
                        f = false
                        break
                }
                e++
                if e == b {
                        break
                }
        }
        if f == false {
                break
        }
        d++
        if d == b {
                break
        }
}

Second, note that we treat every product twice: d=a,e=b and also d=b,e=a . Break that symmetry by starting e at d.

f := true
d := 2
for {
        e := d
        for {
                if d * e == b {
                        f = false
                        break
                }
                e++
                if e == b {
                        break
                }
        }
        if f == false {
                break
        }
        d++
        if d == b {
                break
        }
}

Now note that the inner loop takes products in strictly increasing order. There's no point in continuing to test after the product gets bigger than b. This also gets us out of the inner-loop end test, which is subsumed. It also means that the outer loop will run a bunch of times at the end with the inner loop executing just once.

f := true
d := 2
for {
        e := d
        for {
                t := d * e
                if t >= b {
                        if t == b {
                                f = false
                        }
                        break
                }
                e++
        }
        if f == false {
                break
        }
        d++
        if d == b {
                break
        }
}

Finally, we really needn't start e so low. The lowest it could be is b div d. If this is less than d, we have already covered this case.

f := true
d := 2
for {
        e := b / d
        if e < d {
                break
        }
        for {
                t := d * e
                if t >= b {
                        if t == b {
                                f = false
                        }
                        break
                }
                e++
        }
        if f == false {
                break
        }
        d++
        if d == b {
                break
        }
}

This is plenty fast enough: my Go implementation runs on my test input in around 5 ms.

We can go faster, though. The last optimization to find is the toughest. We have now bounded e below by b div d and above by b div d + d, the latter because of the product condition. The only way this product can come out even is if d divides b, so we can replace the whole inner loop with a modulus.

f := true
d := 2
for {
        e := b / d
        if e < d {
                break
        }
        if d % b == 0 {
                f = false
                break
        }
        d++
        if d == b {
                break
        }
}

Now we have pretty much bog-standard trial division. My Go code runs in around 2ms.

BartMassey/aoc2017day23p2-optimize.md

Automating Advent of Code 2017 Day 23 Part 2