Fastest algorithm to take the product of all subsets Given n numbers in an array (you can't assume they are integers), I would like to compute the product of all subsets of size n-1.

You can do this by  multiplying all the numbers together and then dividing by each one in turn, as long as none of the numbers is zero.  However, how quickly can you do this with no division?


  If you don't allow division, what is the minimum number of
  arithmetic operations (e.g. multiplication and addition) needed to compute the product of all subsets of size
  n-1?


Clearly you can do it in (n-1)*n multiplications. 

To clarify, the output is n different products and the only operations apart from reading and writing to memory allowed are multiplication, addition and subtraction.  

Example

If the input has three numbers 2,3,5, then the output is three numbers 15 = 3*5, 10 = 2*5 and 6 = 2*3.

Winning criterion

Answers should give an exact formula for the number of arithmetic operations their code will use in terms of n.  To make life simple, I will just plug n = 1000 into your formula to judge its score. The lower the better.

If it's too hard to produce an exact formula for your code, you can just run it for n = 1000 and count the arithmetic operations in  the code.  An exact formula would be best however.

You should add your score for n=1000 to your answer for easy comparison.
Python, 3(n-2) operations, score = 2994

l = list(map(float, input().split()))
n = len(l)

left = [0] * len(l)
right = [0] * len(l)
left[0] = l[0]
right[-1] = l[-1]
for i in range(1,len(l)-1):
  left[i] = l[i] * left[i - 1]
  right[-i-1] = l[-i-1] * right[-i]

result = [0] * len(l)
result[-1] = left[-2]
result[0] = right[1]
for i in range(1, len(l) - 1):
  result[i] = left[i - 1] * right[i+1]

print(result)


The arrays left and right contain the cumulated products of the array from the left and from the right, respectively.

EDIT: Proof that 3(n-2) is the optimal number of operations needed for n >= 2, if we only use multiplication.

We will do that by induction; by the above algorithm, we just have to prove that for n >= 2, 3(n-2) is a lower bound on the number of multiplications needed.

For n = 2, we need at least 0 = 3(2-2) multiplications, so the result is trivial.

Let n > 2, and suppose for n - 1 elements, we need at least 3(n-3) multiplications. Consider a solution for n elements with k multiplications.
Now, we remove the last of these elements as if it was 1, and simplify all multiplications directly by it. We also remove the multiplication leading to the product of all the other elements, since that one is not needed as it can never be used as an intermediate value to get the product of n-2 of the other elements, since division is not allowed. This leaves us with l multiplications, and a solution for n - 1 elements.

By induction hypothesis, we have l >= 3(n-3).

Now, let's have a look at how many multiplications were removed. One of them was the one leading to the product of all elements except the last. Moreover, the last element was used directly in at least two multiplications: if it was used in only one, then it was used when multiplying by an intermediate result consisting in some product of the other elements; let's say, without loss of generality, this this intermediate result included the first element in the product. Then, there is no way to get the product of all the elements but the first, since every product that contains the last element is either the last element, or contains the first element.

We thus have k >= l+3 >= 3(n-2), proving the claimed theorem.