Re: Integer test for perfect square

On 12 Mar, 16:58, jimwa...@xxxxxxxxx wrote:
On Mar 12, 10:46 am, Jack Schmidt <Jack.Schmidt.SciM...@xxxxxxxxx>
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?

Unlikely. There is an algorithm, resembling long division,
which rapidly finds the integer floor R of the square root
of any integer N, and the remainder S, i.e. N = R^2 + S
where 0 <= S <= 2R. You can find a description of it at:

www.mathpath.org/Algor/squareroot/algor.square.root.why.htm

and on various other web sites.

The algorithm was taught in schools up until perhaps 1960,
so only quite elderly people are familiar enough with it
to just do it on automatically on paper. But it could be
expected to be the method of choice in a multiple-precision
integer package. I have implemented it several times, in
different languages. Newton's method would be much slower.
--
.

Relevant Pages

  • Re: Integer test for perfect square
    ... have a large positive integer, ... want to know if it's a perfect square, ... have floating point available. ... square root of a positive integer n, ...
    (sci.math)
  • Re: Babylonian root 2 (was: Waradpande seems to have destroyed PIE already)
    ... 'Square Root Approximations in Old Babylonian ... told me time and again that the Babylonians find the ...
    (sci.lang)
  • Re: Integer test for perfect square
    ... have a large positive integer, ... want to know if it's a perfect square, ... have floating point available. ... square root of a positive integer n, ...
    (sci.math)
  • Re: Liskov substitution principle
    ... for square root calculation, which is hard for people to write a unified ... verification function (your example, verifiesOK)? ... It means base and derive do not follow the same contract to implement square ... The magic Quake implementation for square root ...
    (microsoft.public.vc.language)
  • Re: Plausibility Check
    ... Brian Irrelephant Scott forever. ... case of the square root of 2, ... mathematicians of ancient Egypt and Mesopotamia. ...
    (sci.lang)