C++ rounding to nearest multiple of 5

Discussion in 'Programming & Software Development' started by ring wraith, Mar 6, 2006.

  1. houseofzeus

    houseofzeus Member

    Joined:
    Mar 25, 2005
    Messages:
    3,195
    Location:
    St. Lucia, Brisbane
    You must have missed the bit where I noted that dropping the floating point information and rounding down are essentially the same thing.

    No floating point involved, other than the result of i / j, which is cast to integer automatically. It's exactly the same mistake as the first, just without an explicit cast.

    /EDIT: Look, basically it's nitpicking, but calling it rounding is in my mind misleading at best since as you clearly know it only 'rounds down', by truncating any floating point information completely. This is more akin to finding the floor of the number than actual rounding (which can go both ways).
     
    Last edited: Mar 12, 2006
  2. Pacifist

    Pacifist Member

    Joined:
    Mar 10, 2002
    Messages:
    1,949
    Location:
    Gosford
    "No floating point involved, other than the result of i / j,"

    no man, we are getting off topic but in my example
    int i = 29;
    int j = 5;
    int k;
    k = i / j; // K now equals 5

    There is no casting at all, not even implicitly, the floating point unit of the CPU is never used, the i/j return value is not cast to an int, it is an int to start with and an int to finish with, it is all done on the integer portion of the CPU. You could run the above on a 286. A 286 does not do floating point operations at all.
    The reason it equals 5 is not because floating points get truncated on casting (although that is true), the reason it is 5 is because an integer divided by an integer returns an integer that is rounded down.
     
  3. mordy

    mordy Member

    Joined:
    Aug 30, 2001
    Messages:
    5,100
    Location:
    melb
    yeh, but im not sure about but i think it rounds to the nearest number, not just down .. maybe im mistaken
     
  4. houseofzeus

    houseofzeus Member

    Joined:
    Mar 25, 2005
    Messages:
    3,195
    Location:
    St. Lucia, Brisbane
    Dude you own terminology is what is letting you down. It can't be rounded down if there is no floating point :p. Like I said, it's an implicit cast, yes it is done without touching the FPU but it's still there.

    While we are off topic, you do know that floating point calculations worked on 286s don't you. It wasn't through an FPU but emulated using integer maths.

    No, it truncates. It will never round up.
     
    Last edited: Mar 12, 2006
  5. Ze.

    Ze. Member

    Joined:
    Sep 13, 2003
    Messages:
    7,871
    Location:
    Newcastle, NSW
    Folks thats the correct answer and it was the third reply posted :) the +2 fixes the integer always round downs problem by transforming the number into the right range , then it gets rounded down.

    ie 53 becomes 55 , which divided by 5 == 11 , times 5 == 55. Whilst 52 becomes 54 which divides by 5 and equals 10 , which gives 50 , which is the correct answer again.
     
  6. houseofzeus

    houseofzeus Member

    Joined:
    Mar 25, 2005
    Messages:
    3,195
    Location:
    St. Lucia, Brisbane
    Yah, we know that. Mordy was just trying to suggest a quicker way (albeit one that doesn't actually work) and the rest of us are just arguing semantics over why. Where's the harm in that :p.
     
  7. Rolan

    Rolan Member

    Joined:
    Jun 27, 2001
    Messages:
    330
    Location:
    Sydney
    Afaik Pacifist's example does not involve any floating point stuff. Integer division is just continuous subtraction until the carry flag goes off, and that's how it rounds down.
     
  8. houseofzeus

    houseofzeus Member

    Joined:
    Mar 25, 2005
    Messages:
    3,195
    Location:
    St. Lucia, Brisbane
    Note I said implicit.
     
  9. ArcTan

    ArcTan Member

    Joined:
    Dec 23, 2001
    Messages:
    4,694
    Location:
    Sydney
    any chance you're doing COMP115 at mac uni?
    edit: If you're doing 115 and have christophe doche then it's probably something similar to this

    x = static_cast<int>(floor( ( num * 100 ) / 5 + 0.5 ) * 5 );
     
    Last edited: Mar 13, 2006
  10. OP
    OP
    ring wraith

    ring wraith Member

    Joined:
    Jan 18, 2002
    Messages:
    2,120
    Location:
    A.K.A Frank
    holy crap thats got alot of replies. yes I do comp115 and it seems that the next lecture (the night ones for me) are gonna help with this problem.. however this thread has given me ample information to sift through. ill play around tonight and see how it goes.
     
  11. ArcTan

    ArcTan Member

    Joined:
    Dec 23, 2001
    Messages:
    4,694
    Location:
    Sydney
    it'll probably something similar to what I posted then
    the assignment should be easy except that rounding part
    which is probably typical of what christophe does
    I'd doubt many people would get tha part right without help

    pretty sure you'd need the floor function to round it to the nearest 5
     
  12. Ze.

    Ze. Member

    Joined:
    Sep 13, 2003
    Messages:
    7,871
    Location:
    Newcastle, NSW
    I'm by no means a c++ expert but that seems to be wrong :) since you are multiplying the number by 100 but not dividing it :) , not to mention the rest of the hassles.

    floor( ( num * 100 ) / 5 + 0.5 can be rewritten as floor(num*20+0.5) which can then be rewritten as num*20 you then multiple that by 5 and you've got num*100.

    I've been having a think about (n+2)/5*5 and it doesn't work for negative numbers. So i take back my comments about it being correct :)

    to handle positive and negative numbers you need an if statement.

    Gregdudes solution in http://forums.overclockers.com.au/showpost.php?p=5633666&postcount=13 is correct but unoptimised as he says :) and uses a few builtin functions.

    Code:
    if(n<0)
      n=((n-2)/5)*5
    else
      n=((n+2)/5)*5
    so when we turn it into a generic we end up with.

    Code:
    int round(int number , round)
    {
       if(number<0)
          number=((number-round/2)/round)*round;
       else
         number=((number+round/2)/round)*round;  
    }
    The round/2 is going to be quick since divides by 2^n get converted to shifts of by n in the direction of the least significant bit.

    The most expensive operation in this is going to be the division. From memory modulo is just as time consuming as division , however if we use modulo we can replace the multiplication (slow in some cpus) with branches and additions.

    Code:
    int round(int number , round)
    {
       mod=number%round;
       number=number-mod; //round the number
       if(number<0) // note we can replace this with mod<0 since we are just using it to get the sign
          if(mod+round/2 <0)
             number=number-round;
       else
          if(mod-round/2>0)
             number=number+round;
    }
    Worst case we've got :
    1 branch + 1 shift + 1 divide/mod + 1 add/sub + 1 multiply
    2 branches + 1 shift + 1 divide/mod + 3 sub/adds

    so we are trading one multiply for 1 branch + 2 add/subs , this could be a very worthwhile trade on some cpu's.
     
    Last edited: Mar 13, 2006
  13. ArcTan

    ArcTan Member

    Joined:
    Dec 23, 2001
    Messages:
    4,694
    Location:
    Sydney
    I just cut and paste from an assignment solution of a previous assignment written by the same lecturer
    essenstially it's the same with rounding to the nearest 5
    it's something that kinda screwed me up as we really haven't learn much at that point and the rest of the assignment was easy
     
  14. Ze.

    Ze. Member

    Joined:
    Sep 13, 2003
    Messages:
    7,871
    Location:
    Newcastle, NSW
    Don't cut and paste , think about your assignments , thats what they are for. If you go through uni cutting and pasting solutions , then you've wasted your time there. If you earn your degree then you've just shown what a mockery that degree has become. University is about thinking. Its not about regurgitating the answers , you can't do that in the real world , and you certainly can't do it if you get involved with research.

    In hindsight i've said too much in this thread , but i'll leave it , as there is only one other correct solution.
     
  15. ArcTan

    ArcTan Member

    Joined:
    Dec 23, 2001
    Messages:
    4,694
    Location:
    Sydney
    yeah I know that but this is something that hasn't been studied up to this point for him. The only reason I kind of got my result was with the help of a tutor
    this is something probably only a tiny percentage of student doing the subject will get it and imo there hasn't been enough notes and lectures on it to work it out. Even a couple of friends scoring 90's in the subject at the end didn't figure it out because it wasn't really studied

    given the notes and what's done so far, it's difficult to get that rounding right
    I've already been through the subject and know the lecturer well

    edit: maybe it's to separate the good students from the average students
    my friends and I didn't really get that part totally right(was worth a small percentage of the total assignment) and we all ended up with D and HD's
     
    Last edited: Mar 13, 2006
  16. Ze.

    Ze. Member

    Joined:
    Sep 13, 2003
    Messages:
    7,871
    Location:
    Newcastle, NSW
    You can't rely on being spoonfed solutions to every problem , work through the problem and your solution to it , then see if you can find cases where it doesn't work. Whilst the material taught at university in your lectures is important , the skills in learning to think are just as important.
    Your tutor misled you or you misunderstood him.
    It's easy to work out once you start thinking about what can happen with different input. You are still expecting to be spoonfed the solution.
    It's to sort out the students that can actually think versus the sheep who can regurgitate answers.

    You shouldn't just be listening during lectures , you should be thinking ahead of what he's saying when he's showing you solutions to the problem and trying to work out how he's going to solve it.

    You won't be right everytime but you'll get better and you'll learn from your mistakes. Everybody makes mistakes but yours was a simple one to avoid, if you checked a few values in your head you would've found that you were incorrect and begun to see where you went wrong. Heck i've made a mistake in this thread , i said camh solution was correct but i forgot to test it with negative numbers.

    Learn to do these things now , and you'll find university much easier. There is nothing worse than trying to debug a large chunk of code and finding that one fix introduces another error , needing more and more patchwork fixes to fix the thing. When it would've been easier to work out the big picture first, then build it up out of small components that you've tested.

    It's far easier and more useful to remember the methods of solving problems than the solutions to them.

    I know it sounds a bit harsh but its for your own good.
     
  17. Ravenclaw

    Ravenclaw Member

    Joined:
    Dec 6, 2004
    Messages:
    2,090
    this will work in all sane languages. be careful with languages that truncate towards infinity.

    i love python

    Code:
    >>> int(-7/5.0)
    -1
    
    >>> -7/5
    -2
    
     
  18. Ze.

    Ze. Member

    Joined:
    Sep 13, 2003
    Messages:
    7,871
    Location:
    Newcastle, NSW
    Thats insane , what the bloody hell were they thinking? That takes the rules of integer arithmatic laid down by mathematicians and throws them out the window.
     
  19. camh

    camh Member

    Joined:
    May 23, 2002
    Messages:
    140
    Location:
    Sydney
    It may be insane, but it's also reality. Since you've now pointed twice that I was wrong (accepted) :), I'll have to make a few comments on you final answer.

    I was reading "The Standard C Library" by P.J.Plaugher (1st ed.) where I was reading about the div() function (pp. 384) and it says:

    While discussing the expense of a divide versus a branch, you always favoured the branch. Even though you recognise a branch can be expensive on some CPUs, I would have thought that on modern processors, avoiding a branch (and hence a pipeline stall) would be worth more than avoiding a divide instruction.

    You need some braces in your code. The "else" is ambiguous and will typically bind to the inner "if", while your indentation suggests otherwise. Also, the "if" after that "else" will be treated as an "else if". Both of these can be fixed with braces.

    You don't declare the type of "round" which should be "unsigned int".

    Finally, the type of "number" should also be "unsigned int" so that my one liner can be right again :)
     
  20. Ze.

    Ze. Member

    Joined:
    Sep 13, 2003
    Messages:
    7,871
    Location:
    Newcastle, NSW
    I'm always happy for criticism.

    It's highly dependent upon cpu's and thats why i posted the costs of it.

    admittably i was thinking more toward microcontrollers where it's apparent , on a modern pipelined cpu its far better to avoid the stall.
    You are quite right :) laziness took over.

    Easy mistake to make , and easy mistake to avoid but we all make em.
     

Share This Page

Advertisement: