Archive

Archive for October, 2010

Clone, configure, build and test M4RI

7 October 2010 Leave a comment

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

6 October 2010 Leave a comment

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

2 October 2010 5 comments

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.
  • google-perftools: Fast, multi-threaded malloc() and nifty performance analysis tools.
  • gprof: The GNU profiler. For a tutorial on this tool, see Profiling Tutorial: A simple program by DJ Worth, LS Chin, and C Greenough.
  • OProfile: Profiler for Linux systems, capable of profiling all running code at low overhead.
  • RATS: Rough Auditing Tool for Security.
  • Solaris Studio: Formerly Sun Studio, but is now called Oracle Solaris Studio.
  • Valgrind: Instrumentation framework for building dynamic analysis tools.
Follow

Get every new post delivered to your Inbox.