1

I'm currently writing a series of equations into python code (I should note, for fun!) and am having trouble understanding this. From my ignorant perspective it looks like a set with a series of variables. The following equation encodes a 16-bit integer value Vp (unsigned, only positive values up to 65,536 ) as an 12-bit (4096) integer value Vi, theoretically taking a value from a linear to logarithmic space.

Equation

If anyone could explain would be incredibly grateful!

Asaf Karagila
  • 393,674
Devereux Gabriel
  • 13
  • 1
    Are you aware of the fact that N >> q means a right shift by q places of the binary expression of N ? – Jean Marie Jan 09 '22 at 14:13
  • You can basically think of this notation as an "if statement" or like a ternary operator (or a case statement...). After the left curly brace there are two columns. The second column tells you under what condition to "choose" a row, and the first column tells you what value to use when you have chosen that row. Have a look at this: https://math.stackexchange.com/questions/1272030/how-to-do-if-and-else-in-math – Izaak van Dongen Jan 09 '22 at 14:14
  • @Jean, To me it seems like it might be! Since they asked about something that "looks like a set with a series of variables". I guess we'll see! OP, are you asking about what the notation with the curly brace with two rows inside it means? – Izaak van Dongen Jan 09 '22 at 14:20
  • @ Izaak van Dongen Looking at it again, you might be right ... – Jean Marie Jan 09 '22 at 14:27
  • @IzaakvanDongen Yes! So the top row and bottom row are an IF statement? If I'm to understand correctly so as a RHS expression it is IF Vp < 1024, Vi=Vp. If Vp >= 1024 follow Jean's equation bellow. – Devereux Gabriel Jan 10 '22 at 01:39
  • That's it ..... – Jean Marie Jan 10 '22 at 09:09
  • @DevereuxGabriel, Yes, exactly. Of course Python has a built-in right bitshift operator, also denoted by >>, so in Python, you could literally write vi = vp if vp < 1024 else 512 * q + (vp >> q), or an if statement containing the assignments vi = vp and vi = 512 * q + (vp >> q). – Izaak van Dongen Jan 10 '22 at 12:42

1 Answers1

0

I have attempted to unveil a part of the mysterious definition. Here is what I have "deciphered".

Let us start from the definition of $q$:

$$q=\log_2(v_p)-9+\varepsilon \ \ \ \ \text{where}\ \ 0\le \varepsilon < 1$$

As a consequence:

$$2^q=2^{\log_2(v_p)}2^{-9}2^{\varepsilon}$$

which is equivalent to :

$$2^q=\frac{v_p}{512} K \ \ \ \ \text{where}\ \ 1\le K < 2\tag{1}$$

The curly brackets clearly mean the two different expressions $v_i$ can take according to the position of $v_p$ with respect to $1024$.

Let us consider the interesting case $v_p \ge 1024$, where we can convert the RHS expression into:

$$v_i=512 q + \frac{v_p}{2^q}\tag{2}$$

(explanations below)

Plugging (1) into (2):

$$v_i=512 q + \frac{512}{K}$$

$$v_i=512(q+K') \ \ \ \ \text{where}\ \ 0.5 < K':=\frac{1}{K} \le 1\tag{3}$$

$$v_i=512(\log_2(v_p)-9+\varepsilon+K') \ \ \ \ \text{where}\ \ \begin{cases}0.5 < K' \le 1 \\ 0\le \varepsilon < 1 \end{cases}\tag{4}$$

where, indeed, $v_i$ is "asymptotically proportional" to $\log(v_p)$.

Explanation for expression (2): Notation N >> q means "right shift by $q$ places of the binary expression of $N$", amounting to a division by $2^q$.

Jean Marie
  • 81,803
  • thank you! A few Q's - the introduction of & K is to take into account the right shit of Vp>>Q? I'm mostly stumped by the bottom statement Q is the integer part of the difference – Devereux Gabriel Jan 10 '22 at 01:57
  • Saying that "$q$ is the integer part of $B$" is the same as saying that "$q=B+\varepsilon$ for a certain positive $\varepsilon < 1$". It is exactly what I say in the very first equation with $B=\log_2(v_p)-9$. – Jean Marie Jan 10 '22 at 07:02
  • No: the rightshift $v_p>>q$ is taken into account when I write it $\frac{v_p}{2^q}$. For example $(v_p>>1) =\frac{v_p}{2}$ (rightshifting by 1 is like dividing by 2) – Jean Marie Jan 10 '22 at 07:05
  • Copy copy, that makes a lot of sense! My last question is, how does one determine the positive value of and/or K. – Devereux Gabriel Jan 10 '22 at 08:19
  • (I have rectified the last formulations in my answer)/ Answer to your last question : One cannot truly determine them. It just gives a bracketing of the answer; as the sum $K'+\varepsilon$ is between $0$ and $1.5$, one gets: $512(\log_2(v_p)-9) <v_i<512(\log_2(v_p)-7.5)$. – Jean Marie Jan 10 '22 at 08:42
  • Maybe connected to your issue: https://janmr.com/blog/2010/09/computing-the-integer-binary-logarithm/ – Jean Marie Jan 10 '22 at 09:12