Re: Integer test for perfect square

Is there an integer test for a perfect square?
Henri Cohen's ... algorithm 1.7.3. ... check if
the number is a square modulo some small numbers
(11, 63, 64, 65 is suggested), then square the
integer square root.

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:

http://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.

Are you sure? Have you tested that? Newton's method
doubles the nubmer of digits on each iteration, but
the "long-division" method that I know so well only
gives one extra digit per phase. My speed tests show
integer variants of Newton's Method to be far faster
for large numbers.

In short, my results disagree with your assertion, and
I would be interested to see how your evidence comapares
with my tests.
.

Relevant Pages

  • Re: Square root algorithms and complexity
    ... > I developed an algorithm which includes multiplications,addistions, ... > and the computation of a square root. ... > number of multiplications that the algorithm performs, ... >> computing the square root using a specified algorithm? ...
    (sci.math)
  • Checking square root algorithm for portability/correctness
    ... I posted a thread on comp.programming awhile back asking about an algorithm ... I implemented on square root. ... prime number as a convenient way to get a pseudorandom number generator. ... iterations could be arbitrary. ...
    (comp.lang.c)
  • Re: Applying Poisson methods
    ... It is certainly not your algorithm. ... use of an inverse CDF and mine. ... CDF as you show, so long as it does not break. ... Take the square root of 75, to save as a constant M. ...
    (sci.stat.math)
  • Re: Square root algorithms and complexity
    ... >I developed an algorithm which includes multiplications,addistions, and the ... is using "machine precision", additions and multiplications ... may be such that part or all of the time for a square root ... >> computing the square root using a specified algorithm? ...
    (sci.math)
  • Re: Checking square root algorithm for portability/correctness
    ... > an algorithm I implemented on square root. ... > number of iterations to make. ... mask the highest eventh bit and shift the mask as you go. ... Assuming you have M value bits, your algorithm performs ...
    (comp.lang.c)