/*  
 *  Find optimal addition chains for exponents between 2 and MAXT
 *  
 *  Mauro Persano - m at fzort dot org
 *  2007-07-04
 *
 */

#include <stdio.h>
#include <string.h>

enum {
	MAXT = 200,	/* max # to search for */
	MAXL = 20	/* max chain size */
};

struct chain {
	int len;
	int chain[MAXL][2];
} chains[MAXT - 1] ;

int nfound;

int
search(int len, int maxlen, int used[], int cur_chain[][2])
{
	int i, a, b, target;
	struct chain *p;

	if (len > maxlen)
		return 0;

	a = used[len - 1];

	for (i = 0; i < len; i++) {
		b = used[i];

		target = a + b;

		if (target > MAXT)
			break;

		cur_chain[len - 1][0] = a;
		cur_chain[len - 1][1] = b;

		if (!chains[target - 2].len) {
			p = &chains[target - 2];

			p->len = len;
			memcpy(p->chain, cur_chain, p->len*sizeof *p->chain);

			if (++nfound == MAXT - 1)
				return 1;
		}

		used[len] = target;

		if (search(len + 1, maxlen, used, cur_chain))
			return 1;
	}

	return 0;
}

int
main(void)
{
	static int chain[MAXL][2], used[MAXT];
	int i, j;
	struct chain *p;

	/* search */

	for (i = 1; ; i++) {
		used[0] = 1;

		if (search(1, i, used, chain))
			break;
	}

	/* dump results */

	for (i = 0; i < MAXT - 1; i++) {
		p = &chains[i];

		printf("+=========================\n");
		printf("|  x^%d\n", i + 2);
		printf("+-------------------------\n");

		for (j = 0; j < p->len; j++)
			printf("|  x^%d = x^%d * x^%d\n",
			  p->chain[j][0] + p->chain[j][1],
			  p->chain[j][0], p->chain[j][1]);

		printf("+-------------------------\n\n\n");
	}

	return 0;
}