### Archive

Archive for October, 2010

## Clone, configure, build and test M4RI

I’m new to the autotools world, so I was rather helpless when I first looked at M4RI. Say I have patched a file in M4RI. The problem now is figuring out how to configure, build, and test the patched M4RI tree. The solution below was kindly communicated to me by the lead M4RI maintainer Martin Albrecht.

$hg clone http://bitbucket.org/malb/m4ri$ cd m4ri/
$autoreconf --install$ ./configure
$make$ make check


## 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


## Tools for C development

This post collects free and open source software tools that are useful when you do software development in C. For a survey of software development tools for scientific computation, see A Survey of C and C++ Software Tools for Computational Science by D.J. Worth, C. Greenough and L.S. Chin. See The Art, Science, and Engineering of Software Development by Steve McConnell for some best practices.

Lint tools

• Cppcheck: A tool for static C/C++ code analysis.
• Splint: Annotation-assisted lightweight static checking.

Documentation generators

• Natural Docs: documentation generator for multiple programming languages.
• ROBODoc
• Sphinx: A tool that makes it easy to create intelligent and beautiful documentation.

Testing tools

See A Survey of Software Testing Tools for Computational Science by L.S. Chin, D.J. Worth and C. Greenough.

• CUnit: Unit testing framework for C.
• gcov: A test coverage program. See ggcov for a GUI replacement of gcov.

Profiling & debugging tools

• DDD: Graphical front-end for command-line debuggers such as GDB, etc.
• GDB: The GNU Project debugger.