One way to form almost a circle is by the circle algorithm described in HAKMEM; only addition, subtraction, and right-shifts, are needed. Depending on what needs to be done, this might be sufficient (you will still have to write in yourself the programming for dealing with positive/negative). (I suggest making the "epsilon" parameter to be 1/256 if programming it on 6502; now you do not even need shifts.) This might not be sufficient for what you need though (but see what Bregalad wrote for homing projectiles), however I mention it in case it is useful to you or anyone else for some other purpose.

Circle algorithm is:

Code: Select all

```
NEW_X = OLD_X - EPSILON * OLD_Y
NEW_Y = OLD_Y + EPSILON * NEW_X
```

For multiplication, one algorithm is "quarter square" algorithm (there is also the Russian algorithm, which is slower, but does not require a lookup table). By a bit of algebra, it can be seen that ((x+y)

^{2}-(x-y)

^{2})/4=xy (when I learned about this algorithm, my first idea was to do such algebra in order to see that). You can round down (x+y)

^{2}/4 and (x-y)

^{2}/4 and it will still work. Therefore, you can store the quarter of the square of the numbers in a lookup table, and then look up (x+y) and (x-y) and subtract them. You can also use it with 16-bit numbers, you can consider the two numbers to multiply as (256a+b) and (256c+d) and then (256a+b)(256c+d)=65536ac+256bc+256ad+cd and if you keep only the low 16-bits (i.e. modulo 65536), same as 256(bc+ad)+cd.

Dwedit wrote:There was that integer square root algorithm where you subtract 1, 3, 5, 7, 9... then the number of times you subtracted was the square root.

While I have never heard of this algorithm before, it does make sense. The sum of (2x-1) for x from 1 to n equals n squared, so if you subtract such numbers to form part of the sequence then you can make the square root.