Allegro.cc - Online Community

Allegro.cc Forums » Programming Questions » Rounding down

This thread is locked; no one can reply to it. rss feed Print
Rounding down
xinco1
Member #8,061
December 2006

Whats the best way of rounding a variable down to the nearest number. For example, if a variable is 99, and I want to round it to a multiple of 32, so the 99 variable is now 96. How do I do this?

mscava
Member #6,815
January 2006
avatar

I have to be tired today...

Matthew Leverton
Supreme Loser
January 1999
avatar

x = (x/32) * 32;

// or

x -= (x % 32)

Andrei Ellman
Member #3,434
April 2003

Matthew Leverton said:

x = (x/32) * 32;

// or

x -= (x % 32)

As 32 is a power of two, the above could be written

x = (x>>5)<<5;

// or

x &= 0xFFFFFFE0

But this is unnescesary, as modern compilers will do this optimisation for you. However, if chosing a multiple to round down to, it still helps if you chose one that is a power of two so that the compiler can do these optimisations.

AE.

--
Don't let the illegitimates turn you into carbon.

X-G
Member #856
December 2000
avatar

Or better yet (?)...

x &= ~0x1f;

(Does not assume 32-bit integer.)

--
Since 2008-Jun-18, democracy in Sweden is dead. | 悪霊退散!悪霊退散!怨霊、物の怪、困った時は ドーマン!セーマン!ドーマン!セーマン! 直ぐに呼びましょう陰陽師レッツゴー!

orz
Member #565
August 2000

Minor caveats:

x = (x/32) * 32;

is not equivalent to

x = (x>>5)<<5;
or, equivalently, the x &= ~0x1f;

for cases were x is negative. The first rounds towards zero, the second rounds towards negative infinity.

Quote:

But this is unnescesary, as modern compilers will do this optimisation for you. However, if chosing a multiple to round down to, it still helps if you chose one that is a power of two so that the compiler can do these optimisations.

Last I checked, if the variable was of an signed type, MSVC would branch on the sign, do the bitwise operations for positive numbers, and for negative numbers first negate, then do the bitwise stuff, then negate the result. All that just to get the correct rounding rules on negative numbers.

Tobias Dammers
Member #2,604
August 2002
avatar

I'm wondering whether branching for something this simple is a good idea... if there is a random distribution of positive and negative numbers to be divided, this will kill branch prediction... wouldn't the integer divide be faster on modern hardware in that scenario?

---
Me make music: Triofobie
---
"We need Tobias and his awesome trombone, too." - Johan Halmén

orz
Member #565
August 2000

Quote:

I'm wondering whether branching for something this simple is a good idea... if there is a random distribution of positive and negative numbers to be divided, this will kill branch prediction... wouldn't the integer divide be faster on modern hardware in that scenario?

I haven't benchmarked the approaches, but my guess would be:
Unpredictable sign is very rare.
The penalty for mispredict is high (20 to 35 cycles, at a guess), but so is integer division (10-30 cycles at a guess). So, even a 50% mispredict rate is probably not significantly worse than regular integer division.
Though, the version with a branch is probably consuming at least a tiny bit of branch prediction resources, and probably minutely lowering the prediction success rate of other branches in the same program.
But Microsoft probably did benchmark the approaches before choosing the method they chose (/me crosses his fingers).

Tobias Dammers
Member #2,604
August 2002
avatar

It depends on what you use it for.
If you do a lot of divisions, and your material is more or less "contiguous" (by that I mean a reasonably accurate discrete representation of a contiguous signal), such as the case in higher-quality audio, or all values have the same sign (such as in e.g. image data), then the branching approach is definitely faster, since there would be only a few or no mispredictions.
If, OTOH, you divide only occasionally, or the input values oscillate wildly (sign change on every 3rd value or more), then just dividing is faster.
Though I don't think one meets this scenario a lot.

---
Me make music: Triofobie
---
"We need Tobias and his awesome trombone, too." - Johan Halmén

xinco1
Member #8,061
December 2006

Ok, and what is the best way of rounding up?

GullRaDriel
Member #3,861
September 2003
avatar

If it is not a time critical function who need to round your number, then do not take care of any optimization and use x = (x/32) * 32; (as ML said).

It will take care of positive/negative value and will avoid you from the (Does not assume 32-bit integer.) thing.

Plus, a decent compiler will take care of those sort of optimization for you.

Generally, I can tell that you first need to fully develop your application.
Optimization should take place once you know that the application is stable and you know which platform will run your code.

CMIIAW

_

"Code is like shit - it only smells if it is not yours"
Allegro Wiki, full of examples and articles !!

Tobias Dammers
Member #2,604
August 2002
avatar

Quote:

Ok, and what is the best way of rounding up?

Exactly the same, but before rounding, you add precision-1 to the input.
E.g.:

rounded = ((original + 31) / 32) * 32;

---
Me make music: Triofobie
---
"We need Tobias and his awesome trombone, too." - Johan Halmén

X-G
Member #856
December 2000
avatar

--
Since 2008-Jun-18, democracy in Sweden is dead. | 悪霊退散!悪霊退散!怨霊、物の怪、困った時は ドーマン!セーマン!ドーマン!セーマン! 直ぐに呼びましょう陰陽師レッツゴー!

xinco1
Member #8,061
December 2006

Ok,thats that problem sorted, but I got another:
I need a formula to get the mouse_x and draw it to the screen on a grid. Heres what I got thanks to you guys:
(0 + (x % 20) + (mouse_x - (mouse_x % 20)))
x is the variable of where the grid is drawn (can be anywhere from -2000 to 0)
The problem with this is that when the grid is drawn at -10 for example the mouse is in a grid square while the code equals another how do i fix it??

Kauhiz
Member #4,798
July 2004

Care to actually describe the problem? Also, what is the zero doing in the code?

---
It's Ridge Racer! RIIIIIDGE RAAAAACER!

Tobias Dammers
Member #2,604
August 2002
avatar

If I understand correctly, you have a tile map that is displayed on screen at a given scroll position, and you want to transform screen coordinates (e.g. from the mouse) into tile coordinates, and possibly back.
OK, here goes.
I assume that the scroll position is given in screen coordinates, not tilemap coordinates.
First, you need to find out where IN SCREEN COORDINATES (that is, pixels) the mouse is relative to the grid origin. This is easy: just subtract the scroll position from it:

mouse_x_rel = mouse_x - scroll_x;

And then you need to transform pixels into tile coordinates. Since a tile is (in your scenario) 20 pixels wide, you must divide the screen coordinates by 20:

tile_x = mouse_x_rel / 20;

Or, in a more general approach:

tile_x = mouse_x_rel / tile_w;

If your tile width happens to be a power-of-two, you can substitute:

tile_x = mouse_x_rel & (tile_w - 1);

...which is a lot faster.
Putting it together:

tile_x = (mouse_x - scroll_x) / tile_w;
// or in case of power-of-two:
tile_x = (mouse_x - scroll_x) & (tile_w - 1);

The reverse can be found by simply solving the above equation for mouse_x:

mouse_x - scroll_x = tile_x * tile_w;
// <=>
mouse_x = tile_x * tile_w + scroll_x;

This gives you the upper-left corner of the tile in question; if you want the center, add tile_w / 2 to it.
If your tiles are power-of-two-sized, you can substitute left-shift operations for the multiplication, though it's a little less straightforward than the &, especially if you don't hard-code the tile size.

--- EDIT ---
Oh, and please read this. I could have just answered "By using the correct equation." ;D

---
Me make music: Triofobie
---
"We need Tobias and his awesome trombone, too." - Johan Halmén

xinco1
Member #8,061
December 2006

What i meant was if I had this:

1if(mouse_x<10){
2 x++;
3}
4if(mouse_y<10){
5 y++;
6}
7if(mouse_x>630){
8 x--;
9}
10if(mouse_y>470){
11 y--;
12}
13if(x>0){
14 x=0;
15}
16if(x<-2000){
17 x=-2000;
18}
19if(y>0){
20 y=0;
21}
22if(y<-2000){
23 y=-2000;
24}
25draw_sprite(buffer,grid,x,y); //The grid is 20x20
26draw_sprite(buffer,marker,(x%20)+(mouse_x-(mouse_x%20)),(y % 20)+(mouse_y-(mouse_y%20)));

Thats what I've got. It draws the marker correctly to the grid but it is slightly out. What happens is the mouse is sometimes in one square but the marker is drawn to the square to the left. My question is how can I correct this so that the marker is drawn at the correct place?

Simon Parzer
Member #3,330
March 2003
avatar

In your code, what are x and y good for?

xinco1
Member #8,061
December 2006

X and Y are the positions of where the grid is drawn

ImLeftFooted
Member #3,935
October 2003
avatar

int makePow2(int x) {
  x--; x |= (x >> 1); x |= (x >> 2); x |= (x >> 4);
  x |= (x >> 8); x |= (x >> 16); x++; return x;
}

This is the code I'm using to upsize my textures to a power of 32.

Bob
Free Market Evangelist
September 2000
avatar

Dustin said:

This is the code I'm using to upsize my textures to a power of 32.

And you can find an explanation for it here.

--
- Bob
[ -- All my signature links are 404 -- ]

ImLeftFooted
Member #3,935
October 2003
avatar

Quote:

And you can find an explanation for it here [bob.allegronetwork.com].

Whenever you link to that page I always think how useful the thing is. But then when I actually need it I've forgotten it exists. :-/

Go to: