Overview of Fixed Point Number Pitfalls. Fixed point numbers is a method of giving intergers a fractional or rational (fractional) component. There BIG advantage over floating point numbers is speed of calculations as they make direct use of integer math and bit rolls (bit rolls are the same speed as integer addition). The Disadvantage however is that they can not handle large numbers or small fractions very well, and require forethought before use. Fixpoint numbers can be added and subtracted (even negitively) using the normal + and - operations of intergers. This makes them perfect for the recording of positions/ velocity and acclerations. Multiplication and division is not so easy. Because of the position of the decimal point in the middle of a fixpoint number, bit rolls are required to correct the final position of the decimal point place. What exactly is it? It involves taking a integer and pretending that the decimal place instead of at the end is somewhere in the middle! For Example here is a normal integer (16 bits long for the example) signed bit 15 bit value +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ |+/-| | | | | | | | | | | | | | | | * +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | decimal point here ---' Which produces a number from -32768 to +32767. Now we pretend that it is instead a 9 bit integer (including sign bit) with a 7 bit rational component to produce a rational number. signed bit 8 bit real component 7 bit rational componant +---+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+ |+/-| | | | | | | | | * | | | | | | | | +---+---+---+---+---+---+---+---+---+ | +---+---+---+---+---+---+---+ decimal point is now here ---' producing a number from -256.0 to about +255.9922. with a precision of 1/128. This is nowhere near the precision of a floating point number. What this does however is allow ultra fast calculations on rational numbers. ------------------------------------------------------------------------------- The size of the numbers used in the calculation however can be a problem as overflowing a 32 bit register ( 31 bit for number + sign bit ) is VERY VERY easy in multiplications and divisions. You are normally more concerned with the precision or accuracy of the numbers you are calculating thus normally you would use the following marcos for multiplication and division. fixmul() - here the numbers are multiplied and then adjusted. this ensures that no loss of precision results from the multiplication, however the result of the calculation is limited in size of overflow of register results. fixdiv() - The divided number is adjusted before the operation resulting in the a small maximum size for the numerator (divided) before overflow occurs - no loss of precision results. However should you be concerned with the size of the numbers and not the accuracy as in the final calculations to screen coordinates, the following macros ensure that as long as the result is within normal maximum for the fixpoint number, the result of the multiplication or numerator of the division will not overflow the 32 bit register This is at the expense of an extra bit roll however. fixmul2() - the numbers are corrected before the operation. This means that larger numbers can be used but at only half the precision. fixdiv2() - both numerator and divisor is adjusted before the operation. This results in a larger number that can be divided at the loss of the maximum size of the divisor. The following table is to help with the final selection of PLACE. Results of multiplys and numerators in divisions must be less than the Maximums listed in the table, or overflow will occur. Note the loss of maximum in normal multiplys and the loss of precision in version 2 forms. PLACE Add/Sub Normal Multiply version `2' Multiply size Maximum Precision Maximum Precision Maximum Precision 16 32768 1/65536 .5 1/65536 32768 1/256 14 131072 1/16384 8 1/16384 131072 1/128 12 524288 1/4096 128 1/4096 2^19 1/64 10 2^21 1/1024 2048 1/1024 2^21 1/32 8 2^23 1/256 32768 1/256 2^23 1/16 6 2^25 1/64 2^19 1/64 2^25 1/8 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - int 2^31 1 2^31 1 2^31 1 NOTE :- The above table is for 32 bit integers set up as a 31 bit number + sign bit (numbers are absolute maximums). Operations with Integers NOTE :- if at all possible fixpoint numbers should be multiplied and divided by integers as list in the valid operations below, These operations DO NOT involve the loss of accruacy in fix point numbers. CORRECT FORMULAS FOR FIXED POINT NUMBERS ( i = int ; f = fixpoint ) i = fixtoint( f ) f = inttofix( i ) f = f + f f = f - f f = fixmul( f , f ) f = fixdiv( f , f ) f = f * i f = f / i i = f / f f =+ fix1 (* increment *) i = fixdiv( i , f ) ------------------------------------------------------------------------------- Fixed Point Angles If you define an angle as a fraction of 2*PI using either signed or unsigned intergers then very fast angle mathematics can be used. First in addition/subtraction/multiplication/division, the binary overflow will cause the angle to wrap naturally in the circle. Which quadrant the angle is in can be determined from the top two bits. The rest of the number (lower 14 bits for 16 bit angles) can be used with a sine or cosine table lookup. all very easy, simple and fast. For example with a 8 bit angle _fixed_point_ radians decimal .00000000 0 0 .01000000 PI/2 90 .10000000 +/- PI +/- 180 .11100000 -PI/2 or 7*PI/4 -45 or 315 The sign depends only on the type of integer, the bit pattern remains the same in either case. For more detail See the book "Graphic Gems (1)" ------------------------------------------------------------------------------- Fixed Point Square Root /* The following comes from Graphics Gems V, gem I.3 ** It is iterative, with the precision basically doubling every iteration. ** The number of fractional bits MUST is a divisible by 2. */ /* The definitions below yield 2 integer bits, 30 fractional bits */ #define FRACBITS 30 /* Must be even! */ #define ITERS (15 + (FRACBITS >> 1)) typedef long fixpoint; fixpoint fixsqrt(fixpoint x) { register unsigned long root, remHi, remLo, testDiv, count; root = 0; /* Clear root */ remHi = 0; /* Clear high part of partial remainder */ remLo = x; /* Get argument into low part of partial remainder */ count = ITERS; /* Load loop counter */ do { remHi = (remHi << 2) | (remLo >> 30); /* get 2 bits of arg */ remLo <<= 2; root <<= 1; /* Get ready for the next bit in the root */ testDiv = (root << 1) + 1; /* Test radical */ if (remHi >= testDiv) { remHi -= testDiv; root += 1; } } while (count-- != 0); return(root); } ------------------------------------------------------------------------------