0
$\begingroup$

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?


My workings before the answer:

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$.

$\endgroup$
  • $\begingroup$ The question is a little vague. What would you do with the numbers $00, 00, 01$? Store an infinite string of bits? $\endgroup$ – copper.hat Apr 30 '16 at 22:29
  • $\begingroup$ 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... $\endgroup$ – JMoravitz Apr 30 '16 at 22:29
  • $\begingroup$ @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. $\endgroup$ – alan2here Apr 30 '16 at 22:47
  • $\begingroup$ @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. $\endgroup$ – alan2here Apr 30 '16 at 23:37
  • 1
    $\begingroup$ 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 $\endgroup$ – JMoravitz Apr 30 '16 at 23:41
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

$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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.