Home > documentation, number theory, programming, Python, Sage > Optimized parity testing

Optimized parity testing

To test the parity of an integer is to determine whether it is even or odd. Letting n = 132469, we can test the parity of n by computing its value modulo 2. This can be done either by using the Sage built-in mod function, the Python modulo operator %, or by using the Python bitwise operator &. The operator & is bitwise conjunction, i.e. it corresponds to multiplication over the Galois field \mathbf{F}_2 of two elements. The integer n = 132469 is odd, hence the result of parity testing via mod, %, and & should each return 1.

sage: n = 132469
sage: mod(n, 2).lift()
1
sage: mod(n, 2)
1
sage: n % 2
1
sage: n & 1
1

However, the test using the bitwise operator & is the fastest of all:

sage: %timeit mod(n, 2).lift()
625 loops, best of 3: 42.2 micro second per loop
sage: %timeit mod(n, 2)
625 loops, best of 3: 42.2 micro second per loop
sage: %timeit n % 2
625 loops, best of 3: 1.22 micro second per loop
sage: %timeit n & 1
625 loops, best of 3: 1.02 micro second per loop

The program below demonstrates how to do parity testing using C.

#include <stdio.h>

/* Parity testing using bitwise AND.
 */
static void parity_and(int n)
{
    if (n & 1)
        printf("%i is odd\n", n);
    else
        printf("%i is even\n", n);
}

/* Parity testing using the modulus operator.
 */
static void parity_mod(int n)
{
    if (n % 2)
        printf("%i is odd\n", n);
    else
        printf("%i is even\n", n);
}

int main(void)
{
    int n = 132469;
    int m = 132470;

    printf("Parity testing using modulus operator\n");
    parity_mod(n);
    parity_mod(m);
    printf("Parity testing using bitwise AND\n");
    parity_and(n);
    parity_and(m);

    return 0;
}

The output of the program is:

Parity testing using modulus operator
132469 is odd
132470 is even
Parity testing using bitwise AND
132469 is odd
132470 is even
Advertisements
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: