Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Integer test for perfect square
Replies: 20   Last Post: Mar 13, 2009 12:54 PM

 Messages: [ Previous | Next ]
 jimward2@gmail.com Posts: 7 Registered: 3/12/09
Re: Integer test for perfect square
Posted: Mar 12, 2009 4:26 PM

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.

#! /usr/bin/python

# This module determines if an integer is a perfect square.
# See: http://en.wikipedia.org/wiki/Integer_square_root

import math

for test in range(1, 1001):
# X_k = old_num / old_den

old_num = test
old_den = 1

while 1:
# X_k+1 = 1 / 2 * (X_k + (test / X_k))

new_num = (old_num * old_num) + (old_den * old_den * test)
new_den = 2 * old_num * old_den

# Not strictly necessary, but helps to reduce new_num and
new_den.
# Use the Euclidean algorithm to find the gcd of new_num /
new_den
# From: http://en.wikipedia.org/wiki/Euclidean_algorithm

gcd = new_num
b = new_den

while b != 0:
t = b
b = gcd % b
gcd = t

new_num /= gcd
new_den /= gcd

# Test for abs(X_k+1 - X_k) <= 1

left_side = (new_num * old_den) - (new_den * old_num)
right_side = old_den * new_den

if(left_side > 0):
if(right_side > 0):
if(left_side < right_side):
break
elif(left_side < -right_side):
break
elif(left_side < 0):
if(right_side > 0):
if(-left_side < right_side):
break
elif(-left_side < -right_side):
break
else: # left_side is 0
break

# Not done yet, continue with X_k+1 as X_k

old_num = new_num
old_den = new_den

# The integer square root in new_num / new_den.
# Check to see if a perfect square.

floor = new_num / new_den

if (floor * floor) == test:
print test, "is a perfect square"

Date Subject Author
3/12/09 jimward2@gmail.com
3/12/09 Jack Schmidt
3/12/09 Bill Dubuque
3/12/09 jimward2@gmail.com
3/12/09 Jack Schmidt
3/12/09 jimward2@gmail.com
3/12/09 riderofgiraffes
3/12/09 riderofgiraffes
3/12/09 Jack Schmidt
3/13/09 waste of time
3/13/09 jimward2@gmail.com
3/13/09 bert
3/12/09 mensanator
3/12/09 bert
3/12/09 riderofgiraffes
3/12/09 Tim Smith
3/12/09 Herman Rubin
3/13/09 bert
3/12/09 b92057@yahoo.com
3/12/09 Robert Israel
3/13/09 Michael Stemper