Finding Gauss-Legendre's three squares

This program implements a randomized algorithm in Pollack and Schorn's paper. This algorithm is very efficient, despite some inefficiency in my codes, it finds the three squares of very large numbers almost instantly. You can run a big number (say filling up all the blank below) to see how fast it is. In my test, a 500 digits long integer takes about 1 minute.

Of all the non-negative integers, 5/6 of them can be written as a sum of three squares. If you happend to hit one that cannot be done, then that number plus one definitely can. For security reasons, I put a limit of 80 digits on the input integer.

Speical thanks goes to Rasoul@UNB for sharing access of one key reference paper the algorithm depends on.

Step 1. Input a positive integer which you want to decompose to three squares

Step 2. Click Find Three Squares button

See Also

Finding Lagrange's four squares.

Opened on: 08/03/2019. Last edited on: 10/19/2019