## Proposed algorithm for more efficiently testing if any integer in list of integers is square

Expand Messages
• 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
Message 1 of 1 , Dec 26 8:21 AM
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
basic idea.

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@... >
Your message has been successfully submitted and would be delivered to recipients shortly.