fannkuch C GNU gcc program

Does this C GNU gcc program work for all the input values? Why not? Read ↓ the log. Does this program use optimized assembly code libraries? Is this program small and simple, or very optimized? How could this program be improved?

 N  CPU secs Elapsed secs Memory KB Code B ~ CPU Load
90.05392628  
100.47392628  
115.87392628  
/*
 * The Computer Lannguage Shootout
 * http://shootout.alioth.debian.org/
 * Contributed by Heiner Marxen
 *
 * "fannkuch"	for C gcc
 *
 * $Id: fannkuch.1.gcc.code,v 1.1 2008-08-06 18:32:49 igouy-guest Exp $
 */

#include <stdio.h>
#include <stdlib.h>

#define Int	int
#define Aint	int

    static long
fannkuch( int n )
{
    Aint*	perm;
    Aint*	perm1;
    Aint*	count;
    long	flips;
    long	flipsMax;
    Int		r;
    Int		i;
    Int		k;
    Int		didpr;
    const Int	n1	= n - 1;

    if( n < 1 ) return 0;

    perm  = calloc(n, sizeof(*perm ));
    perm1 = calloc(n, sizeof(*perm1));
    count = calloc(n, sizeof(*count));

    for( i=0 ; i<n ; ++i ) perm1[i] = i;	/* initial (trivial) permu */

    r = n; didpr = 0; flipsMax = 0;
    for(;;) {
	if( didpr < 30 ) {
	    for( i=0 ; i<n ; ++i ) printf("%d", (int)(1+perm1[i]));
	    printf("\n");
	    ++didpr;
	}
	for( ; r!=1 ; --r ) {
	    count[r-1] = r;
	}

#define XCH(x,y)	{ Aint t_mp; t_mp=(x); (x)=(y); (y)=t_mp; }

	if( ! (perm1[0]==0 || perm1[n1]==n1) ) {
	    flips = 0;
	    for( i=1 ; i<n ; ++i ) {	/* perm = perm1 */
		perm[i] = perm1[i];
	    }
	    k = perm1[0];		/* cache perm[0] in k */
	    do {			/* k!=0 ==> k>0 */
		Int	j;
		for( i=1, j=k-1 ; i<j ; ++i, --j ) {
		    XCH(perm[i], perm[j])
		}
		++flips;
		/*
		 * Now exchange k (caching perm[0]) and perm[k]... with care!
		 * XCH(k, perm[k]) does NOT work!
		 */
		j=perm[k]; perm[k]=k ; k=j;
	    }while( k );
	    if( flipsMax < flips ) {
		flipsMax = flips;
	    }
	}

	for(;;) {
	    if( r == n ) {
		return flipsMax;
	    }
	    /* rotate down perm[0..r] by one */
	    {
		Int	perm0 = perm1[0];
		i = 0;
		while( i < r ) {
		    k = i+1;
		    perm1[i] = perm1[k];
		    i = k;
		}
		perm1[r] = perm0;
	    }
	    if( (count[r] -= 1) > 0 ) {
		break;
	    }
	    ++r;
	}
    }
}

    int
main( int argc, char* argv[] )
{
    int		n = (argc>1) ? atoi(argv[1]) : 0;

    printf("Pfannkuchen(%d) = %ld\n", n, fannkuch(n));
    return 0;
}

 about the program

 

 build & benchmark results

BUILD COMMANDS FOR: fannkuch.gcc

Tue Apr 29 16:02:12 PDT 2008

/usr/bin/gcc -pipe -Wall -O3 -fomit-frame-pointer -march=pentium4   fannkuch.c -o fannkuch.gcc_run

=================================================================
COMMAND LINE (%A is single numeric argument):

fannkuch.gcc_run %A


PROGRAM OUTPUT
==============
1234567891011
2134567891011
2314567891011
3214567891011
3124567891011
1324567891011
2341567891011
3241567891011
3421567891011
4321567891011
4231567891011
2431567891011
3412567891011
4312567891011
4132567891011
1432567891011
1342567891011
3142567891011
4123567891011
1423567891011
1243567891011
2143567891011
2413567891011
4213567891011
2345167891011
3245167891011
3425167891011
4325167891011
4235167891011
2435167891011
Pfannkuchen(11) = 51

Revised BSD license