On Mar 12, 1:28 pm, Jack Schmidt <Jack.Schmidt.SciM...@gmail.com> wrote: > >>> Is there an integer test for a perfect square? Say > >>> I have a large positive integer (1000 digits), and > >>> I want to know if it's a perfect square, and I > >>> don't have floating point available. I ended up > >>> getting around this by factoring the number, but I > >>> wonder if there's a quicker way. > > >> See Henri Cohen's "A course in computational > >> algebraic number theory." Springer-Verlag, 1993. > >> ISBN 3-540-55640-0 > >>http://www.ams.org/mathscinet-getitem?mr=1228206 > > >> You want algorithm 1.7.3. Roughly speaking, you > >> first check if the number is a square modulo some > >> small numbers (11, 63, 64, 65 is suggested), then > >> square the integer square root. > > >> This is much faster than factoring. > > > I guess Cohen outlines a way to find the integer > > square root without using floating point? Some form > > of Newton's method? > > Yes, algorithm 1.7.1 is integer square root, and yes > it is similar to Newton iteration. To find the floor > of the square root of a positive integer n, use: > 1. x = n (or any number larger than sqrt(n) ) > 2. y = floor( (x + floor(n/x))/2 ) > 3. if y < x, set x = y and goto 2, otherwise return x
Thanks! With you hints, I was able to get the following Python code to work. It avoids floating point, but the intermediate numbers get large.