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

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

    Puzzle: Find the error in this algorithm.


    I figure that this forum could use a puzzle or two, once in a while. So here's my first effort --- basically the idea is to find if there is a flaw in the logic below:

    Algorithm to determine odd or even number:

    1. Perform a modulo divide operation by 2 on the number to get the reminder.
    2. If the reminder is 1, the number is odd, otherwise the number is even.

    Expressed in C, the code would look something like this:
    Code:
    #include <stdio.h>
    
    void odd_even(int x) {
      if ((x % 2) == 1)
        printf("%d is odd\n", x);
      else
        printf("%d is even\n", x);
    }
    
    int main() {
      odd_even(2);
      odd_even(1);
    }
    So, is there anything wrong with this algorithm. Post your replies here.
  2. #2
  3. No Profile Picture
    Contributing User
    Devshed Intermediate (1500 - 1999 posts)

    Join Date
    Jul 2001
    Location
    Oslo
    Posts
    1,516
    Rep Power
    15
    Well, first of all this could done much easier using a bitwise AND with 1, which would also fix the flaw in the algorithm, namely that -1 (or any odd negative number for that matter) will be marked as even because -1%2 = -1.
    --
    Regards
    André Nęss

    Puritanism: The haunting fear that someone, somewhere may be having fun
  4. #3
  5. Banned ;)
    Devshed Supreme Being (6500+ posts)

    Join Date
    Nov 2001
    Location
    Woodland Hills, Los Angeles County, California, USA
    Posts
    9,641
    Rep Power
    4247
    Congratulations Andaness, you found the right answer! I didn't think the puzzle would be cracked so quickly . One other way to fix it would be to reverse the check as in:

    Code:
    if (number modulo 2) = 0 then 
        it is an even number
    else
        it is an odd number
    This will also work with negative numbers.

    The bitwise AND is the more efficient way to determine if this is an odd or even number, but the modulo method was discussed for the purposes of this puzzle. (NOTE: For all the new readers in this forum, the bitwise AND algorithm was discussed earlier in Quick algorithm to determine odd/even numbers Check out the difference in the size of the code using the modulo method and the bitwise method and you'll clearly see where the efficiency comes from.)

IMN logo majestic logo threadwatch logo seochat tools logo