| |
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....
|
| |
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: 933 |
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: 351 |
@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 |
| |
_V_
Account closed
Registered: Jan 2002
Posts: 124 |
Theoretically speaking, that math teacher wasn't completely wrong when he said you can't really calculate sines. Of course, results like sin 0° = 0 are easy and exact, but some sines are irrational numbers (sin 45°, for example), which - using methods currently known - would take forever to determine exactly. So we settle for rational approximations which usually are sufficient for all intents and purposes.
By the way, if you just enter ?SQR(26569), the V2 basic routine gives 162.999976. The INT routine seems to act like a floor function in that it just throws away the decimal part of the result. Maybe it's better to adapt the test routine so that it rounds numbers up or down - for example
1 INPUT Q : REM Q > 0
2 S = SQR(Q) : I = INT(S) : D = S - I
3 IF (D < 0.5) THEN (A = I) : GOTO 5
4 A = I + 1
5 PRINT A
? |
| |
JackAsser
Registered: Jun 2002
Posts: 1989 |
ROUND(x) == FLOOR(x+0.5) == INT(x+0.5), given x>=0 FYI.
This is also important when using fix point for example. Consider using a 8.8 value for expressing an y-coord, then to convert it into actual screen coords I've seen many examples of a simple truncation of the LSB-part. Always add by half before truncation, i.e. y'=HI(y+$0080) otherwise you introduce a 0.5 bit error which will in some cases result in jerky and jumpy motion.
@Graham: Nice work! I'm impressed. :) |
| Previous - 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 - Next |
