# Computing number of ways to make change

Given a list $$C=[c_1,c_2,\dots,c_k]$$ of positive integers, representing the values of $$k$$ varieties of coins, and a positive integer $$n$$, let $$f(n,C)$$ be the number of handfuls of coins with total value $$n$$. The order within the handful does not matter, and there is an infinite supply of each variety of coin.

What is the state-of-the-art algorithm to compute $$f(n,C)$$?

Equivalently, $$f(n,C)$$ is the number of ways to choose non-negative integers $$x_i$$ so that $$n=\sum_{i=1}^k x_ic_i$$.

The list $$C$$ can have repeats, and the interpretation is that there are two varieties of coin with the same value. For example, $$f(3,[2,1,1])=6$$. Letting $$A$$ and $$B$$ be the coins of value $$1$$, and $$C$$ be the coin of value $$2$$, the $$6$$ possible handfuls are $$(A,A,A),(A,A,B),(A,B,B),(B,B,B),(A,C),(B,C)$$

I can think of two solutions. Which is faster depends on $$n$$ and $$C$$.

• Dynamic programming: Let $$C'$$ denote $$C$$ with its last entry removed. A use-it-or-lose-it argument gives $$f(n,C) = f(n-c_k,C)+f(n,C') .$$ This lets you compute $$f(n,C)$$ by filling out an $$n\times k$$ DP table, which takes $$\boxed{\Theta(nk)}$$ additions and look-ups.

• Matrix exponentiation: I will illustrated in the case $$C=[2,3,4]$$. Letting $$a_n=f(n,C)$$, then $$a_n$$ satisfies the recurrence (see https://cs.stackexchange.com/a/87810/24590) $$a_n = a_{n-2}+a_{n-3}+a_{n-4}-a_{n-5}-a_{n-6}-a_{n-7}+a_{n-9}$$ Any linear recurrence can be solved by computing the $$n^{th}$$ power of a certain matrix. In this case, the recurrence has order $$c_1+\dots+c_k$$, so this algorithm takes $$\boxed{O(\log n \cdot M(c_1+\dots+c_k))}$$ arithmetic operations, where $$M(k)$$ is the number of arithmetic operations required when multiplying two $$k\times k$$ matrices (naively $$M(k)=k^3$$, state of the art is $$k^{2.3728639}$$). We get $$\log n$$ by using exponentiation by squaring.

The second algorithm is asymptotically much better as $$n\to\infty$$, but the first is better when the sum of $$C$$ is large.

Are there any known faster algorithms?

From a theoretical perspective, you can diagonalise (well, decompose to Jordan normal form) to do the matrix power. It costs $$O(M(c_1+\dots+c_k))$$ to decompose, $$O(\log n \cdot (c_1+\dots+c_k))$$ to raise the diagonal matrix to the $$n$$th power, and $$O(M(c_1+\dots+c_k))$$ to finish up.
• Good observation. The eigenvalues of this particular matrix are $c_i^{th}$ roots of unity, so I suppose in order to avoid floating point math and rounding errors you would have to work in $\mathbb{Q}[\zeta]$ where $\zeta$ is an lcm$(c_1,\dots,c_k)$ root of unity. – Mike Earnest Jan 29 at 16:58