Archived

This topic is now archived and is closed to further replies.

Arek the Absolute

The math is right...

Recommended Posts


  
#include <iostream.h>
#include "sinlut.h" // contains arrays SIN and COS, each are
                    // signed longs, fixed point containing 16 bits

                    // of fractional data


int main(){

	long pointx = 20<<16, pointy = 20<<16;
        cout << pointx << " " << pointy << endl;
	long angle = 0;
	long newx = ((pointx*COS[angle]) - (pointy*SIN[angle]))>>16;
	long newy = ((pointy*COS[angle]) + (pointx*SIN[angle]))>>16;
	pointx = newx;
	pointy = newy;

	cout << pointx << " " << pointy << endl;

	return(0);

}
  
What''s wrong with this? The output is: 1310720 1310720 0 0 That would imply right there that something in my equation for newx and newy messes up the number. Well, that''s why I tried this version of the same thing:
  
#include <iostream.h>
#include "sinlut.h" // contains arrays SIN and COS, each are
                    // signed longs, fixed point containing 16 bits

                    // of fractional data


int main(){

	long pointx = 20, pointy = 20;
	long angle = 0;
	long newx = ((pointx*COS[angle]) - (pointy*SIN[angle]))>>16;
	long newy = ((pointy*COS[angle]) + (pointx*SIN[angle]))>>16;
	pointx = newx;
	pointy = newy;

	cout << pointx << " " << pointy << endl;

	return(0);

}
  
The output? 20 20 So at the very least, it doesn''t seem to be my equation causing the trouble. All the SIN and COS tables are is: const long SIN[] = {/* all numbers are sin(angle)*65536 */}; Considering I take care of this in the newx and newy equations, I don''t see why this is a problem. It seems almost like I''m shifting all the data out of the number, but if a long is 32 bits, that doesn''t seem to make sense. Am I just missing something stupid? And don''t ask why I''m using fixed point math. I have my reasons. -Arek the Absolute

Share this post


Link to post
Share on other sites
cant use fixed point with fully understanding how/why it works

after i show you why it dont work you will likly hit yourself, heh. i iwll just hosw newx calcs, since newy is the same.

long pointx = 20<<16;
long pointy = 20<<16;
long newx = ((pointx*COS[0]) - (pointy*SIN[angle]))>>16;

so far so good we have:

20/65535
COS[0]/65535
SIN[0]/65535
20/65535 (ie pointy)

(20*COS[0])/(65535*65535) - (20*SIN[0])/(65535*65535)

(20*1)/(65535*65535) - (20*0)/(65535*65535)

(20)/(65535*65535) - (0)/(65535*65535)

(20-0)/(65535*65535)

20/(65535*65535)

nothing fancy yet, just standard math.

oops, we have two 65535s in the divsor. thats not good. we should only have one. multiplications as you can see increase the divsor thus you need a shift of 32 now instead of 16. since you mulitplied your SIN and COS table values by 65535/65535 AND you multipled your pointx and pointy by 65535/65535.

in fact if you take 1310720 and shift it by 16 (or divide by 65535) you get: 20.000305180437933928435187304494
which get truncated to 20 since its a long. crazy, its the right answer.

basically your doing the fixed point wrong. you dont need to mul pointx by anything. the mul is merely to perserve accuracy.

doing 20*0.5 is not viable in fixed point. so we mul the fraction by some value to make it whole and keep accuracy. 0.5*100=50.

20*50/100 = 1000/100 = 10

if the value has no fraction you dont need to mul by one (since estenially thats what happens). this is a common mistake when ppl first start using fixed point math. many times its not explained throughly what is actually happening with the math, and why it works.

i know i could have pointed out teh mistake (which you probably just overlooked) instead i figuered a fully explaination for other would be useful.



Share this post


Link to post
Share on other sites
I get that, I guess I was just unclear in what I''m doing. I take what you say to mean that I shouldn''t be shifting pointx and pointy by 16, and that they don''t need to be fixed point? I understand that, but I do want to have pointx and pointy be fixed point, because they will, in the context of the full application, be containing fractional data. My problem is, if I shift the whole number data in pointx and pointy by 16, somehow it ends up getting zero instead of 1310720, which is of course the calculator result. And unfortunately, 0>>16 is 0, not 20. I realize I wasn''t shifting back when I printed to the screen, but I completely bypassed that step because it somehow gets zero before that. Sorry if I was unclear, and even sorrier still if I misunderstood your post. Still, can anyone please help me figure out how it''s getting zero?

-Arek the Absolute

Share this post


Link to post
Share on other sites
well thats because you get a shift by 32 instead of 16 if you mul them. multiplications basically double the amount of bits needed to hold the highest number. ie 65535 is the highest 16bit number and 65535 squared is 4294836225 while the highest 32bit number is 4294967295. so estenially you get 20 shifted by 32 which overflows the undigned int.

instead you should use either the slower __int64 which is MUCH slower then a normal 32bit int. or drop the accuracy of the fractions. you will have to compromise somewhere.

how much accuracy is good enough? basically you have only 16bits to work with since when you multiply you double the bits required. being that you want signed numbers ypu really only have 15bits of percision total. ie a shift by 15 means all the numbers are fractional and anything over 1.0 will overflow.

normally you would just drop the lower 32bits instead of shifting if you were coding this in asm. the compiler cant do this for you since it needs to remain consistent.

asm example (please learn asm and dont rip the code its basically useless as it is (read that as incomplete):

  
mov eax, pointx // move pointx into the register eax

shr eax, 16 // shift right by 16

mov ebx, COS{0] // move COS[0] to ebx its already shifted

mul ebx // mulitply eax*ebx top 32bits go to edx, bottom 32bits goto eax

mov newx, edx // just take the top 32bits and we dont need to shift



the compiler instead detects it as an overflow (since it is) and drops the upper 32bits. the compiler cant just drop the upper 32bits into newx (which gives you the answer you want without needing to shift it) since the number is actually less then it should be (since 32bit multiplies produce 64bit results).

i probably should have mentioned that (i completly forgot to actually try the code and forgot about how the compiler handles things like that since i normally use much smaller shifts or only shift one side. though i have been using mmx for some code too, so i dont notice the overflow proplem since i can just grab the top bits and ignore the lower ones.

my advice is ranked like the olympics where gold is the "best" way (ie best compromise in speed, ease of use, and accuarcy):
bronze. take the easy and very slow way and use _int64

silver. learn asm and code the sections of fixed point in asm

gold. lower the percision you need. remeber you dont need the same decimal point placment for each set of numbers. thus you can use a shift of 4 for the points and maybe 15 (need one bit for sign) for the COS/SIN table. this limits your points to a max value of -4095 to 4095. then when you multiply you could get;

(COS[0]/(2^15))*(20*(2^4))
(20*COS[0])/(2^19)
so you shift by 19 (ie 15+4).

maybe you dont need -4095 to 4095 maybe only -1023 to 1023 for the points. thus you can get 6 bits of fractional percision. you see the larger the fractional portion, the less you get for the whole number range. remember that you only can have 15bits to work with. 1 is for the sign (which is handled automatically yet you should still consider it) and then 15 bits for your actual number. this is only when multipling numbers. pure addition and subtraction you dont need to deal with that stuff. though to add or subtract numbers they must be in the same fixed point format.

thus you cant add 20<<15 and 20<<6 and would need to shift the lower one up to the higher one. so you get 20<<15 and (20<<6)<<9 and now they are in the same format. multiplies automatically get a common denominator just like normal fractional arithmatic. in fact this adjustment is similar to how floating point must deal with things and why it can handle large or small numbers but can have inconsistent percision. you can see in this example the lower percision number just gets zeros padded to its fractional portion. but dont worry about how floating point deals with things, i only mention it as a tidbit and since you may be adding/subtracting numbers in different fixed point formats.

Share this post


Link to post
Share on other sites