Sunday, June 22, 2008

An update on sqrtRounded

Nicolas Cellier posted the following solution to the sqrtRounded question from a while ago.

    Integer>>sqrtRounded

      | x |
      x := self sqrtTruncated.
      ^x squared + x - self >= 0
        ifTrue: [x]
        ifFalse: [x + 1]

That is an interesting approach indeed. I did something similar to Nicolas' initial derivations... here it is.

    Integer>>sqrtRounded

      | sqrtFloor |
      sqrtFloor := (self * 4) sqrtFloor.
      ^sqrtFloor // 2 + (sqrtFloor \\ 2)

This can also be rewritten so that there are no multiplications or divisions. Isn't it beautiful? :)

I put this as an additional exercise in the hash book. There remain several issues to address even if anybody is willing to believe the code is correct.
  • I gave no proof that it is correct. I can say however that if the code is beautiful, then the proof is doubly so.
  • With floating point numbers, the rounding behavior for numbers of the form k + (1/2) is an issue. Should the FPU round always up, always down, at random, or with some other criteria in those cases? This is a thorny issue that appears nowhere in the code. Why?
Seriously, who needs a DVD player on a long drive... I don't get it.

No comments: