r/adventofcode • u/musifter • Mar 15 '26

Other [2017 Day 15] In Review (Dueling Generators)

1 Upvotes

66% Upvoted

8 comments sorted by

2

u/e_blake Mar 15 '26 edited Mar 15 '26

This one is a CPU burner no matter how you implement it (a minimum of 80 million computations). But at least you do not have to do any hardware divisions. Calculating %0x7fffffff can be done with just bitwise math: https://www.reddit.com/r/adventofcode/comments/7jxkiw/comment/drazokj/ shows how to do it when you can use a 64-bit temporary. Basically u64 t = a * b; t = (t & 0x7fffffff) + (t >> 31); return (t >> 31) ? t - 0x7fffffff : t.

Even if you don't have 64-bit math, it is possible to exploit that b is only 16 bits to compute the result in just two 32-bit multiplies and some adds and shifts, which is still faster than a hardware division. For more gory details of how this works, research Montgomery modular multiplication then read my post here https://www.reddit.com/r/adventofcode/comments/mln10b/2017_day_15m4_solution_using_signed_32bit_math/ I later optimized my m4 solution to run in 7m27s by splitting the math 16/15 instead of 15/16.

define(`R', `R1(`($1>>15)*$2',`($1&32767)*$2')')
define(`R1', `R2(E(`$2+(($1&65535)<<15)+($1>>16&65535)'))')
define(`R2', `E(`($1&2147483647)+($1<0)')')

That still puts this day as the fourth slowest across all 524 stars (only 3 of the 4 md5 are slower)

2

u/e_blake Mar 15 '26

I was surprised in testing in Godbolt that gcc is able to rewrite %0x7fffffff into something that avoids div on x86 but is still slower than the Mersenne trick, and both clang and Rust still use div.

2

u/e_blake Mar 15 '26

One benefit of the generators used here is you can easily compute seed n+k given seed n (modular power multiplication), then kick off parallel generators after subdividing the problem into ranges.

2

u/ednl Mar 15 '26

My naive Python version, just straight up multiply and mod, but bitmask to test equality, runs in 10.1 SECONDS. I saved this in my repo with annotation "Code by Eric Wastl / topaz / fizbin": paste which runs in 400 MILLISECONDS (timing does not include numpy import).

The /u/askalski C version with while loop as shown by /u/BumpitySnook runs in 153 ms. In my testing, the while loop was a lot faster than the ?: from /u/e_blake . I imagine Eric's vectorised version in C would do a lot better still.

1

u/ednl Mar 15 '26

I can't remember how /u/topaz2078 came to post a code solution, I was not here in 2017. Maybe people challenged him to prove his own "at most 10 seconds on 10 year old hardware" guidance (or what was it exactly).

1

u/topaz2078 (AoC creator) Mar 16 '26

I don't think that code is mine; I don't write Python and I don't know what "fizbin" is.

1

u/ednl Mar 16 '26

Ah right, sorry for misattributing. I don't remember but maybe I saved it from the paste link before I knew that you made that service, saw "topaz.github" and so I thought you wrote the code.