Proposed algorithm for more efficiently testing if any integer in list of integers is square
- Let x1, x2, . . ., xm, be a list of positive integers in increasing order.
The following algorithm is proposed for testing if any of the x1,x2,. .
. xm are squares.
In case I made a mistake describing the pseudo code, I describe the
Generate the list of squares, starting with the first square not less
than x1, and compare with the x1, x2, . . . xm by
a merge operation to see if any x_k is in the list of squares.
The list of squares is generated sequentially by making use of the formula
1 + 3 + 5 + 7 + . . . + (2 * n - 1) = n^2
compute r = sqrt(x1)
compute j = 2 * r - 1
compute k = 1
compute t = r * r
if t = x1 then x1 is square
Loop while (k < m):
j = j + 2
r = r + j
while (x_k < r) and ( k < m) :
k = k + 1
if x_k == r; x_k is square
Kermit Rose < kermit@... >