Assorted tech notes

• Optimal Addition Chain Exponentiation
• Dynamic Programming
• "Metaprogramming" with the C Preprocessor

Optimal Addition Chain Exponentiation

The naive way to compute aⁿ involves (n - 1) multiplications.

With a bit of thought, we can do a lot better. This is the so-called binary exponentiation method [1]:

int binpow(int a, int n)
{
	int s, t;

	s = 1;
	t = a;

	while (n) {
		if (n & 1)
			s *= t;
		t *= t;
		n >>= 1;
	}

	return s;
}

The average number of operations involved is 1.5*log₂(n).

Can we do better? Yes. For n=15, it's possible to do it with just 5 operations, instead of the 6 that binpow would require:

a^2 = a * a
a^3 = a^2 * a
a^5 = a^3 * a^2
a^10 = a^5 * a^5
a^15 = a^10 * a^5

Here is a program that searches for optimal sequences. It's not particularly clever. I don't feel too bad about it, though, because there isn't a lot of room for cleverness here (no, dynamic programming does not work).

1. Bruce Schneier, Applied Cryptography
2. http://en.wikipedia.org/wiki/Addition-chain_exponentiation

Dynamic Programming

We want to solve a problem that appeared in xkcd. With a bit of thought, we come up with a top-down, exponential solution for a related problem: finding the number of different orders that cost exactly a given amount:

enum {
	NITEMS = 6
};

int prices[NITEMS] = { 215, 275, 335, 355, 420, 580 };

/*
 *  number of orders that cost exactly 'amount', for the sublist of items
 *  starting at the item with index 'from'
 */
int
norders(int amount, int from)
{
	int r, i, next;

	if (amount == 0) {
		r = 1;
	} else if (from >= NITEMS)
		r = 0;
	} else {
		r = 0;

		for (next = amount; next >= 0; next -= prices[from])
			r += norders(next, from + 1);
	}

	return r;
}

To find the number of orders for 15.05, we call it with norders(1505, 0).

This works, but the run time is exponential. That is okay for a problem size as small as this, but add a few more items to the menu and we're in trouble. Next, we realize that we're solving the same subproblem many times, so we memoize (cache results):

int cache[MAXAMOUNT + 1][NITEMS + 1];

int
norders(int amount, int from)
{
	int r, i, next;

	if (cache[amount][from] != UNINITIALIZED) {
		r = cache[amount][from];
	} else { 
		if (amount == 0) {
			r = 1;
		} else if (from >= NITEMS) {
			r = 0;
		} else {
			r = 0;

			for (next = amount; next >= 0; next -= prices[from])
				r += norders(next, from + 1);
		}

		cache[amount][from] = r;
	}

	return r;
}

Now for the final step: we realize that, by turning the solution upside down, we can fill the cache iteratively - solving smaller subproblems first and using the solutions we get to solve larger ones (this is called dynamic programming):

int
norders(int amount)
{
	int i, j, t, r;

	for (i = 0; i <= amount; i++) {
		for (j = NITEMS; j >= 0; j--) {
			if (i == 0) {
				r = 1;
			} else if (j >= NITEMS) {
				r = 0;
			} else {
				r = 0;

				for (t = i; t >= 0; t -= prices[j])
					r += cache[t][j + 1];
			}

			cache[i][j] = r;
		}
	}

	return cache[amount][0];
}

Now, to actually enumerate the orders, we can work from the data we already have in the cache:

void
dump(int amount, int from, int used[], int nused)
{
	int i, next;

	if (amount == 0) {
		/* print the solution */
		for (i = 0; i < nused; i++)
			printf("%d ", used[i]);
		putchar('\n');
	} else {
		for (i = 0, next = amount; next >= 0; i++, next -= prices[from]) {
			if (i > 0)
				used[nused++] = from;

			/* is there a solution if we add this item to the order? */
			if (cache[next][from + 1] != 0)
				dump(next, from + 1, used, nused);
		}
	}
}

/* ... */

int used[100];

dump(1505, 0, used, 0); /* show orders for 1505; call this after filling the cache, of course */

By the way, there are two orders that cost exactly 15.05.

Wait a minute, we have found an obviously polynomial-time solution for a NP-complete problem. Doesn't this prove that P=NP? Alas, no - see http://en.wikipedia.org/wiki/Subset_sum_problem to understand why.

this needs to be fleshed out a bit more

"Metaprogramming" with the C Preprocessor

C++ folks are always raving about how you can do things such as computing factorials at compile time with C++'s template engine. Well, here they are, those darned factorials computed at compile time, but this time with the venerable C preprocessor:

#ifndef INITIALIZED
    #define INITIALIZED
    #ifndef N
        #define N 11
    #endif
    #define A ((N)&1)
    #define B ((N)>>1&1)
    #define C ((N)>>2&1)
    #define D ((N)>>3&1)
int main(void)
{
    printf("fact(%d) = %d", N,
    #include __FILE__
    );
    return 0;
}
#else /* INITIALIZED */
    (8*D + 4*C + 2*B + A)
    #if A
    	#undef A
        #define A 0
    #else
    	#undef A
        #define A 1
        #if B
	    #undef B
            #define B 0
        #else
	    #undef B
            #define B 1
            #if C
	        #undef C
                #define C 0
            #else
	        #undef C
                #define C 1
                #if D
	            #undef D
                    #define D 0
                #endif
            #endif
        #endif
    #endif
    #if A || B || C || D
        *
        #include __FILE__
    #endif
#endif

We're barely scratching the surface here. Some deranged individual used the preprocessor to implement a Turing machine.

back to my page

Last Update Fri Jul 13 18:17:47 ESAST 2007