• doynax (unregistered) in reply to Tom Dibble
    Anonymous:

    In any case, I'd much rather to an if-branch on the negative value case than modulo twice.  Wouldn't that always be both more efficient and less likely to give me a headache?  (okay, don't answer the latter, I already know its answer).

    Well, on some systems it pays of to do perform some seriously convoluted bithacks (and other workarounds) to avoid unpredictable branches. Even an extra modulo may well be far cheaper if you're unlucky.

    But instead of an extra modulo wouldn't it be easier (and more natural? I honestly have no idea what the modulo solution does) just to add the signed bias to transform things into an unsigned range, and then subtract it afterwards to get a signed value back out.

    value -= INT_MIN;
    value += step;
    value -= (unsigned) value % step;
    value += INT_MIN;

  • Jon (unregistered) in reply to aikii
    Anonymous:
    This convert-to-string-and-look-for-minus-sign seems to be a classic. Throughout all lines of code on earth that test for negative, how many times it happens ? 0.1% ?
    ...
    Or multiply x by itself, then test if x and the result have different signs.
    But that leaves the problem of checking if two numbers have different signs. Hmmm. How about multiplying them together and seeing if the result is negative?
  • pete (unregistered) in reply to seer

    I _did_ rethink that -- negative modulus in valid:
     

    c:\>irb

    irb(main):001:0> -2%5

    => 3

  • (cs) in reply to Oliver

    The clue to this code is the value += 1 preceding the loop, which indicates that the author thought was using integer math and that value may be divisible by step already. In fact, in the submission Ward implies it is part of a loop, which I neglected to mention. The intention for that code was for ( int value = 0 ; value < n ; value += step ) { ... }. The comment was left unchanged.

  • (cs)
    Derrick Pallas:
      // find the next "value" divisible by "value"
  value += 1
  while ( 0 <> value%step )
  {
      value += 1
  }

    Like all developers .. nobody has read the specs The fix would be as short as the following: 

      // find the next "value" divisible by "value"
  value += 1
  • (cs) in reply to GeneWitch

    GeneWitch:

    Read above... My statement was not incorrect, i just assumed that the original programmer couldn't have been so stupid as to have made the variable "step" larger than the variable "value" everything i said regarding the step>value was 100% correct, except that i assumed it wanted the NEXT larger value. which would mean 1000, in this case. 477 iterations.

    The original programmer wasn't stupid (well he was, but for other reasons) The original programmer didn't know how big value would be.

     For example, I'm working on a program the displays text files. I can display so many lines per page, say 25... So my step is 25. If I read it a large 10,000 line program, then my value is 10,000. But if I read in a small 10 line program my value is 10. I didn't MAKE the variable smaller than step, it just is. Unforuntately us programmers have to deal with things like that.

     You also said:

    GeneWitch:

    I've said this at least four times now.... IF step is LARGER than value, the answer is either step, or multiples of step. If not, THEN you have to do other voodoo magic. see above post. I'm out of here, since this has been beaten to death and i hate having to repeat myself when the stuff is in the thread in black and white.

    you are half correct. If the step is larger than the value the answer is a multiple of step (guess what, step is also a multiple of step AND if the value is LARGER than step, the answer BETTER not be step, cause well step is smaller than value so it can't be the next value divisible my step) If the answer is NOT larger than the value you do not need to do any voodoo magic, the answer will STILL be a multiple of step.

    WHY or WHY would you want to think of, code and maintain a 7 line, multiple if solution when a nice succient 1 line solution works?

  • (cs)

    Most of the simple additions with modulo to solve the first problem will give the wrong answer in the overflow case when the next divisor of step greater than value would be greater than MAX_INT.

     

    The the second answer, what if value is being passed in as an object and the function was trying to match anything where the object's toString method started with a "-"?
     

  • anonymoose (unregistered) in reply to Prefect
    Prefect:

    Most of the simple additions with modulo to solve the first problem will give the wrong answer in the overflow case when the next divisor of step greater than value would be greater than MAX_INT.

    And what exactly would be the correct answer in that case?

    Prefect:


    The the second answer, what if value is being passed in as an object and the function was trying to match anything where the object's toString method started with a "-"?



    Yeah, I always use the term "negative" to describe an object whose toString method starts with a "-".  For example "- you're an idiot" is a negative string...
  • anonymoose (unregistered) in reply to Jon
    Anonymous:
    Anonymous:
    This convert-to-string-and-look-for-minus-sign seems to be a classic. Throughout all lines of code on earth that test for negative, how many times it happens ? 0.1% ?
    ...
    Or multiply x by itself, then test if x and the result have different signs.
    But that leaves the problem of checking if two numbers have different signs. Hmmm. How about multiplying them together and seeing if the result is negative?


    Hahahahaha!  Took me a minute and then I nearly choked laughing...
  • hobbified (unregistered) in reply to seer
    Anonymous:
    Anonymous:

    next_value_divisible_through_step_without_remainder = value + ((step - value) % step)

    obviously modulo is difficult for some people...
     

    If value=7 and step=5, what is the value of (-2 % 5) ???

    You might want to rethink that one...

    Well that depends, actually. In some languages/implementations, you get a definition of "remainder after truncated division" in which case (-2 % 5) is -2, because -2 / 5 is 0. However, in some languages/implementations you get a much more mathematically sane (if sometimes less handy) definition which has (x % n) always vary between 0 and n-1, in which case (-2 % 5) is 3. 7+3 is 10, and you win. :)

    Captcha: chocobot. Is that a bot that dispenses chocolate, or a huge robotic yellow bird?

  • Your Name (unregistered) in reply to Tom Dibble

    abs(x) is your friend.

     Catchpa: chocobot.
     

  • Mirrorball (unregistered) in reply to Your Name

    WTF! Everyone knows that the proper way to test if a number is negative is: take its square root. If the program fails, then the number is negative.

  • (cs) in reply to Your Name
    Anonymous:

    abs(x) is your friend.

    Actually, that's what I thought when I read it. When I was programming in BASIC at about 9 years of age I never thought of checking to see if a number was less than 0 to see if it was negative. Instead I used to check to see if x <> abs(x) 

  • hahaha (unregistered) in reply to Mirrorball

    hahahahah this THREAD is the biggest WTF ever.

    somebody needs to compile all the solutions, comment them and put it on the front page. the list would include:
    -poster names and count of errors they made
    -who first included the case when step is larger/smaller than value (no consequence at all)

    captcah: 1337

  • (cs) in reply to Mike
    Anonymous:

    > The real wtf is noone can get it right
    > If you want to round up to the next value
    > up_value=value+step-value%step

    Hah! You didn't get it either. Rounding up 4 on 4-grain will give you 8 with this equation. You have to account for the values that are already aligned. Hence:

    /// \brief Rounds \p n up to be divisible by \p grain
    template <typename T>
    inline T Align (T n, size_t grain)
    {
        T r = n % grain;
        T a = n + (grain - r);
        return (r ? a : n);
    }

    The a temporary should be used (instead of just folding the code into the conditional) because it allows the compiler to use a cmov and compile the whole thing with no jumps.

    But what is the next number divisible by 4 which is greater than 4?  Look at the original code.  If we assume it's doing the right thing, then it increments by 1 before testing the modulus.  Therefore, in your example, 8 is the value required.

     

  • Atilla ACAR (unregistered)

    Shouldn't // find the next "value" divisible by "value" 

    be          //find the next "value" divisible by "step"

     and another point how can you find next divisible number divisible by step with value += step?

    I have not think about it, but is not the code above simple? Are there another way?
     

  • Atilla ACAR (unregistered) in reply to Atilla ACAR
    Anonymous:

    Shouldn't // find the next "value" divisible by "value" 

    be          //find the next "value" divisible by "step"

     and another point how can you find next divisible number divisible by step with value += step?

    I have not think about it, but is not the code above simple? Are there another way?
     

    I am so lazy......................... 

    Next_Value_Div_By_Step  = Value + (Max(Value, Step) - Min(Value, Step))%Step

  • JL (unregistered) in reply to hobbified
    Anonymous:
    Captcha: chocobot. Is that a bot that dispenses chocolate, or a huge robotic yellow bird?
    Probably the first.  Or maybe a robot made out of chocolate.  It's a reference to a TV show that appears in The Simpsons: "The Mattel and Mars Bar Quick Energy Chocobot Hour".
  • (cs) in reply to JL

    I just submitted this thread to Alex.

    Anonymized, of course.

  • AdT (unregistered) in reply to Mike

    Three WTFs:

    #1: The original coder already knows the % operator, but not how to use it.

    #2: Many commenters don't either.

    #3:

    Anonymous:

    The a temporary should be used (instead of just folding the code into the conditional) because it allows the compiler to use a cmov and compile the whole thing with no jumps.

    Prematurely microoptimizing nitwit. Did you even test this on your compiler, let alone all C compilers?

  • AdT (unregistered) in reply to GeneWitch
    GeneWitch:


    I've said this at least four times now....



    Indeed. What a waste of words.

    GeneWitch:
    IF step is LARGER than value, the answer is either step, or multiples of step.


    The answer is always a multiple of step. (Where step, 0 and -step are multiples of step, as anyone who has basic mathematical education will confirm.)

    GeneWitch:
    If not, THEN you have to do other voodoo magic. see above post.


    Yes, writing special case code for a special case that is covered by the general case makes a lot of sense. NOT.

    GeneWitch:

    Isn't this just a "lowest common denominator"


    No, it's not. First, there is no "lowest common denominator", unless you mean the negation of the greatest common denominator. Second, what you actually wanted to refer to is the least common multiple, which would be step * value / gcd(step, value), better written as step / gcd(step, value) * value in C-ish languages. Third, you got the definition of the LCM wrong, too. Fourth, even the correct version does not have the slightest little thing to do with what the original code is trying to accomplish.

    In other words: Sorry, not even close.

  • Jeff (unregistered) in reply to doynax
    Anonymous:

    This isn't really C's fault, if anyone is to blame it's the processor designers. Whether integer division and modulo round towards zero or negative infinity is implementation defined, the language simply mirrors whatever your processor actually does to avoid costly workarounds on "odd" processors.
    This is (at least some of the reason) why there's a div() function, it's guaranteed to round towards zero.

    It was implementation-defined in original K&R C, but it's long since been standardized as round-toward-zero. The problem is that round-toward-zero is utterly useless behavior. You almost always want round toward negative infinity for integers, which would make % be a true modulus operator. It might be forgivable if there was a div() function that worked right, but there isn't. So you have two ways to do the wrong thing and no way to do the right thing (efficiently -- there's still ((A % B + B) % B) available.)

    This is one of the big things I'd fix if I had a time machine to go back and yell at early computer scientists. (For what it's worth, I'd also tell the ASCII committee to define a newline character. Not LF, not CR, not freaking VT, NEWLINE.)

     

  • Jeff (unregistered) in reply to Jeff
    Anonymous:

    It was implementation-defined in original K&R C, but it's long since been standardized as round-toward-zero...

    Before anyone else yells at me... yes, I know this is wrong. I actually looked it up before posting to make sure I wasn't full of crap, discovered I was full of crap, and then forgot to fix it before hitting 'post'. Oops.

     

  • (cs) in reply to Jeff
    Anonymous:

    The problem is that round-toward-zero is utterly useless behavior. You almost always want round toward negative infinity for integers, which would make % be a true modulus operator. It might be forgivable if there was a div() function that worked right, but there isn't. So you have two ways to do the wrong thing and no way to do the right thing (efficiently -- there's still ((A % B + B) % B) available.)



    How about rounding towards zero for floating point to integer conversion. Would you like to change that too?

    Frankly I've rarely had any problems with rounding-towards-zero aside from the very fact that it's behavior is undefined, which can be especially nasty when dealing with deterministic code.

    My personal pet peeve is that we're routinely told that optimizing compilers are "smart enough" to turn division and modulo by powers of two into right shifts and bitwise ands, which is clearly impossible when rounding towards zero (assuming that one's complement machines are finally extinct anyway).

  • smile (unregistered) in reply to hobbified
    hobbified:

    Well that depends, actually. In some languages/implementations, you get a definition of "remainder after truncated division" in which case (-2 % 5) is -2, because -2 / 5 is 0. However, in some languages/implementations you get a much more mathematically sane (if sometimes less handy) definition which has (x % n) always vary between 0 and n-1, in which case (-2 % 5) is 3. 7+3 is 10, and you win. :)

    Captcha: chocobot. Is that a bot that dispenses chocolate, or a huge robotic yellow bird?

    In a mathematically sane world -2 % 5 should return an equivalence class consisting of [,,,-7,-2,3,8,13,,,] which are all equivalent in modulo 5. Alas, that's a bit hard for computers to work with and no where near as useful.

  • Anon (unregistered)

    Isn't it just as simple as (C style, for ints)

    value = ( (value / step) +1) * step;

    ?

    of course, you'd need to do all the gubbins about making sure step wasn't zero etc. but I assume in this case that would be done in another Fn.

    Captcha - stfu

    Wonder if it's trying to tell me something?

  • Anon (unregistered) in reply to Anon

    Oops, missed a bit. That was assuming you would be able to modify one or other of the values outside the 'utility' function. If you can't do that, just store it somewhere and increment it by step.

  • annoynimous (unregistered)

    I was looking for one of those "if ( (!(bool)varBool==true) != (false ^^ true))..." gems to add one snippet... But this thread is not worse for the case!

    http://bash.org.ru/quote.php?num=66390

    if (b.ToString().length < 5){...}

    ~~ Captcha: search the frying universe

  • annoynimous (unregistered)

    i even think that the best practice would be to make a fusion with http://thedailywtf.com/Articles/How_Not_to_Parse_Command_Line_Arguments.aspx

    Compare that dull, showing 100% lack of imagination and creativity, "if (b)" with the secure cryptographic "if (!(getHashValue(b.ToString().toUpperCase().toCharArray())!=xxx))"

  • Scotty Brewbuck (unregistered)

    I really can't believe the silliness of some of these comments. How to find the next value divisible by step? Here goes:

    /* Find next value divisible by step. Assumes value is already divisible by step: */ value += step

    Wow, that was profoundly difficult, no?

    But what if value is not already divisible by step? A simple trick of integer math gives the solution which works in all cases:

    value = (value / step + 1) * step

    Notice that no stupid remainders are necessary. Learn how to use integer math, people.

  • persicsb (unregistered) in reply to allo
    allo:
    Anonymous:
    Anonymous:
    isn't more something like:value = value + value%step + 1 ?
     No:value = value - value%step + step 
    easier: value=value+value%step

    value%step is the distance to the next number divisable by step ...

    Hm, not that right, I think.

    value%step is not the distance to the next number. It is the distance from the previous number divisible by step. Look at for example: value = 7, step=5. value%step = 2, since 7 = 1*5 + 2. And 7+2=9 is not divisible by 5, but 7-2=5 is.

  • wade b (unregistered) in reply to persicsb

    If you want the next Highest value divisible by step, you can do this: Value = (Ceiling(Value/step) * step).

    Implement your own Ceiling function or use a runtime one, your choice.

    Some of these proposed "solutions" are really off the mark unless I am misunderstanding something.

    Test Inputs: Value=20 Step= 3 Output = 21

  • Patrick (unregistered)

    I don't know if this was posted already, but:

    value += step-value%step

    value = 11 step = 5

    value%step = 1

    step-1 = 4

    value+4 = 15

    People these days..

Leave a comment on “Fun with Maths”

Log In or post as a guest

Replying to comment #:

Log Out

« Return to Article