CODEWITHSUNDEEP
c++winapimathinteger-division
vexe
vexe

Reputation: 5615

Evenly distribute grid cells horizontally/vertically?

I'm trying to draw a grid inside a window of game_width=640 and game_height=480. The numbers of grid cells is predefined. I want to evenly distribute the cells horizontally and vertically.

void GamePaint(HDC dc)
{
    int numcells = 11;
    for(int i = 1; i <= numcells; i++)
    {
        int y = <INSERT EQUATION>;
        MoveToEx(dc, 0, y, NULL);
        LineTo(dc, game_width, y);
    }

    // solving the horizontal equation will in turn solve the vertical one so no need to show the vertical code
}

The first equation came to mind was:

i * (game_height / numcells)

The notion behind this is to divide the total height by the number of cells to get the even cell size, which is then multiplied by i in each iteration of the loop to get the correct y coordinate of the beginning of the horizontal line.

The problem with that is that it seems to leave an extra small cell at the end:

enter image description here

I figured this must have something to do with that integral division, so we come to the second equation:

(int)(i * ((float)game_height / numcells))

The idea is to avoid the integer division, do a float division, multiply by i like before and cast the result back to int. This works well, no extra small cell at the end!

enter image description here

What's driving me nuts, is this equation:

i * game_height / numcells

which seems to have the same effect as the previous equation, but of course with the added benefit of not doing any casting. I can't figure out why this doesn't suffer from the integer division issues in the first equation.

Note that mathematically: X * (Y / Z) == X * Y / Z So there's definitely a problem with integer division in the first equation.

Here's a video watching these 3 equations in the debugger watch window.

You can see an increasing gap between the result of the first equation vs the second and third (which always had the same result) as i increases.

Why is the 3rd equation giving correct results as the second equation and not suffering from the integral division error in the first equation? I just can't seem to wrap my head around it...

Any help is appreciated.

Upvotes: 1

Views: 403

Answers (1)

IInspectable
IInspectable

Reputation: 51503

The answer is in the order of operations performed. The first equation

int y = i * (game_height / numcells);

performs the division first, and magnifies the rounding error by multiplying with i. The further you move down/to the right, the larger the accumulated rounding error becomes.

The last equation

int y = i * game_height / numcells;

is evaluated left to right. The relative error gets smaller, as you are dividing larger numbers (i * game_height). You still have a rounding error, but it doesn't accumulate. The fact, that you do not wind up with extra space at the final evaluation is, that i is equal to numcells, essentially cancelling each other out. You will always see y == game_height in the final iteration.

Using floating point operations is still more accurate: While the rounding error using integer math is in the interval [0 .. numcells) for each line, floating point math reduces that to [0 .. 1). You will see more evenly distributed lines using floating point math.

Note: On Windows you can use MulDiv instead of the integer equation, to prevent common errors such as transient overflows.

Upvotes: 2

Related Questions