Calculating $b_1,b_2,...,b_k$ where $b_i$=$a_1a_2...a_{i-1}a_{i+1}...a_k$ in minimal number of multiplications

Question

Let's suppose we have a set of integers $a_1, a_2, ..., a_k$ in $Z_n^{*}$, and that we define $b_i$ to be the multiplication $a_1a_2...a_{i-1}a_{i+1}...a_k$. Is there a way to calculate the set $\{b_1,...,b_k\}$ in less than $C*k$ multiplications between the $a_i$s? (Where $C$ is some constant).

Answer 1

Well you can do this with $2*k$ multiplications i.e with $C=2$. The algorithm is outlined below:

Initialize $temp = 1$

for i=$1$ to k
do
$b_i$ = temp
temp = temp*$a_i$
end

temp = $1$
for i=k to $1$
do
$b_i$ = temp
temp = temp*$a_i$
end

Example , $k=4$

First Pass

$b_1$ = 1
$b_2$ = $a_1$
$b_3$=$a_1*a_2$
$b_4=a_1*a_2*a_3$

Second Pass (updating the existing values of $b_i$) {temp=$1$}

$b_4=a_1*a_2*a_3$ {temp =$a_4$}
$b_3$=$a_1*a_2*a_4$ {temp=$a_4*a_3$}
$b_2$=$a_1*a_3*a_4$ {temp=$a_4*a_3*a_2$}
$b_1$=$a_2*a_3*a_4${temp=$a_4*a_3*a_2*a_1$}