[Darth-Apple]

I play around with Project Euler from time to time. These are programming problems that are designed to be difficult to solve, but not unsolvable with a modest computer hardware and a good algorithm. The trick is to come up with a good algorithm to do the job. Therein lies the problem. Algorithms are hard to design, especially if they are highly efficient.  

I usually do these in Python. I also do very easy problems, and try to optimize them as much as possible. Python, unfortunately, is an interpreted language. It does not compile to machine code. As a result, average Python code is at least 10x slower than equivalent C code, and often slower. 

That being said, my challenge to myself was to make this problem run as quickly as possible, and to make it run with relatively large numbers. This problem is based on Problem 4, but I've expanded it somewhat. Instead of using two three digit numbers to find a palindrome, it uses two numbers of arbitrary length. I've tested it with as many as 10 digits, and found that it runs in fairly reasonable time constraints. 

My python code: https://www.dropbox.com/s/hoekt73ioovwq0...me.py?dl=0

This is technically an O (10^n)^n algorithm, so it is, quite literally, doubly exponential in runtime. As the number of digits increases, the runtime increases quite severely. I have yet to find a better algorithm to do the job, so I tried to optimize the one I had as best I could. I've asked as many math majors as I could. I've looked all over the internet for better ways of approaching it. I have yet to crack the problem. It seems like trial and error is the only way to really attack it, as least as of so far. 

What this does to run faster: 

• I multithreaded this. The trick to doing this is to use processes instead of threads. This gets around the GIL lock that ordinarily prevents this, and allowed Python to properly use all available cores. 
  
• The algorithm starts by checking the largest numbers first, as it only wants the largest palindrome possible. Generally, the factors of the largest possible palindrome are very easy to find at the top of the possible number range. By starting at the top, runtime is improved significantly. 
  
• As it turns out, every single even-digit palindrome has a factor of 11. This algorithm only ever needs to check every 11th number, making it run ~11 times faster. 
  
• It runs as a loop within a loop (hence the doubly exponential time). However, it assumes that the first factor will always be the larger of the two factors, since 997 x 993 == 993 x 997. Thus, if it checks a combination of numbers, it doesn't check the reverse of this combination, which would have the same result. 
  
• If it finds a palindrome at 993 x 990, it cannot necessarily stop evaluating lower numbers. If, for example, 992 x 995 was a palindrome, it would be a higher palindrome than the first one would be. However, it has a heuristic to detect if there is possibly any higher palindrome than the highest one it has found yet, using only numbers it hasn't checked. As soon as it detects that no higher palindrome could be possible, it stops evaluating. This massively improved performance compared to the unoptimized code. 
  
• It "guesses" on possible values to find the first palindrome. The highest palindrome is almost always made up of two factors that are very near the top of the number range that is given. As a result, it does not attempt to calculate 999 * (any number from 999 to 1). It stops at 999 * (some number around 900-990, depending on settings), and then moves on to 998 * (similar range as previous iteration). 
  
• By "guessing" in the most likely range first, it almost always finds palindromes much more quickly. If "guessing" fails to find palindromes, it falls back to checking the full range. It rarely does this. There's almost always a palindrome near the top of the range. 
  
• Once it's finds the first palindrome, it can check a smaller range of numbers, since it only needs to check combinations that, when multiplied, are higher than the previous highest palindrome. As a result, this algorithm goes much faster once the first palindrome was found. (This is the reason that "cheating" and guessing on palindromes increases performance so drastically. )
  

Someone else did another deep dive into this very same problem, and posted their findings and code. I implemented very similar optimizations in my own code, with a few differences. His runs much faster than mine. He is doing it in a much better programming language for performance, and it shows. 

As much as I spent some time diving into this one, I have yet to find a faster algorithm. If anyone well-versed in math has a better solution, please give me a shout out. I'd be interested in taking suggestions and learning further ways to optimize it! 

In the meantime, happy programming. If anyone wants to see how to multithread python, take a look at my code. It really is that easy.