Number of bits for a scalar product

Question

let's consider two vectors $v_1[i]$, $v_2[i]$, for $i = 0, 1, ... , N-1$.

Suppose you want to calculate the scalar product between them: it is simply the sum of all $v_1[i] * v_2[i]$ terms $(i=0,...,N-1)$.

Suppose now that each element of $v_1, v_2$ may be written as a $M$ - bits binary number. How many bits are the necessary to express the result?

Answer 1

For each product, the maximum result is

$$ (2^M - 1)^2 = 2^{2M} - 2^{M+1} + 1 $$

Let $q = log_2N \Leftrightarrow N = 2^q$, then the biggest number you might get from your dot product is

$$ N(2^{2M} - 2^{M+1} + 1) = 2^{2M+q} - 2^{M+q+1} + 2^q $$

which means you might need $2M+\mathtt{ceil}(q)$ bits