C versions?

[gtoal]

It would be interesting to also compare against algorithms expressed in C (compiled using whichever is the best compiler for the 6502).
This is the isqrt code I use on the 6809 using gcc-6809 (where divides should be avoided at all costs and multiplies minimised where sensible) when programming for the Vectrex where RAM is at a premium and lookup tables are usually avoided, to allow more code in the available EPROM space. It generates successive squares iteratively and stops when the parameter lies between one square and the next.

uint8_t IterSqrt(uint16_t b) {
  uint8_t i, j;
  uint16_t step, prev, tot, isquared, jsquared;
  if (b <= 1) return b;
  i = j = 0; isquared = prev = tot = 0; step = 1;
  for (;;) { // iterations cost cheap compared to the 5 x 16-bit divides in software needed by NewtonSqrt.
    tot += step; step += 1; jsquared = tot+prev; prev = tot;     // calculate squares incrementally using 'table of differences' method.
    if (jsquared == 0) return 255U; // overflow and loop-end test in one!
    if (b >= isquared && b < jsquared) return i;     // test plausible square root: sqrt(b) = i IF i^2 <= b < (i+1)^2
    i += 1; isquared = jsquared;
  } // loop contains two full adds, two increments, and 3 comparisons.
}

If you ever feel the urge, a similar comparison for division algorithms would be interesting and also (from a purely personal point of view) a similar survey for 6809 code (where there is a hardware MUL instruction but no divide).