is mod(%) efficient?

This is a discussion on is mod(%) efficient? within the C++ Programming forums, part of the General Programming Boards category; I understand that using shifting bits to do multiplication is fast. but what a mod? is using the standard mod ...

  1. #1
    Registered User
    Join Date
    Dec 2004
    Posts
    163

    is mod(%) efficient?

    I understand that using shifting bits to do multiplication is fast.

    but what a mod? is using the standard mod fast? can i do shifting bits to do mod?

  2. #2
    Woof, woof! zacs7's Avatar
    Join Date
    Mar 2007
    Location
    Australia
    Posts
    3,459
    Mod is slow in comparison to other operations, and yes you can use bitwise ops to a certain extent to do modulus.
    http://snipplr.com/view/2431/test-if...wise-operator/

  3. #3
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    You can find the remainder of an unsigned number mod any power of two with bitwise operators - for example, the remainder mod 64 is the result of a bitwise & with 63.

    Edit: And the quotient is the result of a bitwise right shift by 6. In general, you can get both the quotient and remainder for a power of two this way. For the general case, there's div(), ldiv(), lldiv(), and imaxdiv() which let you compute the quotient and remainder simultaneously.
    Last edited by robatino; 05-14-2007 at 05:11 AM.

  4. #4
    Registered User
    Join Date
    Dec 2004
    Posts
    163
    ok, i understand, thanks guys!

  5. #5
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,892
    And don't do any of this bit stuff. If it can be done, the compiler will notice it and do it.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  6. #6
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    Quote Originally Posted by CornedBee View Post
    And don't do any of this bit stuff. If it can be done, the compiler will notice it and do it.
    Unless the number in question is a variable that happens to always be a power of two, but the compiler doesn't know it. Are compilers typically smart enough to optimize something like
    Code:
      m &#37;= (1 << n);
    for example? There can be worse cases where the fact that it's a power of two wouldn't be evident from the expression.

    Edit: Also, I'd agree that something like m & 63 may be a little confusing (mostly because the constant isn't in binary - octal or hexadecimal would be better), but m & 1 is perfectly intuitive - a (unsigned?) number is odd iff its 1's bit is 1.
    Last edited by robatino; 05-14-2007 at 09:41 AM.

  7. #7
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,892
    Quote Originally Posted by robatino View Post
    Unless the number in question is a variable that happens to always be a power of two, but the compiler doesn't know it. Are compilers typically smart enough to optimize something like
    Code:
      m %= (1 << n);
    for example?
    Do you actually have such cases? Do you know in these cases that it will always be a power of two? In the typical case, such optimizations are done by the programmer only when the number is a constant anyway.

    And even if there is a complicated expression that you know is a power of two, you still should use modulo unless profiling proves that you really have a bottleneck there.

    Edit: Also, I'd agree that something like m & 63 may be a little confusing (mostly because the constant isn't in binary - octal or hexadecimal would be better), but m & 1 is perfectly intuitive - a number is odd iff its 1's bit is 1.
    Perfectly intuitive and perfectly unportable: it's the other way round for negative numbers on a 1's complement machine. Which is part of what I meant by "if it can be done": the compiler knows if it's on a 1's complement or a 2's complement machine and can choose to do this optimization depending on this knowledge.
    The programmer, on the other hand, should strive for code that works on both machines.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  8. #8
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,160
    Quote Originally Posted by CornedBee View Post
    Perfectly intuitive and perfectly unportable: it's the other way round for negative numbers on a 1's complement machine.
    This will change in C99.

    EDIT: Wait. We're talking about ANDing at this point, not modulus. Nevermind.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Most Efficient Way to Check a Variable Is A Whole Number
    By bengreenwood in forum C++ Programming
    Replies: 29
    Last Post: 05-28-2009, 01:33 PM
  2. Is std::map efficient for this problem?
    By dudeomanodude in forum C++ Programming
    Replies: 12
    Last Post: 04-10-2008, 02:15 PM
  3. Efficient Algorithm
    By purple in forum C Programming
    Replies: 10
    Last Post: 02-05-2003, 02:01 PM
  4. How do I write more efficient code?
    By minesweeper in forum C++ Programming
    Replies: 4
    Last Post: 08-06-2002, 11:08 AM
  5. Any better & efficient alternative to this C prg.
    By perlguy in forum C Programming
    Replies: 12
    Last Post: 05-24-2002, 03:00 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21