Whew, hey everyone. Yes, hack-a-day is happening this year! I was a few days late starting (out of state), and then I did an assembly programming project! But then I promptly got a nasty bug and was laid up in bed for four days. Not a fast start! But that's okay, I'm feeling good.
I'm thinking this year will be AI-light to AI-none. Last year it was novel for me, this year I want a break from it. And really, hack-a-day is about learning and flow for me, as much as shiny demos.
On day 5, I decided to learn some X86-64 assembly coding. AI help was limited to an assembly cheatsheet (I didn't know assembly), and some final bugfix help after I got sick, since I was over my 1-day budget.
The problem is to solve the following equation using positive integers. As far as I know it doesn't have a specific name, although it has a short lineage: Euler conjectured no solutions, Elkies found infinitely many solutions, and Frye found the smallest by computer search.
x^4 + y^4 + z^4 = w^4
We're given the hint that there is exactly one solution with all numbers less than 1 million. I'll avoid posting the answer here, but you can find it if you follow the wikipedia link above.
The algorithm I'm using was worked out by me and Kragen Javier Sittaker (mostly Kragen), although it's been long enough I had to reinvent it. It turns out it's the same one that Frye used to solve it originally, in 1988 -- although he used a parallel implementation I don't know the details of.
Brute force search doesn't work -- one million times one million, times one million, times one million, is too many possibilities to try (10^24). So instead we make two lists, one of numbers x^4 + y^4 (in sorted order), and one of numbers w^4 - z^4 (in sorted order). And then it's easy to see if they're ever equal. Of course, those would be lists of a trillion things, so we can't make them either. We use a priority heap of a million elements, instead.
For fast testing, we hint the solver has to the right bounds for X, Y, etc. For me it takes about 4 hours for the full run.
I'm happy I got this to work! I'm sure my assembly isn't the best, since it's about my second assembly program, but I learned a little about x86 and about the intel syntax and nasm macros.
Python and x86-64 assembly versions both on github.
Next project will be something a little more chill.
Happy hacking!