| |
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....
|
| |
_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: 2014 |
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. :) |
| |
Graham
Account closed
Registered: Dec 2002
Posts: 990 |
@JackAsser: Rounding is not correct here since the assembler routine also gives INT(SQR(X)) and not INT(SQR(X)+0.5).
@_V_: You can calculate it as long as you don't have intermediate numbers, for example: (SIN(45°)^2) = 0.5 :)
Well and the math teacher said that pocket calculators used tables for calculation. That's definitely wrong, imagine that he said that in the 80s when a few KB was not only expensive but also biiiig :) |
| |
_V_
Account closed
Registered: Jan 2002
Posts: 124 |
Graham: You calculated sin^2(45°), not sin(45°), which is a different number. Sin(45°) is equal to sqr(2)/2. Since sqr(2) is an irrational number, sin(45°) cannot be equal to a decimal fraction or bit pattern of any kind, it can only be approached by one. The best we can do with irrational numbers is to represent them with a symbol (e, for example) or extract them from properties wherein they appear (for example, the ratio of the surface of a perfect disc and the squared radius of said disc is exactly equal to pi). In other words, we use them in an indirect way so that we don't have to use their mindboggling explicit form.
Yes, you can use a currently known algorithm to calculate sin(45°)... but only up to a certain degree of precision. If you want to determine the entire number, its real value, you'll need an infinite amount of time to do so. That's why I said that you can't *really* calculate them with such methods.
As for the 80s maths teacher and the table, he might have meant a table containing certain power series (Taylor, Lagrange, etc.) expansion coefficients which the calculator could use to calculate f(x) for a given x and f, using for example a formula like f(x) = a0+a1*x+a2*x^2+... Such a table would be small enough to fit into the calculators of that era, I reckon. If he was talking about storing the huge books filled with log-tables and stuff inside them, then no indeed :). |
| |
Graham
Account closed
Registered: Dec 2002
Posts: 990 |
No I was talking about keeping "SIN(45°)" as representation of SIN(45°), you don't always need decimals :) |
| |
_V_
Account closed
Registered: Jan 2002
Posts: 124 |
Yep, but at some point, in some formula, you'll need the numerical value of sin(45°), because it's explicitly stated in the result. And then, you'll find that you cannot calculate it exactly with the current methods, unless you're willing to wait forever :). |
| |
JackAsser
Registered: Jun 2002
Posts: 2014 |
Question is, why do you WANT the numerical exact representation. To apply it in the real world? I don't think so, at some point you'll get down to the quant angle, quant time, quant length, quant ***. So, one could argue that more decimals in PI than f.e. 1000 is irrelevant in the numerical form since they're not applicable on anything. :D And if you need that many decimals to avoid summing up rounding errors I suggest using another method than the numerical representation in the first place. |
| |
enthusi
Registered: May 2004
Posts: 677 |
this is somewhat off topic here :) but euler's 'e' is for example very much needed with greater precision than 1000 decimals since there are massive iterative computations 'using' it. Actually there is the legend about an error in 1000th place that caused the first examination of 'chaotic' behavior.
Since sin is periodic and almost always associated with geometry, I would know of no use for superprecision (well that is not the reason for my lack of knowledge but you get what I mean).
@_v_: waiting for ever wont give you the result either
in general: don't defend math teachers - they tend to know shit :) But I too thought they use small coefficent tables for some calcs - like the kernal does :)
|
| |
Graham
Account closed
Registered: Dec 2002
Posts: 990 |
Here's an extended incarnation of the integer sqrt routine. This one is extended so it does proper rounding. It is achieved by adding another iteration and calculate bit -1 which then can be used to determine if the fractional part is >= .5 or not.
The disadvantage of rounding is that the output has to be 9 bits now, because inputs $FF01 to $FFFF result in 256 now (and not 255). Alternatively you also might modify this routine and simply use bit -1 for further calculations. This gives you more accuracy than rounding.
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
; bit 0 iteration
STY THI
LDX MLO
LDA MHI
BCS .skip2
CPX #$80
SBC THI
BCC .skip3
.skip2
TXA
SBC #$80
TAX
LDA MHI
SBC THI
STA MHI
INY ; R = R OR D (D is 1 here)
.skip3
CPX #$80
ROL MHI
; bit -1 iteration and rounding ( + 0.5)
LDX #$00
BCS .skip4
CPY MHI
BCS .skip5
.skip4
INY ; R = R + 0.5
BNE .skip5
INX
.skip5
; R in X and Y (Y is low-byte)
RTS
stab: .BYTE $01,$02,$04,$08,$10,$20,$40,$80
If you don't wanna have the rounding and prefer having bit -1, then use this final iteration:
; bit -1 iteration
BCS .skip4
LDX #$00
CPY MHI
BCS .skip5
.skip4
LDX #$80
.skip5
; R in Y, X contains bit -1
RTS |
| |
_V_
Account closed
Registered: Jan 2002
Posts: 124 |
@Jackasser: I was speaking theoretically, at the moment, there is no apparent need for super-precision. Hence my prior statement, "So we settle for rational approximations which usually are sufficient for all intents and purposes". However, this may very well change in the future - there may also be procedures which only have superslow convergence, or systems of differential equations which require superprecision in order to not blow up after 2 iterations.
Quantum theory might not be the end-all of everything. Therefore, I would wait before declaring that the universe is just a collection of discrete spaces of quantum dimensions in which elementary particles hop and do their thing, and that only a limited amount of precision is all you need.
@enthusi: No, when you wait infinitely long, i.e. when you take the limit t->+Inf, you will have the exact decimal representation of the number (as decimals are countable). Remember, "infinity" is a weird thing. And, I have to defend maths teachers because I am one (actually physics, but I've given maths for a couple of years and I did have the impression that I knew what I was talking about). |
| Previous - 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 - Next |
