I'm back to searching for numbers that are palindromes both in decimal and in binary. [0]
I had an insight the other day, that as I fix the n least (and most, it's a palindrome!) significant decimal digits, I also fix the remainder from division in 5^n. Let's call it R. Since I also fix by that point a bunch of least (and most) significant bits, I can subtract how much they contribute mod 5^n from R, to get the remainder from division in 5^n of the still unknown bit. The thing is, maybe it's not possible to get this specific remainder with the unknown bits, because they're too few.
So, I can prepare in advance a table of size 5^n (for one or more ns) which tells me how many bits from the middle of the palindrome I need, to get a remainder of <index mod 5^n>.
Then when I get to the aforementioned situation, all I need to do is to compare the number in the table to number of unknown bits. If the number in the table is bigger, I can prune the entire subtree.
From a little bit of testing, this seems to work, and it seems to complement my current lookup tables and not prune the same branches. It won't make a huge difference, but every little bit helps.
The important thing, though, is that I'm just happy there are still algorithmic improvements! For a long while I've been only doing engineering improvements such as more efficient tables and porting to CUDA, but since the problem is exponential, real breakthroughs have to come from a better algorithm, and I almost gave up on finding one.
I did some manual golfing with nand2tetris assembly and developed similar hacks to the max() implementation, where one appropriates an arbitrary, conveniently placed, memory address.
After reading the article, though, I feel like I definitely need a superoptimiser, to see what could be improved :)
> for this game you can throw the usual tools away...
> The reason is that Starflight was written in Forth
I recently reverse-engineered another game from the 80's, and had a similar issue because it was written with Turbo Pascal.
The different tools didn't like quirks such as data stored inline between the instructions or every library function having a different calling convention.
Turns out the simplest way to handle this was to write my own decompiler, since Turbo Pascal 3 didn't do any optimisations.
In academia, seeing your research being published by someone else sucks, but the consolation prize is that you know you had the right instincts choosing what to research.
I had an insight the other day, that as I fix the n least (and most, it's a palindrome!) significant decimal digits, I also fix the remainder from division in 5^n. Let's call it R. Since I also fix by that point a bunch of least (and most) significant bits, I can subtract how much they contribute mod 5^n from R, to get the remainder from division in 5^n of the still unknown bit. The thing is, maybe it's not possible to get this specific remainder with the unknown bits, because they're too few.
So, I can prepare in advance a table of size 5^n (for one or more ns) which tells me how many bits from the middle of the palindrome I need, to get a remainder of <index mod 5^n>.
Then when I get to the aforementioned situation, all I need to do is to compare the number in the table to number of unknown bits. If the number in the table is bigger, I can prune the entire subtree.
From a little bit of testing, this seems to work, and it seems to complement my current lookup tables and not prune the same branches. It won't make a huge difference, but every little bit helps.
The important thing, though, is that I'm just happy there are still algorithmic improvements! For a long while I've been only doing engineering improvements such as more efficient tables and porting to CUDA, but since the problem is exponential, real breakthroughs have to come from a better algorithm, and I almost gave up on finding one.
[0] https://ashdnazg.github.io/articles/22/Finding-Really-Big-Pa...
reply