Efficient way to compute $n$ products of $n$ numbers

49 Views Asked by At

Say I have a set of $n$ numbers ${a_1, ..., a_n}$. I want to compute $n$ products, where the $i$th product is defined as the product of all elements in the set, except $a_i$. For example, for $n=5$, I want to compute the five products \begin{align} \quad a_2 \cdot a_3 \cdot a_4 \cdot a_5, \\ a_1 \quad \cdot a_3 \cdot a_4 \cdot a_5, \\ a_1 \cdot a_2 \quad \cdot a_4 \cdot a_5, \\ a_1 \cdot a_2 \cdot a_3 \quad \cdot a_5, \\ a_1 \cdot a_2 \cdot a_3 \cdot a_4 \quad. \end{align} In a straightforward manner I can do this with $n \cdot (n-2)$ multiplications. However, I could reuse some partial multiplications that appear in the first equation, store them, and then reduce the number of multiplications in the second equation. My question is what is the most efficient way to do this? Thanks in Advance.