# 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, (in,in+1)=input value
\ On exit,  Y=(out)=root, X=(out+1)=remainder
\ If out=in+2 this lets you use !in=value

.sqr                            :\ On entry, !in=input value
LDY #1:STY out+0:DEY:STY out+1  :\ Initialise out to first subtrand
.sqr_loop                       :\ Repeatedly subtract increasing
SEC                             :\   odd numbers until in<0
LDA in+0:TAX:SBC out+0:STA in+0 :\ in=in-subtrand, remainder in X
LDA in+1:SBC out+1:STA in+1
BCC sqr_done                    :\ in<0, all done
INY                             :\
LDA out+0:ADC #1:STA out+0      :\ step +2 to next odd number
BCC sqr_loop                    :\ no overflow, subtract again
INC out+1:BNE sqr_loop          :\ INC high byte and subtract again
.sqr_done                       :\ Y=root, X=remainder
STY out+0:STX out+1             :\ out?0=root, out?1=remainder
RTS
```

You can test this with:

```   FOR A%=1 to 65535:!in=A%:CALL sqr:P.A%,out?0,out?1:NEXT
```

or with:

```   FOR A%=1 to 65535:!in=A%:B%=USR sqr:P.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 large than 16 bits different code is needed, as the square root of &10000 (a 17-bit number) is &100 (a 9-bit number).

Jgharston 21:37, 30 August 2007 (BST)