| |
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
|
|
| |
A Life in Hell
Account closed
Registered: May 2002
Posts: 204 |
Quote: 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
The answer is, as always, a lookup table :) |
| |
Compyx
Registered: Jan 2005
Posts: 631 |
Quote: The answer is, as always, a lookup table :)
And some logic to go with that, as a lookup-table for 16-bit fixed point numbers would be 65536 bytes, which looks an awful lot like the total memory available on a C64 :)
Look at this page: http://en.wikipedia.org/wiki/Methods_of_computing_square_roots for some information on how to approximate the square root of an arbitrary number. Some parts of the equations can be implemented as lookup-tables, other parts you'll have to implement as code.
I've done these things in the past, don't remember how I did them though, as it was a long time ago I did any 'serious' mathematics in assembly.
|
| |
WVL
Registered: Mar 2002
Posts: 902 |
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: 2014 |
@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: 677 |
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: 146 |
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: 121 |
There had also been an article in 64ér magazin about this... When still in need i will look up it...
|
... 92 posts hidden. Click here to view all posts....
|
| Previous - 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 - Next |
