| |
Trifox
Account closed
Registered: Mar 2006
Posts: 108 |
calculating of square roots ?
hi all, for my newest project i am in urgent need to calculate the length of a 2d vector, reminding pythagorian math i remember that i have to calculate the roots of a fixed point (8bits.8bits) number, how can that be mastered in a convenient way ?!?!?!
thx
|
|
... 92 posts hidden. Click here to view all posts....
|
| |
WVL
Registered: Mar 2002
Posts: 886 |
Actually I do somewhat the same in pinball dreams to calculate the total speed of the ball : v=sqrt(vx^2+vy^2), now because i wanted a very high resolution, i couldnt use a lookup table.
Good thing for me was that i knew the angle vx and vy made, so i used that as a basis for my calculation (I also have a very convenient and easy way to calculate this angle!).
then you have the following equations that hold :
sin(angle)=vy/v and cos(angle)=vx/v
or, written out for v :
v=vy/sin(angle) or v=vx/cos(angle)
now, sin and cos are interesting, because they're max 1. So i can rewrite this like
v=vy*(1/sin(angle)=vy*((1/(sin(angle))-1)+vy
now, if i make use of only 45' where sin is between sqrt(2)/2 (say .5) and 1 , this means that 1/sin(angle) is between 1 and 2 and (1/sin(angle))-1 is between 0 and 1!!
So i simply have a 1 byte lookup table (0bits.8bits) with the value of (1/sin(angle))-1 and do the calculation using a simple multiplication! :) My table only has to be 32 bytes long (256 makes a complete circle, 64 makes one quarter and i only need half of that).
(you have to use 1/cos(angle)-1 if you're in the other 45' ofcourse, but you can use the same table).
I hope this helps :)
Anyway, if you need to know this for 3d vectors, I'm guessing you're approaching it from the wrong direction and you seriously need to investigate doing the calculations using matrices!
|
| |
JackAsser
Registered: Jun 2002
Posts: 1989 |
@trifox: may I ask why you need to know the length of the vector, perhaps there are otherways. The best optimization is to not do it at all. :D |
| |
Graham
Account closed
Registered: Dec 2002
Posts: 990 |
There is a binary method of calculating a square root, if you totally optimize it towards 6502 asm it is almost as fast as a binary divide routine. |
| |
Trifox
Account closed
Registered: Mar 2006
Posts: 108 |
thank you, i need i for some kind of billard simulator, and the reason why i want it to is simply to tread collisions of balls correctly ... hmm, if i ever get this done ?!??! i just got cc65 ready to handle some parts of the maths easily, especcially cross product and scalar produkt calculations is too heavy math for me on doing it directly in asm ... |
| |
enthusi
Registered: May 2004
Posts: 675 |
Since you work in C anyway...
Maybe this one?
http://www.cs.mtu.edu/~shene/COURSES/cs201/NOTES/chap04/sqrt.ht..
For 6502 it might be rather slow though but you can chose an accuracy rather simple...
This method can also be quickened quite significantly by using tables (oh, surprise). |
| |
PopMilo
Registered: Mar 2004
Posts: 145 |
Here is one way to do it from
http://www.geocities.com/oneelkruns/asm1step.html
Returns the 8-bit square root in $20 of the
16-bit number in $20 (low) and $21 (high). The
remainder is in location $21.
sqrt16 LDY #$01 ; lsby of first odd number = 1
STY $22
DEY
STY $23 ; msby of first odd number (sqrt = 0)
again SEC
LDA $20 ; save remainder in X register
TAX ; subtract odd lo from integer lo
SBC $22
STA $20
LDA $21 ; subtract odd hi from integer hi
SBC $23
STA $21 ; is subtract result negative?
BCC nomore ; no. increment square root
INY
LDA $22 ; calculate next odd number
ADC #$01
STA $22
BCC again
INC $23
JMP again
nomore STY $20 ; all done, store square root
STX $21 ; and remainder
RTS
|
| |
Trifox
Account closed
Registered: Mar 2006
Posts: 108 |
oh, i found a interresintg routine here:
http://zeus.osix.net/modules/article/?id=770
which should do exactly what i want ... ;)
|
| |
Honesty
Registered: Jan 2003
Posts: 117 |
There had also been an article in 64ér magazin about this... When still in need i will look up it...
|
| |
Graham
Account closed
Registered: Dec 2002
Posts: 990 |
GO64 had an article about this by Krill, but the routine he presented was mine. He didn't explain much about the routine and how to get to it since I didn't explain to him. :)
Anyway here comes the explanation: Imagine you wanna have a square root:
R = sqrt(N)
That obviously gives you:
R^2 = N
Since we wanna establish a convergent algo, we simply use this during calculation:
R(n)^2 <= N
R(0) will be 0. To get closer to N we add a third value D to R as long as that formula is true. Since we work with binary computers, this D will be of the kind 2^x (128, 64, 32 etc).
Ok assuming we wanna have the root from a 16 bit number and since the output of a sqrt of max 65535 (highest 16 bit input) is maximum 255.998 we start with a D of 128 and LSR it down to 1. On each iteration we try (R+D)^2 <= N and if that formula is true, we have R=R+D. If not, R stays unmodified. The resulting algo looks like this:
R = 0
D = 128
while (D >= 1)
{
temp = R+D
if (temp*temp <= N) then R=T
D = D/2
}
As you see this algo is very simple and apart from the temp*temp it does not involve any time consuming operation. The D/2 is ofcourse just a single LSR.
Ok but we are not satisfied. One single integer multiplication is too much for our little 6510 so we have to get rid of it.
(end of part 1, part 2 soon) |
| |
Cruzer
Registered: Dec 2001
Posts: 1048 |
*holds breath* |
| Previous - 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 - Next |
