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