# Assorted tech notes

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

```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*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:

```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
```
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

## 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