Assorted tech notes


Optimal Addition Chain Exponentiation

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

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

The average number of operations involved is 1.5*log2(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:

Unfortunately, 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


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:

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):

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):

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

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:

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