# Bit increase when averaging?

I have a given number $N$ of binary numbers, that are stored using a given number $B$ of bits. $B$ is the same for all the numbers.

For example, thease values where $N = 4, B = 4$.

0000 (zero)
0001 (one)
1111 (fifteen)
1001 (nine)


Q: I take the average, how many bits $R$ do I need to store the result with an ordinary binary number?

The average of the above example, adding extra bits to the result:

0000 (zero)
0001 (one)
1111 (fifteen)
1001 (nine)


=

0110.01 (6.25)


One might assume that combining all four, 4 bit numbers requires 16 bits, $R = N * B$, however many of thease values will represent impossible results. For example when $N = B = 4$, $R$ cannot equal $0000.000000000001$.

So I know that in just the case where $N = B = 4$, that $5 < R < 16$.

• The question is a little vague. What would you do with the numbers $00, 00, 01$? Store an infinite string of bits? – copper.hat Apr 30 '16 at 22:29
• If you have $N=3$ and $B=1$, and the numbers $0$, $0$, and $1$, what is their average denoted in binary? Taking this into account, do you wish to invoke any special restrictions on the possible values of $N$? E.g. $N$ must be a power of two... – JMoravitz Apr 30 '16 at 22:29
• @copper.hat and JMoravitz. Assume we are not using $N$ values where this is a problem, such as $N = 3$. If you want to include cases such as $N = 3$, then include enough bits to differentiate it from other possible values. – alan2here Apr 30 '16 at 22:47
• @JMoravitz If you have an answer for specifically where N is a power of two, I'd consider this a good enough answer to mark as correct, and it covers what I need the answer for. – alan2here Apr 30 '16 at 23:37
• If N is a power of two, think about what happens in the averaging process (think of averaging as first adding them all up and then dividing by N). As N is a power of two, this has the effect of shifting the decimal place. Couple this with the fact that the average cannot exceed the maximum value and reach a conclusion – JMoravitz Apr 30 '16 at 23:41

Suppose $p\neq 2$ is a prime factor of $N$ and choose $N$ numbers such that their sum is ${N \over p}$, then the result is ${ 1\over p}$ which has a non terminating binary expansion. Hence the only non problematic $N$ are those that are powers of $2$.

So, suppose $N = 2^n$ for some $n$ (hence dividing by $N$ corresponds to a right shift of $\log_2 N$ bits). Since the sum of the numbers must lie between $0$ and $2^n (2^{B+1}-1)\le 2^{n+B+1} -1$, we see that at most $n+B$ bits are required, and by considering $2^n-1$ copies of the number $2^B$ and one number of $2^B+1$, we see that the sum is $1+2^{n+B}$, hence at least $n+B$ bits are required, hence we see that $B+\log_2 N$ bits are required.

$N ∈ ℕ, B ∈ ℕ$

Where $N$ is a power of two, $N = 2^{∈ℕ}$, then $R = B + log2(N)$.

In some cases, this way will require an infinite number of bits, then $R = ∞$, or at times more practically $R = B + log2(N) + ∈\{0, 1\}$.

256 bytes are able to be included in an average before the result requires 2 bytes to store.