How to quickly check if some huge number (from 100 digits) is the square of an integer?

Question

Mathematics

How to quickly check if some huge number (from 100 digits) is the square of an integer?

Answer 1

You can try to calculate the root with a fast algorithm . But it's difficult there. Google Karatsuba square root. There are open implementations . There is another infernal method through the fast Fourier transform, try to google it too.
An easier to implement, but less fast method for calculating the root is binary search. Store l, r, l^2, r^2 and lr. From these numbers, you can calculate m=(l+r)/2, m^2, m*l, m*r without long multiplications, but only by adding long numbers and dividing by 2. You need to maintain that l^2 <= n <= r^2. Initially, you can make l=1, r=10^51 (or more - half the length of the input number + a little, so that the square is exactly greater than n), then divide the segment in half and discard the unnecessary half.
There is also a probabilistic method through the symbolLegendre / Jacobi . This will be the fastest method.
It's like looking at the last digit. Squares can give 0, 1, 4, 9, 6, 5 there. But there is not a single square that ends in 2. That is. if the number ends in 2, then you can immediately say that it is not a square. We took the remainder of 10 (the last digit) and saw which ones are good. Here is the Legendre symbol - this is such a check for the modulus for any prime number (not 10).
If we take some prime number p, then n can be a square only if the Legendre symbol (n / p) is equal to 1 or 0 (Scientifically: n - must be a quadratic residue).
If we take small (<64-bit) prime numbers, then we can count n%p as a line and then calculate the Legendre symbol (n%p/p) using the algorithmthrough the Jacobi symbol in O(log(p)^2). When the Legendre symbol was calculated and if it is -1, then n is definitely not a root.
The problem here is that this is a necessary but insufficient criterion - if you get -1 for some p - then this is definitely not a square. But perhaps you can pick up a number that all your tests will give 1, and it is not a square. Therefore, it is necessary to take a lot of prime numbers. Let's say 20. It is also desirable to take large enough numbers. But you don't have to look for them every time, you can hardcode them. A rough estimate says that the error probability of such an algorithm is 2^(-number of primes).
Those. take a lot of prime numbers. Count for each n%p by dividing a large number by a short one (one pass through the array of digits). Then count the Legendre symbol. If you get -1 somewhere, then it's definitely not a square. Otherwise - most likely a square.
It is possible to combine the probabilistic test and the calculation of the root. First, check a couple of primes for the Legendre symbol to cut off definitely not squares. You can also check the last digit, it's very cheap. If not cut off, then consider the root. This will always work correctly but will be faster in some cases.

Answer 2

Well, if it is very fast, you need to pre-calculate the desired range, and then check it using the map.

Answer 3

Quick root , or rather check the processor for a similar instruction. In other words, fast != simple != accurate, etc., and speed is measured in cycles, so such algorithms have little to do with mathematics.
Another approach is a table or dictionary, i.e. cache of precomputed roots. This way you can transfer the calculation problem to the search problem (see hash tables, trees, sorting, graphs, etc.).
And if we are talking about mathematics, then here you can use the properties of numbers (for example, a square cannot end in 7 or 3) + checking for prime numbers.

Answer 4

Newton's method