Finding Lagrange's four squares

This program implements a version of Rabin and Shallit's algorithm appears in page 6 of Pollack and Trevino's paper. It is written in Haskell and heavily depends on the newsynth library by Neil J. Ross and Peter Selinger. This algorithm is very efficient, despite some inefficiency in my codes, it finds the four 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.

For security reasons, I put a limit of 80 digits on the integer. Because someone tested a 2102 digits number which almost crashed the server. The alogrithm works efficiently for arbitary n, but for ridiculously large numbers, it still takes a noticable time. For example, a 308 digits long number takes about 2 minutes.

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

Step 2. Click Find Four Squares button

See Also

Finding Gauss-Legendre's three squares.

Opened on: 06/16/2019. Last edited on: 08/11/2019