Using CUDA to Find the World’s Largest Square Palindromes

In October 2022, Professor David Griffeath of UW-Madison approached me with an interesting recreational mathematics question: how efficiently could a computer find square palindromes, i.e. numbers which are perfect squares and which also read the same forwards and backwards (when written in base 10)?

There are certain infinite families of square palindromes which are well-known. For example, 11^2 = 121, 101^2 = 10201, 1001^2 = 1002001, etc. is one such family. However, there are also sporadic square palindromes (SSPs) which do not fit any kind of pattern; for example, 836^2 = 698896.

So far, there does not seem to be any algorithm to predict the occurrence of SSPs, and so we must resort to brute-force in order to find such numbers. I set out to devise an algorithm which would (relatively) efficiently find such SSPs, and created an initial multi-threaded prototype using Rust which was able to quickly find several previously-unknown square palindromes of length 49.

The algorithm is highly parallelizable, so in November 2022 I set out to make a CUDA version of it to take advantage of GPU parallelization. Shortly, a distributed effort began to find ever-larger SSPs with my algorithm, culminating in the (current) world record SSP of 67 digits – 3109885844380152888763910885950363^2 = 9671389965076056510789702463424611164243642079870156506705699831769 – found in October 2023 by Patrick de Geest of www.worldofnumbers.com using an NVIDIA RTX 4090 GPU. This massive number requires searching over 10^{16} candidates!

The program uses a custom algorithm which I developed that specifically takes advantage of the CUDA threading model to deliver extremely high speeds. I also developed a custom big-int library which uses PTX assembly to get even better speeds.

The program can be used to search for any palindromic number of the form Ax^2 + Bx + C for integers A, B, C, making it very flexible. It is now available for public use, if you want to participate in the distributed search. See details of the search here: https://www.worldofnumbers.com/distributed.htm.