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

