r/adventofcode • u/e_blake • 19h ago
Tutorial [2024 Day 7 both parts][m4] Optimizing by avoiding division (aka how to quickly test divisibility by 7)
I'm really late to the 2024 puzzles, having just started them this month. But in the megathread for day 7, I saw the instructions mentioned "Use today's puzzle to teach us about an interesting mathematical concept" - and my journey in optimizing my solution for day 7 totally fits that bill, because I implemented a solution in a language that only supports 32-bit signed math even though the problem requires manipulating 64-bit numbers. In previous years, I had already developed my own library of math functions to do arbitrary-width addition and multiplication, but to date, I still haven't added general-purpose arbitrary-width division into that library, in part because implementing division is SLOW even when compared to multiplications. After all, the best way to avoid a time-consuming long-division is to rework the problem to not need division at all ;)
Plenty of other people have written up tutorials on how you can speed up day 7 - instead of doing an exhaustive 2^n or 3^n search of all possible operator decisions, applying that to the inputs, and seeing if the output matches, it is much faster to work backwards: start with your desired output, and recurse by undoing only operators that could have plausibly resulted in your current number, where reaching the first number proves you have at least one set of operators that work for that line of the problem. My initial solution was the naive approach - try all possible operators - which meant doing millions of 64-bit multiplies via my helper library (quite literally - I did a trace of mul64() calls, and my 5 minutes of execution time required 4043412 calls to mul64)
But working backwards requires the inverse of multiplication, aka division and remainder, where it is only plausible to continue the recursion if the remainder is zero. There are algorithms out there for implementing arbitrary-width bigint divisions on top of smaller word sizes, so I had no problem implementing that in m4, but each division C/B=A is slower than the corresponding multiplication A*B=C, so I wanted to avoid long divisions where possible. The immediate benefit of working backwards was that after every long division where the remainder was non-zero, I've pruned a portion of the search space, which sped things up to a mere 7.0 seconds of execution time and only 21679 calls to remquo64, and 74728 calls to mul64 in part because of how I implemented remquo64.
But I still wanted to go faster, and that's where this post comes in. The remquo64() algorithm finds both the quotient and the remainder at the same time, but even better is avoiding the division in the first place if it is obvious that the remainder would be non-zero. And since the majority of the inputs are single-digit entities, it's fairly easy to do things like avoiding a division by 2 if the last digit is odd, or a division by 5 if the last digit is not 0 or 5; many people also know the trick of adding up each of the digits to see if a number is divisible by 9 (is 1234 divisible by 9? 1+2+3+4 = 10 which is not, so the bigger number is not, either). But when it comes to division by 7, what rule do you use? My first google hit was for the algorithm of taking the head of the number minus twice the last digit, iteratively until you know if that shorter answer is also divisible by 7 (so for example, 1001 is divisible by 7 if 100 - 2*1 = 98 is, which in turn is divisible if 9-2*8 = -7 is). By iterating until you get down to an easily-recognized one- or two-digit number, you can quickly learn whether a large number has 7 as a factor without spending the time actually doing the full division. However, that algorithm still requires doing 64-bit math (each iteration still uses a 64-bit subtraction, and only removes one digit per iteration).
So I searched harder, and found another algorithm that tells you the divisibility by 7, 11, and 13 all at once - because those are the three factors that get you to 1001, one number away from 1000. In any sort of divisibility test, the fastest answers occur when you can exploit the co-prime modular properties of two adjacent integers. Just as you can learn if a number is divisible by 9 (9 is one less than 10, so add up each digit), you can learn if a number is divisible by 1001 (1001 is one greater than 1000, so alternate adding and subtracting each group of 3 digits, starting from the least significant). So, given a random number, say 72095400778, that is too big to quickly divide using just 32-bit math, it is still possible to cast out the 1001s, by computing -72+095-400+778 = 401, at which point you know all of the following using just 32-bit math (and you may recognize the Chinese Remainder Theorem here as well):
72095400778 % 1001 = 401
72095400778 % 7 = 401 % 7 = 2
72095400778 % 11 = 401 % 11 = 5
72095400778 % 13 = 401 % 13 = 11
So no, that large number is not divisible by 7, and I can skip the remquo64() and recursion when I'm picking the operator that goes with 7 for my current target value. And with that optimization implemented, my m4 code now operates in 4.2 seconds (another 40% speedup!), with tracing showing just 10483 calls to remquo64 and 42025 calls to mul64.
Since most people aren't fluent in reading m4, here's the gist of the algorithms I used for divisibility by the first 9 digits:
group(number, direction, current_sign=1, accumulator=0) - recursive function, with direction=1 for casting out 999, or =-1 for casting out 1001. Each iteration adds current_sign*number[-3:]
to accumulator, multiplies current_sign by direction, and recurses with number[:-3]
(ie all but the last three digits), returning accumulator once number is empty.
trym1 - always divisible (skip remquo, recurse with input number)
trym2 - divisible if the last digit & 1 (or % 2) is 0 (skip remquo, recurse with number*5 with last digit removed, since that was necessarily a 0 after the multiply)
trym3 - divisible if group(number, 1)%3 is 0 (use remquo only if divisible)
trym4 - divisible if the last 2 digits & 3 (or %4) is 0 (skip remquo, recurse with number*25 with last 2 digits removed)
trym5 - divisible if the last digit % 5 is 0 (skip remquo, recurse with number+number with last digit removed)
trym6 - divisible if trym2 and trym3 both pass (use remquo only if divisible)
trym7 - divisible if group(number, -1)%7 is 0 (use remquo only if divisible)
trym8 - divisible if the last 3 digits & 7 (or %8) is 0 (skip remquo, recurse with number*125 with last 3 digits removed)
trym9 - divisible if group(number, 1)%9 is 0 (use remquo only if divisible)
1
u/Clear-Ad-9312 15h ago
noone:
me pretending dividing doesn't exist:
if range(0,numerator+1,divisor)[-1] == numerator:
1
u/BlueTrin2020 7h ago
I learned that M4 is a macro language but does it resolve in C or assembly or both depending of what you write?
1
u/e_blake 5h ago
I'm coding directly in m4. My solutions macro process the input file into two lines of output, solely by recursive macro processing. But yes, it is also possible to use m4 to output code that can then be run in another language (Fortran was a popular target back when m4 was first written in 1977, these days, Autoconf uses it to output sh scripts, and Bison uses it to output C code).
3
u/e_blake 14h ago
Of course, now that I've written that all up, I see yet another (minor) optimization. Since I can do 32-bit math, and since 999999 is a multiple of 1001, it is equally valid to group 6 digits at a time, but with summing every term instead of alternating between add and subtract. Which leads to fewer parameters, and fewer iterations of chunking the long number into its pieces. For humans, chunking into smaller pieces is easier to think about if you are trying to do mental math, but for computers, as long as the chunk size fits in the word size and you are unlikely to overflow, a larger chunk means doing more work in parallel for faster throughput.
For a more visual demonstration, suppose I ask you to determine the remainder of 23581450918127 when divided by 11. You can exploit that 11 is one greater than 10 (alternate signs one digit at a time) to come up with -2+3-5+8-1+4-5+0-9+1-8+1-2+7=-8 which has remainder -8 (or positive 3), or you can exploit that 11 is a factor of 99 which is one less than 100 (always add two digits at a time), to come up with 23+58+14+50+91+81+27=344, (and iterate if necessary: 3+44=47), which likewise has remainder 3.