
Re: Integer test for perfect square
Posted:
Mar 12, 2009 12:58 PM


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." SpringerVerlag, 1993. ISBN 3540556400http://www.ams.org/mathscinetgetitem?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?

