On Mar 12, 10:46 am, 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-0http://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?