Tricks of the Windows Game Programming Gurus:Algorithms, Data Structures, Memory Management, and Multithreading

All ITKnowledge Source Code Search Tips Advanced Search |

| Tricks of the Windows Game Programming Gurus by Andre LaMothe Sams, Macmillan Computer Publishing ISBN: 0672313618 Pub Date: 09/27/99

Search this book:

Previous | Table of Contents | Next

Addition and Subtraction

Addition and subtraction of fixed-point numbers is trivial. You can use the standard + and – operators:

    FIXPOINT f1 = FLOAT_TO_FIX(10.5),

             f2 = FLOAT_TO_FIX(-2.6),

             f3 = 0; // zero is 0 no matter what baby

    // to add them

    f3 = f1 + f2;

    // to subtract them

    f3 = f1 – f2

> Note: You can work with both positive and negative numbers without a problem because the underlying representation is 2’s complement.

Multiplication and Division

Multiplication and division are a little more complex than addition and subtraction. The problem is that the fixed-point numbers are scaled; when you multiply them, you not only multiply the fixed-point numbers but also the scaling factors. Take a look:

    f1 = n1 * scale

    f2 = n2 * scale

    f3 = f1 * f2 = (n1 * scale) * (n2 * scale) = n1*n2*scale2

See the extra factor of scale? To remedy this, you need to divide or shift out the one factor of `scale^2`. Hence, here’s how to multiply two fixed-point numbers:

    f3 = ((f1 * f2) >> FP_SHIFT);

Division of fixed-point numbers has the same scaling problem as multiplication, but in the opposite sense. Take a look at this math:

    f1 = n1 * scale

    f2 = n2 * scale

Given this, then

    f3 = f1/f2 = (n1*scale) / (n2*scale) = n1/n2 // no scale!

Note that you’ve lost the `scale` factor and thus turned the quotient into a non-fixed-point number. This is useful in some cases, but to maintain the fixed-point property, you must prescale the numerator like this:

    f3 = (f1 << FP_SHIFT) / f2;

> Warning: The problem with both multiplication and division is overflow and underflow. In the case of multiplication, the result might be 64-bit in the worst case. Similarly, in the case of division, the upper 16 bits of the numerator are always lost, leaving only the decimal portion. The solution? Use a 24.8-bit format or use full 64-bit math. This can be accomplished with assembly language because the Pentium+ processors support 64-bit math. Or, you can alter the format a little and use 24.8. This will allow multiplication and division to work better because you won’t lose everything all the time, but your accuracy will fall apart.

For an example of fixed-point mathematics, try `DEMO11_4.CPP[vbar]EXE`. It allows you to enter two decimal numbers and then perform fixed-point operations on them and view the results. Pay attention to how multiplication and division seem not to work at all. This is a result of using 16.16 format without 64-bit math. To fix this, you can recompile the program to use 24.8 format rather than 16.16. The conditional compilation is controlled by two `#defines` at the top of the code:

    // #define FIXPOINT16_16

    // #define FIXPOINT24_8

Uncomment the one you want to use and the compiler will do the rest. Finally, this is a console application, so like Spike says, do the right thing…

#### Unrolling the Loop

The next optimization trick is loop unrolling. This used to be one of the best optimizations back in the 8/16-bit days, but today it can backfire on you. Unrolling the loop means taking apart a loop that iterates some number of times and manually coding each line. Here’s an example:

    // loop before unrolling

    for (int index=0; index<8; index++)

        {

        // do work

        sum+=data[index];

        } // end for index

The problem with this loop is that the work section takes less time than the loop does for the increment, comparison, and jump. Hence, the loop code itself doubles or triples the amount of time the code takes! You can unroll the loop like this:

    // the unrolled version

    sum+=data[0];

    sum+=data[1];

    sum+=data[2];

    sum+=data[3];

    sum+=data[4];

    sum+=data[5];

    sum+=data[6];

    sum+=data[7];

This is much better. There are two caveats:

  • If the loop body is much more complex than the loop mechanics itself, there is no point in unrolling it. For example, if you’re computing square roots in the work section of the loop, a few more cycles each iteration isn’t going to help you.
  • Because the Pentium processors have internal caches, unrolling a loop too much might prevent it from fitting in the internal cache anymore. This is disastrous and will bring your code to a halt. I suggest unrolling 8-32 times, depending on the situation.

#### Look-Up Tables

This is my personal favorite optimization. Look-up tables are precomputed values of some computation that you know you’ll perform during run-time. You simply compute all possible values at startup and then run the game. For example, say you needed the sine and cosine of the angles from 0-359 degrees. Computing them using `sin()` and `cos()` would kill you if you used the floating-point processor, but with a look-up table your code will be able to compute `sin()` or `cos()` in a few cycles because it’s just a look-up. Here’s an example:

    // storage for look up tables

    float SIN_LOOK[360];

    float COS_LOOK[360];

    // create look-up table

    for (int angle=0; angle < 360; angle++)

        {

        // convert angle to radians since math library uses

        // rads instead of degrees

        // remember there are 2*pi rads in 360 degrees

        float rad_angle = angle * (3.14159/180);

        // fill in next entries in look-up tables

        SIN_LOOK[angle] = sin(rad_angle);

        COS_LOOK[angle] = cos(rad_angle);

        } // end for angle

As an example of using the look-up table, here’s the code to draw a circle of radius 10:

    for (int ang = 0; ang<360; ang++)

        {

        // compute the next point on circle

        x_pos = 10*COS_LOOK[ang];

        y_pos = 10*SIN_LOOK[ang];

        // plot the pixel

        Plot_Pixel((int)x_pos+x0, (int)y_pos+y0, color);

        } // end for ang

Of course, look-up tables take up memory, but they are well worth it. “If you can precompute it, put it in a look-up table,” that’s my motto. How do you think DOOM, Quake, and my personal favorite, Half-Life, work?

Previous | Table of Contents | Next

Copyright © Macmillan Computer Publishing, Inc.

Products | Contact Us | About Us | Privacy | Ad Info | Home
Use of this site is subject to certain Terms & Conditions, Copyright © 1996-2000 EarthWeb Inc. All rights reserved. Reproduction in whole or in part in any form or medium without express written permission of EarthWeb is prohibited. Read EarthWeb's privacy statement.