Integer Square Roots in 6502 machine code
=========================================
A simple 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).