| |
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....
|
| |
Steppe
Registered: Jan 2002
Posts: 1510 |
Math teacher? :-) |
| |
_V_
Account closed
Registered: Jan 2002
Posts: 124 |
Here's a weird lookup table idea:
sqrt(x) = x^(1/2)
so
ln(sqrt(x)) = ln(x^(1/2)) = (1/2)*ln(x)
In other words, to calculate the sqrt of x, I would
1) look up ln(x) in an x/ln(x)-table
2) ROR ln(x)
3) search for the ROR'ed value in the x/ln(x)-table and check which x value corresponds to it
4) print out sqrt(x) :)
Forgive me if this is already featured in one of the linked articles. I also have no idea whether this is fast or not, or if a good x/ln(x) table for this fits into 64k, etc... |
| |
Cruzer
Registered: Dec 2001
Posts: 1048 |
Math professor? |
| |
Graham
Account closed
Registered: Dec 2002
Posts: 990 |
Heh, math teachers usually don't have too much math skills. I remember a math teacher who said that it was impossible to calculate a sinus and all the small pocket calculators had big lookup tables inside :D
PS. Oh and I noticed a small mistake in the routine. It's input is max. 14 or 15 bits and not full 16 due to some overflow stuff I had not taken into account earlier. |
| |
Hein
Registered: Apr 2004
Posts: 939 |
Those teachers don't teach at university, do they? |
| |
Trifox
Account closed
Registered: Mar 2006
Posts: 108 |
great suggestions, but what is with my fixed point number ?!?!
can i use this kind of algo on a 16 bit number and treat the result as a fixed point 8bit.8bit float value ? i think that would be faar too easy ... ;( |
| |
Graham
Account closed
Registered: Dec 2002
Posts: 990 |
Fixed point is pretty simple: Just increase iteration count and extend all the variables to fixed point. Currently D counts from 2^7 to 2^0 but you can continue with 2^(-1) etc. Not a problem. |
| |
Monte Carlos
Registered: Jun 2004
Posts: 355 |
@trifox
look in the user contributions section of the cc65 homepage.
there should be a file sqrtv1.0.zip
i wrote this after the last csdb discussion about calculating sqareroots. Perhaps it helps
Monte Carlos
|
| |
Graham
Account closed
Registered: Dec 2002
Posts: 990 |
Ok guys, I finally tested the routine I did up there. Like said before, it only allows 14 bit input ($0000 to $41FF to be more accurate). The reason for this is that M needs one more bit. Ok, some people might want full 16 bit so here is a fixed routine which only has 3 opcodes more:
LDY #$00 ; R = 0
LDX #$07
CLC ; clear bit 16 of M
.loop
TYA
ORA stab-1,X
STA THI ; (R ASL 8) | (D ASL 7)
LDA MHI
BCS .skip0 ; M >= 65536? then T <= M is always true
CMP THI
BCC .skip1 ; T <= M
.skip0
SBC THI
STA MHI ; M = M - T
TYA
ORA stab,x
TAY ; R = R OR D
.skip1
ASL MLO
ROL MHI ; M = M ASL 1
DEX
BNE .loop
; last iteration
BCS .skip2
STY THI
LDA MLO
CMP #$80
LDA MHI
SBC THI
BCC .skip3
.skip2
INY ; R = R OR D (D is 1 here)
.skip3
RTS
stab: .BYTE $01,$02,$04,$08,$10,$20,$40,$80
This routine works perfectly for all values from $0000 to $FFFF. It even works better than BASIC V2 math which for example fails at INT(SQR(X)) sometimes :)
In fact, my small BASIC program which was supposed to test the assembler sqrt routine failed at value 26569. It returned 162 there although 163*163 = 26569, so it said that my asm routine had failed although it was the BASIC V2 math routines which had failed :D |
| |
enthusi
Registered: May 2004
Posts: 675 |
maybe someone can sue MS for that |
| Previous - 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 - Next |
