| ??? 07/26/02 20:50 Read: times |
#26380 - RE: floating point - Improper fractions? |
Hi
I tried this and it worked well in my case. Represent all numbers as 3 units: X,Y and Z, where the value of the number is given by X + Y/Z. Using this I could highly optimize my extensive calculations to fit into the limited ROM. You can also optimize by limiting the size in bytes of X,Y and Z as per their practically maximum possible values. Another advantage of this method is that with repeated divisions, one could extend the resolution indefinitely. However, I realize that this is not the most suitable solution, as multi-byte divisions are still not properly accounted for. You can still try another trick I used and represent your values as 2 units, X and Y where the value is given as X.Y This method is the same as the first, except that Z is assumed to be some constant multiple of 10, depending on your required resolution. This makes additions and subtractions very easy, but is not suitable for multiplication/division. Multiplication would have to be done using the factor method suggested by Lance, where Z gives the factor. Addition: X1.Y1 + X2.Y2 (for factor Z) = (X1+X2).(Y1+Y2) ;if (Y1+Y2 < Z) or = (X1+X2+1).(Y1+Y2-Z) ;if (Y1+Y2 > Z) Multiplication: Product = X1.Y1 * X2.Y2 = (X1 + Y1/Z1)*(X2 + Y2/Z2) = ((X1*Z1 + Y1)*(X2*Z2 + Y2))/(Z1*Z2) or even = X1*X2 + X2*Y1/Z1 + X1*Y2/Z2 + (Y1Y2)/(Z1Z2) if Z1=Z2=Z = X1*X2 + (X2*Y1 + X1*Y2)/Z + (Y1*Y2)/(Z^2) Let P = X1*X2, Q = (X2*Y1 + X1*Y2) and R = (Y1*Y2) hence product = P + Q/Z + R/Z^2 which is approximately = P.Q ; if Q < Z or = (P+1).(Q-Z) ; if Q > Z R/Z^2 would be neglible and should not be considered unless R > Z^2. Try this operation on paper with,say, 10.234 and 145.003, where Z = 1000. You'll see how easily it works out with only multi-byte multiplications and additions, without any real multi-byte divisions, which is really the only bad part of the 16-bit math library. :-) You can avoid unnecessary calculations by checking for zeroes before any operation. Unfortunately I cannot suggest any way to avoid 16 bit divisions if they do show up. Division: Div = X1.Y1 / X2.Y2 = (X1 + Y1/Z1)/(X2 + Y2/Z2) = (X1*Z1 + Y1)/Z1 / (X2*Z2 + Y2) /Z2 If Z1= Z2 = Z Div = (X1*Z + Y1) / (X2*Z + Y2) = A/B say If you really need to do optimized multi-byte divisions, try this reeeeally screwed up and convoluted method... :-)) 1)Keep left-shifting P and Q until they are both 8-bit values, say A' and B'. A faster but less accurate way would be to simply truncate all but the most significant bytes in both values. 2)Find Q' = A'/B'. Q' is an approximate value for your quotient. 3)now ... do { R' = A - (Q'*B) Q'++ } while(R' > B) // this loop should ideally run only once...twice maximum final value of Q' = actual value of quotient = Q. Remainder R = A-(Q*B) And hence you have your final value of the result as Q + R/B, the improper fraction format. There you have it, a some-what optimized 16-bit division sub routine using the 8-bit division opcodes and 16-bit add/sub operations. Of course, to convert the R/B term into the BCD representation of the decimal part of the number would be: for(int n=0; n<resolution; n++) { Q1 = quotient of R*10/B posn[n] = Q1 R = remainder of R*10/B } As 'resolution' can be any required number, this is what I meant by being able to incease resolution indefinitely. If R*10/B is a multibyte division, you can use the same method described above!! Wow, talk about complications... Don't laugh!! I actually did most of this in assembly due to severe constraints, expanded it for a 32-bit/16-bit division and generated a code that was shorter than the output of a cross-compiler!! :-)) It'll be useful if you devise a 16-bit/ 8-bit division routine to supplement your 8-bit division opcode... it's not difficult. I believe that as long as divisions aren't a concern, this is actually a good solution to your and most other floating point problems. Do forgive me if I just made this nothing more than a confusing mess!! :-)) Awaiting any criticisms/ comments/ corrections for my method... kundi |



