Oddness and evenness summary

I finally got a chance to talk to Jeroen about this one last BeerCamp and I finally have time to write it up now — sorry about the delay.

Jeroen's question was how to tell if a number was even or odd without using division. As Jeroen says, Mike's Python solution is exactly what he had in mind. Here it is:

def odd(n, x=1): return odd(abs(n)) if n < 0 else n if n<2 else odd(n-x,1) if x+x>n else odd(n,x+x)

It isn't entirely obvious what's going on here unless you already know how to solve it.

The essence of the algorithm is in the value x and it's doubling at the end of the line. What Mike is doing is to start from 1 and then keep doubling this number until he overshoots the value that he's looking at. He can subtract the previous value of x thus reducing the number he's looking at. Keep doing this and he ends up with a value of zero or one, and if the original value reduces to one it was odd, if zero then it was even. The process is actually a way of converting a number to binary without using division (although he throws this extra information away).

Say we started with 62 this is what it does (as his version is recursive I'll just list out the successive calls to odd):

1. odd(62, 1)
2. odd(62, 2)
3. odd(62, 4)
4. odd(62, 8)
5. odd(62, 16)
6. odd(62, 32)
7. odd(30, 1) — 64 was greater than 62 so we start again after subtracting 32
8. odd(30, 2)
9. odd(30, 4)
10. odd(30, 8)
11. odd(30, 16) — 32 was greater than 30 so we start again after subtracting 16
12. odd(14, 1)
13. odd(14, 2)
14. odd(14, 4)
15. odd(14, 8) — 16 was greater than 14 so we start again after subtracting 8
16. odd(6, 1)
17. odd(6, 2)
18. odd(6, 4) — 8 was greater than 6 so we start again after subtracting 4
19. odd(2, 1)
20. odd(2, 2) — 4 was greater than 2 so we start again after subtracting 2
21. odd(0, 1)

The last call returns zero meaning the initial value was even. A little bit of a cheat maybe, but quite understandable and works well with Python's notion of “truthiness”. If that bothers you then the following small change makes it return a boolean:

def odd(n, x=1): return odd(abs(n)) if n < 0 else (n==1) if n<2 else odd(n-x,1) if x+x>n else odd(n,x+x)

Haskell

Alexey Romanov also had the same idea and expressed it in Haskell:

powersOf2 n list@(x:xs)
             | n > x     = powersOf2 n (x*2 : list)
             | otherwise = list

reduce n [] = n
reduce n (x:xs)
             | n >= x    = reduce (n - x) xs
             | otherwise = reduce n xs

isOdd n = reduce n (powersOf2 n [2]) == 1

Alexey's powersOf2 builds a list of powers of powers of 2 up to the target value and the reduce function subtracts them. The interaction there is a little subtle — he avoids the test that Mike uses for greater because that test is captured in the list generation done by powersOf2. Finally he reduces the value by subtracting those powers of 2 that correspond to set bits in the binary representation of the value.

isOdd makes use of this, but generates the powers of 2 list from 2, this will leave the least significant bit left over after the reduction which he then uses to give his answer.

Ruby

Sikachu! went about it in a different way:

def even(number); number[ 0 ] == 0 end

I think technically this is cheating :) It's quite a neat API for grabbing a bit in an integer though.

C

Wiennat had a go in C. It's been a long time since I did any C programming and it took me a while to work out the right headers and how to use printf :/

#include <stdio.h>
#include <malloc.h>


int odd(int in){
    int b, c;
    int maxi = 8;
    int max  = 1;
    int i    = 1;
    int *a   = NULL;
    a = (int *)malloc(sizeof(int) * maxi);

    a[0] = 2;

    while (in < max+max){
        if (i == maxi){
            maxi *= 2;
            a = (int *)realloc(a, sizeof(int) * maxi * 2);
        }
        a[i] = a[i-1]*2;
        i++;
    }
    b = in-a[i];
    do {
        for(c=i-1; a[c]>b && c >= 0;c--);
        b -= a[c];
    } while (b >= 2);
    free(a);
    return b;
}

int main() {
    printf("%d\n", odd(62));
    printf("%d\n", odd(63));
    printf("%d\n", odd(16));
    printf("%d\n", odd(17));
}

As for how this works… I'm not sure that I have a clue at all. What I think it's doing is something very similar to Alexey's — it creates a list of powers of two (the first while loop) which then go through a reduction phase (the do loop). Being C of course Wiennat has to deal with memory allocation — not a lot of fun when all you're after is a list. He might have saved himself a little trouble there by realising that the maximum array size he needs is related to the size of the int data type — sizeof(int) * 8 should work on any but the weirdest platforms.

So, well done everybody, and thanks to Jeroen for the puzzle.