Algorithms



Square Root Algorithm

  1. read n, tolerance (n is number for which square root is needed)

  2. above <- n

  3. below <-1

  4. square <- ?? (what value should we use?)

  5. repeat until square-tolerance < n < square+tolerance

  6.     middle <- (above + below) ÷ 2

  7.     square <- middle x middle

  8.     if square > n then

  9.       above <- middle

  10.     else

  11.     below <- middle (end if) (end until)

  12. write middle

  13. stop


The key point to argue is termination. Clearly we must have tolerance > 0 to guarantee termination. Prove this to yourself!

[Prev][TOC][Next]

CS1104 Main Page
Last Updated 01/05/2000
© L.Heath, 2000