#1
  1. Banned ;)
    Devshed Supreme Being (6500+ posts)

    Join Date
    Nov 2001
    Location
    Woodland Hills, Los Angeles County, California, USA
    Posts
    9,607
    Rep Power
    4247

    Quick algorithm to determine odd/even numbers


    Here's my first contribution to the algorithm forum. Most of you have probably written a function to determine if a number is even or odd as follows:

    Code:
    BEGIN PSEUDOCODE
    
      function odd(input_val) 
      begin
         x = input_val mod 2;
         if x == 1 then
            return true;
         else
            return false;
       end
    
    END PSEUDOCODE
    Note that this function uses a modulo operation to determine the reminder, if you divide the number by 2. If there is a reminder, then this is an odd number, otherwise it is even. Seems fairly obvious right? What's not so obvious is that the modulo operator has to perform division to determine the reminder. The division operation eats up quite a few more CPU cycles than say an add operation. The method below is even faster:

    Code:
    BEGIN PSEUDOCODE
    
      function odd(input_val) 
      begin
         if (x AND 1) == 1 then
            return true;
         else
            return false;
       end
    
    END PSEUDOCODE
    Notice that this method uses a bitwise AND operation. If you look at any number in binary notation, you'll note that the Least Significant Bit (LSB) will always be set for odd numbers and cleared for even numbers. Hence, all that is necessary to determine if a number is even or odd is to check the LSB. Since bitwise operations like AND, OR, XOR etc. are usually much faster than the arithmetic operations, this method will run a lot faster. In languages like C, Perl, PHP etc, it is not even necessary to compare the value of the AND operation, since 0 is considered false and non-zero is true in these languages. So the function would simplify itself to:

    Code:
      int odd(int inputval) {
         return inputval & 1;
      }
    Now if you use the C++ keyword inline in the function declaration, then a C++ compiler may not even compile it as a function, but merely embed the one line function body into the code directly.

    All comments/criticisms are welcome. Flames will be redirected to /dev/null
  2. #2
  3. A PAtCHy sErver
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jun 2001
    Location
    Italy
    Posts
    408
    Rep Power
    14
    Here is an example that can evidence it better from an "assembler" view:

    This is a sample C file:
    Code:
    int pippo(int val)
    {
    	return val % 2;
    }
    
    int pluto(int val)
    {
    	return val & 1;
    }
    This is the assembler generated by my c compiler for the hitachi micro ( a 16bit microcontroller ) :
    Code:
          1          int pippo(int val)
       \                     pippo:
          2          {
       \   00000000   79050002           MOV.W   #2,R5
       \   00000004   17F6               EXTS.L  ER6
       \   00000006   01D05356           DIVXS.W R5,ER6
       \   0000000A   0DE6               MOV.W   E6,R6
          3            return val % 2;
       \   0000000C   5470               RTS     
          4          }
          5          
          6          int pluto(int val)
       \                     pluto:
          7          {
       \   0000000E   79660001           AND.W   #1,R6
          8            return val & 1;
       \   00000012   5470               RTS     
          9          }
    The total "cycles" inside pluto function are 4 states.

    The total "cycles" inside pippo function are 32 states.

    So running a slow 16mhz micro ( one state == 62.5 ns ) it can make sensitive differences.

    PS
    I put the codes inside functions only to isolate the code better and for explaining the concept better and to avoid compiler optimizations.
    Last edited by pippo; February 1st, 2002 at 02:10 AM.
  4. #3
  5. No Profile Picture
    Contributing User
    Devshed Intermediate (1500 - 1999 posts)

    Join Date
    Jul 2001
    Location
    Oslo
    Posts
    1,516
    Rep Power
    15
    Kinda strange that % 2 isn't optimized by the compiler the way * 2 is? (bitshift).
    --
    Regards
    André Nęss

    Puritanism: The haunting fear that someone, somewhere may be having fun
  6. #4
  7. A PAtCHy sErver
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jun 2001
    Location
    Italy
    Posts
    408
    Rep Power
    14
    Code:
          1          int pippo(int val)
       \                     pippo:
          2          {
       \   00000000   79050002           MOV.W   #2,R5
       \   00000004   17F6               EXTS.L  ER6
       \   00000006   01D05356           DIVXS.W R5,ER6
          3            return val / 2;
       \   0000000A   5470               RTS     
          4          }
          5          
          6          int pluto(int val)
       \                     pluto:
          7          {
       \   0000000C   1096               SHAL.W  R6
          8            return val * 2;
       \   0000000E   5470               RTS     
          9          }
         10          
         11          unsigned pippo_uns(unsigned val)
       \                     pippo_uns:
         12          {
       \   00000010   1116               SHLR.W  R6
         13            return val / 2;
       \   00000012   5470               RTS     
         14          }
         15          
         16          unsigned pluto_uns(unsigned val)
       \                     pluto_uns:
         17          {
       \   00000014   1096               SHAL.W  R6
         18            return val * 2;
       \   00000016   5470               RTS
    mmmhhh...it optimizes only for unsigned, even if there is an instruction that could do it ( arithmetic shift )

    PS Same for value % 2
    Last edited by pippo; February 1st, 2002 at 02:36 AM.
  8. #5
  9. /(bb|[^b]{2})/

    Join Date
    Nov 2001
    Location
    Somewhere in the great unknown
    Posts
    5,163
    Rep Power
    792

    Re: Quick algorithm to determine odd/even numbers


    Originally posted by Scorpions4ever
    Now if you use the C++ keyword inline in the function declaration, then a C++ compiler may not even compile it as a function, but merely embed the one line function body into the code directly.
    You can also acomplish this same task by turning the function into a macro.

    ----

    on another note...
    It is amazing what you see when you look at the optimized asm from the compiler.
  10. #6
  11. Banned ;)
    Devshed Supreme Being (6500+ posts)

    Join Date
    Nov 2001
    Location
    Woodland Hills, Los Angeles County, California, USA
    Posts
    9,607
    Rep Power
    4247
    I tried the following code, compiled in gcc under FreeBSD running on an x86 machine:

    Code:
    int modulo_odd(int x) {
      return x % 2;
    }
    
    int bitwise_odd(int x) {
      return x & 1;
    }
    
    unsigned modulo_oddu(unsigned x) {
      return x % 2;
    }
    
    unsigned bitwise_oddu(unsigned x) {
      return x & 1;
    }
    Interestingly, when I compiled it with the -O2 optimization flags, the code generated for modulo_oddu and bitwise_oddu was IDENTICAL!:

    Code:
    modulo_odd:
            pushl %ebp
            movl %esp,%ebp
            movl 8(%ebp),%edx
            movl %edx,%eax
            shrl $31,%eax
            addl %edx,%eax
            andb $254,%al
            subl %eax,%edx
            movl %edx,%eax
            leave
            ret
    
    bitwise_odd:
            pushl %ebp
            movl %esp,%ebp
            movl 8(%ebp),%eax
            andl $1,%eax
            leave
            ret
    
    modulo_oddu:
            pushl %ebp
            movl %esp,%ebp
            movl 8(%ebp),%eax
            andl $1,%eax
            leave
            ret
    bitwise_oddu:
            pushl %ebp
            movl %esp,%ebp
            movl 8(%ebp),%eax
            andl $1,%eax
            leave
            ret
  12. #7
  13. /(bb|[^b]{2})/

    Join Date
    Nov 2001
    Location
    Somewhere in the great unknown
    Posts
    5,163
    Rep Power
    792
    Yeah, having to determine the sign make the difference, which is skipped for an unsigned variable, but some languages like php doesn't handle unsigned.
  14. #8
  15. Is a Psycho
    Devshed Newbie (0 - 499 posts)

    Join Date
    Dec 2000
    Location
    In your computer
    Posts
    231
    Rep Power
    14
    Quick method to test for odd/even numbers in PHP...

    PHP Code:
    <?php
      
    function is_odd ($i) {
        if (
    is_int($i 2)) {
            return 
    0;
        } else {
            return 
    1;
        }
      }
    ?>
    Last edited by deepspring; February 20th, 2002 at 08:32 PM.
    deepspring

    - "Netscape 4 users are like lemmings... You can't help but laugh when one falls off a cliff"
  16. #9
  17. /(bb|[^b]{2})/

    Join Date
    Nov 2001
    Location
    Somewhere in the great unknown
    Posts
    5,163
    Rep Power
    792
    deepspring? You lost me, what are you talking about?
  18. #10
  19. Is a Psycho
    Devshed Newbie (0 - 499 posts)

    Join Date
    Dec 2000
    Location
    In your computer
    Posts
    231
    Rep Power
    14
    Quick algorithm to determine odd/even numbers
    Never mind, I will remove/edit/rewrite the post if you want... obviously I made a mistake. Was half asleep when typing it... I should never post when bored.

    Funny thing is that I spent most of the night writting test scripts / apps on the subject in Python and Java...
    deepspring

    - "Netscape 4 users are like lemmings... You can't help but laugh when one falls off a cliff"
  20. #11
  21. /(bb|[^b]{2})/

    Join Date
    Nov 2001
    Location
    Somewhere in the great unknown
    Posts
    5,163
    Rep Power
    792
    No need in removing it. I know what you mean about doing thing half a sleep. I just didn't understand why you were doing it that way with the other examples in this thread.
  22. #12
  23. Is a Psycho
    Devshed Newbie (0 - 499 posts)

    Join Date
    Dec 2000
    Location
    In your computer
    Posts
    231
    Rep Power
    14
    Thankyou onslaught. Doing things half asleep can be pain for others, can't it. I wasn't sure if my post was on par with the thread...
    deepspring

    - "Netscape 4 users are like lemmings... You can't help but laugh when one falls off a cliff"
  24. #13
  25. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    May 2001
    Location
    dallas, texas
    Posts
    2
    Rep Power
    0
    shift a
    jc odd
  26. #14
  27. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2003
    Posts
    1
    Rep Power
    0
    Wouldn't this be the fastest routine?

    Code:
    ROR eax,1
    JS my_jump
    stuff_if_even
    JMP finished
    my_jump:
    stuff_if_odd
    finished:

IMN logo majestic logo threadwatch logo seochat tools logo