The naive way to compute a^{n} 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_{2}(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^5Unfortunately, finding optimal sequences is a NP-hard problem. See [2] for more.

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

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*

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*