Loading ...
Sorry, an error occurred while loading the content.

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

Expand Messages
  • Kermit Rose
    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, 2007
    • 0 Attachment
      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.