Integer Square Roots in 6502 machine code
=========================================
A simple, but inefficient way of calculating integer square roots is to
count how many times increasing odd numbers can be subtracted from the
starting value. For example:

32-1=31 -> 31-3=28 -> 28-5=23 -> 23-7=16 -> 16-9=7 -> 7-11<0
        1          2          3          4          5

-> SQR(30)=5, remainder 7

This can be done in 6502 machine code as follows:

\ Calculate 16-bit square root
\ ----------------------------
\ On entry  num+0..num+1   = input value
\           sub+0..sub+1 = workspace
\ On exit   X = SQR(input value)
\           Y = remainder from SQR(input value)
\           A,num,sub = corrupted
\ Size      37 bytes
\
.sqr                              :\ On entry, !num=input value
LDX #1:STX sub+0:DEX:STX sub+1    :\ Initialise sub to first subtrand
                                  :\ and initialise X to SQR(0)
.sqr_loop                         :\ Repeatedly subtract increasing
SEC                               :\   odd numbers until num<0
LDA num+0:TAY:SBC sub+0:STA num+0 :\ num=num-subtrand, remainder in Y
LDA num+1:SBC sub+1:STA num+1
BCC sqr_done                      :\ num<0, all done
INX                               :\
LDA sub+0:ADC #1:STA sub+0        :\ step +2 to next odd number
BCC sqr_loop                      :\ no overflow, subtract again
INC sub+1:BNE sqr_loop            :\ INC high byte and subtract again
.sqr_done
RTS                               :\ X=root, Y=remainder
:

You can test it with:
  FOR A%=1 to 65535:!num=A%:!sub=USR sqr:PRINT A%,sub?1,sub?2:NEXT

or with:
  FOR A%=1 to 65535
    !num=A%:B%=USR sqr
    PRINT A%,(B%AND&FF00)DIV256,(B%AND&FF0000)DIV65536
  NEXT

It is simple to reduce the code to calculate roots of 8-bit numbers by
removing the code to subtract in+1. The code uses an 8-bit counter for the
root, so to calculate roots of numbers larger than 16 bits different code is
needed, as the square root of &10000 (a 17-bit number) is &100 (a 9-bit
number).