% vim: set sts=4 et:
\input{./header}
\input{./shortcuts}
\graphicspath{{images/}{image_install/}}
\newcommand{\sheetnr}{1}
\newcommand{\issued}{21.09.2016}
\newcommand{\dueUni}{28.09.2016 16:00}
%\newcommand{\version}{1} % if you need to release a corrected version, uncomment and increase this counter
\newcommand{\dd}[1][]{\text{d}^{#1}}
\newcommand{\Mod}{{\rm mod\,}}
\DeclareMathOperator{\tr}{Tr}
\showsolutions
\startsheet
\setcounter{exercise}{0}
\exercise[3]{Conservation laws}
One other quantum number that we did not discuss is Izospin.
To install a virtual Linux machine on Linux, MacOS and Windows, follow these steps:
%
\begin{subtasks}
%
\task Follow this link \url{http://www.physik.uzh.ch/data/mchrzasz/Teaching/MC2016/}, download the zip file “VM\_MC2016.zip" and unzip the folder.
%
\task Follow this link \url{https://www.virtualbox.org/wiki/Downloads} and download {\it virtualbox} (select “VirtualBox 5.1.6 for OS X hosts").
%
\task Install {\it virtualbox}, following the instructions of the installer.
\begin{center}
\begin{minipage}{0.45\textwidth}
\includegraphics[width=0.97 \textwidth]{virtual_box_1.png}
\end{minipage}
\begin{minipage}{0.45\textwidth}
\includegraphics[width=0.97 \textwidth]{virtual_box_3.png}
\end{minipage}
\end{center}
%
\task Open {\it virtualbox} and press the “New" button to start the installation of a new virtual machine.
\begin{center}
\begin{minipage}{0.45\textwidth}
\includegraphics[width=0.97 \textwidth]{instal_1.png}
\end{minipage}
\end{center}
%
\task Start the installation following the suggestions of the installer, then when required select “use an existing virtual hard disk file" and press "choose a virtual hard disk".
\begin{center}
\begin{minipage}{0.45\textwidth}
\includegraphics[width=0.97 \textwidth]{instal_2.png}
\end{minipage}
\begin{minipage}{0.45\textwidth}
\includegraphics[width=0.97 \textwidth]{instal_3.png}
\end{minipage}
\end{center}
%
\task Browse to the “VM\_MC2016" folder and select “Ubuntu 64-bit.vmdk". Then press “Create".
Note: please keep nonetheless all the other images present in the folder.
\begin{center}
\begin{minipage}{0.45\textwidth}
\includegraphics[width=0.97 \textwidth]{instal_4.png}
\end{minipage}
\begin{minipage}{0.45\textwidth}
\includegraphics[width=0.97 \textwidth]{instal_5.png}
\end{minipage}
\end{center}
%
\task If the installation go smooth, you should end up with a correctly installed virtual machine present in {\it virtualbox} main menu.
\begin{center}
\begin{minipage}{0.45\textwidth}
\includegraphics[width=0.97 \textwidth]{instal_6.png}
\end{minipage}
\end{center}
%
\task Once accessed to the virtual machine, these are the needed username and password:
\begin{center}
\begin{tabular}{l l}
username: & excellent student
\\
password: & student
\end{tabular}
\end{center}
%
\end{subtasks}
\turnpage
\exercise[3]{Floating point representation}
Let us label the numbers in decimal representation with a subscript ‘$10$', in binary representation with a subscript ‘$2$', in hexadecimal representation with a subscript ‘$16$'.
\begin{subtasks}
\task Convert the following integer decimal numbers in hexadecimal and binary representations:
$12_{10}$, $53_{10}$, $123_{10}$, $431_{10}$. (0.75 Pt.)
%$12$, $53$, $123$, $431$.
\task Convert the following binary and hexadecimal integer numbers in decimal representation: $10011_{2}$, $1101_{2}$, $A2_{16}$, $1AD_{16}$. (0.75 Pt.)
\task In {\it binary16}, a number is represented using 16 digits in the following way:
\begin{center}
\includegraphics[width=0.25 \textwidth]{binary_half.png}
\end{center}
In some detail:
\begin{itemize}
\item[-] The first bit represent the sign: $0 \leftrightarrow +$ and $1 \leftrightarrow -$.
\item[-] The exponent is represented with 5 bits. Thus it can be an integer number from 0 to 31. The values 0 (i.e.~00000) and 31 (i.e.~11111) are reserved for special numbers (NaN, infinity, subnormal numbers).
We are thus left with values from 1 to 30. \emph{By convention}, the exponent of the floating number is the number represented by these 5 digits \emph{minus} a bias, in this case 15 (example: if we want to store $2^{-3}$, the exponent is $-3$ and thus we should store $-3+15=12_{10}=01100_2$ in that slot). In this way we can store exponents from $-14$ (stored as $00001_2=1_{10}$) to $+15$ (stored as $11110_2=30_{10}$).
\item[-] The remaining 10 bits are left for the mantissa. \emph{By convention} (with the exception of subnormal numbers), the first significant digit (the one before the dot) is always 1 and is not stored. Thus, if the mantissa stored is $1000000000$, one should read it as $1.100_{2}=1.5_{10}$.
\end{itemize}
%
Try to convert into {\it binary16} the following decimal floating numbers: $0.3125_{10}$, $-431_{10}$. (0.5 Pt.)
\task With respect to the results of the problem ({\it c}), convert to hexadecimal representation the two bytes representing your floating number and discuss the difference in the storage of your float between big endian and little endian. (0.5 Pt.)
\task Discuss in some detail why, using a machine working with {\it half precision} (i.e.~{\it binary16}), one would get the following results:
\begin{center}
\begin{tabular}{l @{$\qquad\qquad\qquad$} l @{$\qquad\qquad\qquad$} l}
INPUT A: & INPUT B: & INPUT C:
\\
float a ,b, c; & float a; & float a, b, c;
\\
a = 2050; & a = 2050; & a = 2050;
\\
b = 1; & for (int i=0; i<10; i++) & b = 0;
\\
c = a+b; &~~~~~~ a = a+1; & for (int i=0; i<10; i++)
\\
& &~~~~~~b = b+1;
\\
OUTPUT A: & OUTPUT B: & c = a+b;
\\
c = 2050; & a = 2050; &
\\
& & OUTPUT C:
\\
& & c = 2060;
\end{tabular}
\end{center}
%
Write down the binary representation of relevant intermediary results. (0.5 Pts.)
\end{subtasks}
\begin{solution}
\begin{subtasks}
\task The answers are:
\begin{center}
\begin{tabular}{| l | l | l |}
\hline
Decimal: & Hexadecimal: & Binary: \\ \hline
$12$ & C & 1100 \\ \hline
$53$ & 35 & 110101 \\ \hline
$123$ & 7B & 1111011 \\ \hline
$431$ & 1AF & 110101111 \\ \hline
\end{tabular}
\end{center}
A simple algorithm to convert an integer $N$ from decimal to hexadecimal is the following:
\begin{enumerate}
\item[1.] set $i=1$.
\item[2.] Compute $h_i = N_{\Mod 16}$, i.e.~the remainder of the integer (Euclidean) division $N\div16$.
\item[3.] Use the hexadecimal “dictionary" to convert $h_i$:
\begin{tabular}{| l | l | l | l | l | l | l | l | l | l | l | l | l | l | l | l | l |}
\hline
$h$: & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 \\
\hline
hex: & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & A & B & C & D & E & F \\
\hline
\end{tabular}
\item[4.] Replace $N \rightarrow (N - h_i)/16$, set $i=i+1$ and go back to step 2 until $N=0$.
\item[5.] The number in hexadecimal representation is: $h_n h_{n-1} \cdots h_2 h_1$
\end{enumerate}
This algorithm is actually valid for every base change.
Let us apply the algorithm above.
$N=12$:
\begin{align*}
& i=1; & \\
& h_1 = 12_{\Mod 16} = 12 \rightarrow \boxed{C}; & \\
& N \rightarrow (N - 12)/16 =0; \\
&{\rm end:~} 12_{10} = \boxed{C_{16}}
\end{align*}
%
$N=53$:
\begin{align*}
& i=1 && i=2 \\
& h_1 = 53_{\Mod 16} = 5 \rightarrow \boxed{5}; & & h_2 = 3_{\Mod 16} = 3 \rightarrow \boxed{3} \\
& N \rightarrow (N - 5)/16 =3; && N \rightarrow (N - 3)/16 =0; \\
&&&{\rm end:~} 53_{10} = \boxed{35_{16}}
\end{align*}
%
$N=123$:
\begin{align*}
& i=1 && i=2 \\
& h_1 = 123_{\Mod 16} = 11 \rightarrow \boxed{B}; & & h_2 = 7_{\Mod 16} = 7 \rightarrow \boxed{7} \\
& N \rightarrow (N - 11)/16 =7; && N \rightarrow (N - 7)/16 =0; \\
&&&{\rm end:~} 123_{10} = \boxed{7B_{16}}
\end{align*}
%
$N=431$:
\begin{align*}
& i=1 && i=2 &&i=3\\
& h_1 = 431_{\Mod 16} = 15 \rightarrow \boxed{F};
&& h_2 = 26_{\Mod 16} = 10 \rightarrow \boxed{A}
&& h_3 = 1_{\Mod 16} = 1 \rightarrow \boxed{1}
\\
& N \rightarrow (N - 11)/16 =26; && N \rightarrow (N - 10)/16 =1; && N \rightarrow (N - 1)/16 =0; \\
&&&&&{\rm end:~} 431_{10} = \boxed{1AF_{16}}
\end{align*}
%
The former algorithm can be applied also for the conversion in binary. One just need to change $\Mod 16 \rightarrow \Mod 2$ in step 2 and to divide by $2$ (not by $16$) in step 4.
$N=12$:
\begin{align*}
& i=1 && i=2 && i=3 && i=4 \\
& h_1 = 12_{\Mod 2} = \boxed{0} && h_2 = 6_{\Mod 2} = \boxed{0}
&& h_3 = 3_{\Mod 2} = \boxed{1} && h_4 = 1_{\Mod 2} = \boxed{1} \\
& N \rightarrow (N - 0)/2 =6; && N \rightarrow (N - 0)/2 =3;
&& N \rightarrow (N - 1)/2 =1; && N \rightarrow (N - 1)/2 =0; \\
&&&&&&&{\rm end:~} 12_{10} = \boxed{1100_{2}}
\end{align*}
%
$N=53$:
\begin{align*}
& i=1 && i=2 && i=3 && i=4 \\
& h_1 = 53_{\Mod 2} = \boxed{1} && h_2 = 26_{\Mod 2} = \boxed{0}
&& h_3 = 13_{\Mod 2} = \boxed{1} && h_4 = 6_{\Mod 2} = \boxed{0} \\
& N \rightarrow (N - 1)/2 =26; && N \rightarrow (N - 0)/2 =13;
&& N \rightarrow (N - 1)/2 =6; && N \rightarrow (N - 0)/2 =3; \\
%
\\
%
& i=5 && i=6 \\
& h_5 = 3_{\Mod 2} = \boxed{1} && h_6 = 1_{\Mod 2} = \boxed{1} \\
& N \rightarrow (N - 1)/2 =1; && N \rightarrow (N - 1)/2 =0; \\
&&&{\rm end:~} 53_{10} = \boxed{110101_{2}}
\end{align*}
%
$N=123$:
\begin{align*}
& i=1; && i=2 && i=3 && i=4 \\
& h_1 = 123_{\Mod 2} = \boxed{1} && h_2 = 61_{\Mod 2} = \boxed{1}
&& h_3 = 30_{\Mod 2} = \boxed{0} && h_4 = 15_{\Mod 2} = \boxed{1} \\
& N \rightarrow (N - 1)/2 =61; && N \rightarrow (N - 1)/2 =30;
&& N \rightarrow (N)/2 =15; && N \rightarrow (N - 1)/2 =7; \\
%
\\
%
& i=5 && i=6 && i=7\\
& h_5 = 7_{\Mod 2} = \boxed{1} && h_6 = 3_{\Mod 2} = \boxed{1} && h_7 = 1_{\Mod 2} = \boxed{1} \\
& N \rightarrow (N - 1)/2 =3; && N \rightarrow (N-1)/2 =1; && N \rightarrow (N - 1)/2 =0; \\
&&&{\rm end:~} 53_{10} = \boxed{1111011_{2}}
\end{align*}
%
$N=431$:
\begin{align*}
& i=1 && i=2 && i=3 && i=4,5,6,7,8,9 \\
& h_1 = 431_{\Mod 2} = \boxed{1} && h_2 = 215_{\Mod 2} = \boxed{1}
&& h_3 = 107_{\Mod 2} = \boxed{1} && \dots ({\rm see~}N=53) \\
& N \rightarrow (N - 1)/2 =215; && N \rightarrow (N - 1)/2 = 107;
&& N \rightarrow (N )/2 =53; && \dots \\
\\
& {\rm end:~} 431_{10} = \boxed{110101111_{2}}
\end{align*}
%
\task One needs to understand that the decimal representation of an integer is just a short-cut notation. With $124_{10}$ one really means:
\begin{equation*}
124_{10} = 1 \cdot 10^2 + 2 \cdot 10^1 + 4 \cdot 10^0 ~.
\end{equation*}
%
This is valid in \emph{every} basis. Thus is easy to find:
%
\begin{align*}
10011_{2} &= (1 \cdot 2^4 + 0 \cdot 2^3 + 0 \cdot 2^2 + 1 \cdot 2^1 + 1 \cdot 2^0)_{10}
= (16+2+1)_{10} = 19_{10}
\\
1101_{2} &=(1 \cdot 2^3 + 1 \cdot 2^2 + 0 \cdot 2^1 + 1 \cdot 2^0)_{10}
= (8+4+1)_{10} = 13_{10}
\\
A2_{16} &=(A \cdot 16^1 + 2 \cdot 16^0)_{10}
= (10 \cdot 16 + 2)_{10} = 162_{10}
\\
1AD_{16} &=(1 \cdot 16^2 + A \cdot 16^1 + D \cdot 16^0)_{10}
= (1 \cdot 256 + 10 \cdot 16 + 13)_{10} = 429_{10}
\end{align*}
%
\task Before converting a value into a floating number, one should convert it into a binary expression. We already know how to convert $-431_{10}$. To convert a non-integer number $N$ into binary, one can use an extension of the algorithm used in exercise (1a).
\begin{enumerate}
\item[1.] i=0.
\item[2.] Take $\lfloor N \rfloor$ (i.e.~integer part of $N$) and convert it into a binary expression
(call it $h_i$).
\item[3.] Substitute $N \rightarrow 2(N - \lfloor N \rfloor)$.
\item[4.] Set $i=i+1$ and go back to step 2 until $N=0$ or you have reached the desired precision.
\item[5.] Your number is $h_0. h_1 h_2 \dots h_n$
\end{enumerate}
%
Let us convert $0.3125$ with the mentioned algorithm:
%
\begin{align*}
& i=0 && i=1 && i=2 \\
& h_0 = \lfloor 0.3125 \rfloor = \boxed{0} && h_1 = \lfloor 0.625 \rfloor = \boxed{0}
&& h_2 = \lfloor 1.25 \rfloor = \boxed{1} \\
& N \rightarrow 2(N - \lfloor N \rfloor) = 0.625; && N \rightarrow 2(N - \lfloor N) \rfloor) = 1.25;
&& N \rightarrow 2(N - \lfloor N) \rfloor) = 0.5; \\
\\
& i=3 && i=4 \\
& h_3 = \lfloor 0.5 \rfloor = \boxed{0} && h_1 = \lfloor 1 \rfloor = \boxed{1}\\
& N \rightarrow 2(N - \lfloor N \rfloor) = 1; && N \rightarrow 2(N - \lfloor N) \rfloor = 0;
\\
&&& {\rm end:~} 0.3125_{10} = \boxed{0.0101_{2}}
\end{align*}
%
Thus $0.3125_{10} = 0.0101_{2} = (1.01 \cdot 2^{-2})_2$. Thus:
%
\begin{itemize}
\item[-] The sign is $+ \rightarrow 0$
\item[-] The exponent is $-2$. Exponent+bias: $-2+15=13=01101_2$.
\item[-] The mantissa is $1.010$. The first digit ($1.$) is not stored, and we store $0100000000$.
\end{itemize}
%
Thus we have:
%
\begin{equation*}
0.3125_{10} \rightarrow \underbrace{0}_{\rm sign}
\underbrace{01101}_{\rm exp+bias}
\underbrace{0100000000}_{\rm mantissa}
\rightarrow \underbrace{00110101}_{\rm byte~1}
~ \underbrace{00000000}_{\rm byte~2}
\rightarrow \underbrace{35~~00}_{\rm hexadecimal}
\end{equation*}
%
For $-431_{10}$ the exercise is similar. We have already computed $431_{10}=110101111 = 1.10101111 \cdot 2^{8}$. Thus:
%
\begin{itemize}
\item[-] The sign is $- \rightarrow 1$
\item[-] The exponent is $8$. Exponent+bias: $8+15=23=10111_2$.
\item[-] The mantissa is $1.10101111$. The first digit ($1.$) is not stored, and we store $1010111100$.
\end{itemize}
%
Thus we have:
%
\begin{equation*}
-431_{10} \rightarrow \underbrace{1}_{\rm sign}
\underbrace{10111}_{\rm exp+bias}
\underbrace{1010111100}_{\rm mantissa}
\rightarrow \underbrace{11011110}_{\rm byte~1}
~ \underbrace{10111100}_{\rm byte~2}
\rightarrow \underbrace{\rm DE~~BC}_{\rm hexadecimal}
\end{equation*}
%
\task We have already found the hexadecimal bytes representation for our floating numbers: $0.3125_{10}=35~00$ and $-431_{10}={\rm DE~BC}$.
In big endian, these bytes would be sequentially stored in the memory “from left to right", while in little endian the sequential storage would go in the other direction. Explicitly:
%
\begin{align*}
0.3125_{10} \rightarrow ~& {\rm big~endian:~}
\underbrace{\boxed{35}}_{\rm slot~i}~\underbrace{\boxed{00}}_{\rm slot~i+1}
&
-431_{10} \rightarrow ~& {\rm big~endian:~}
\underbrace{\boxed{\rm DE}}_{\rm slot~i}~\underbrace{\boxed{\rm BC}}_{\rm slot~i+1}
\\
\rightarrow ~& {\rm little~endian:~}
\underbrace{\boxed{00}}_{\rm slot~i}~\underbrace{\boxed{35}}_{\rm slot~i+1}
&
\rightarrow ~& {\rm little~endian:~}
\underbrace{\boxed{\rm BC}}_{\rm slot~i}~\underbrace{\boxed{\rm DE}}_{\rm slot~i+1}
\end{align*}
%
\task
The number $2050$ expressed in binary is $100000000010$.
In {\it binary16} its representation is:
%
\begin{equation}
\underbrace{0}_{\rm sign}
\underbrace{11010}_{\rm exp+bias}
\underbrace{0000000001}_{\rm mantissa}
~~\Rightarrow~~
+ \;
2^{26 - 15} \times
1.0000000001
=
1.0000000001 \times 2^{11}
\end{equation}
%
From this representation is already clear that the {\it binary16} precision doesn't allow to store numbers like $2049$ or $2051$ at all, since this would require a 12 digit precision.
Thus, both in INPUT A and in INPUT B, the code is requiring the machine a precision it cannot reach. As it should be clear from how the number $2050$ is stored, the machine has reached it maximal precision and it cannot store the number $2051$ whatsoever. This means that at each step in which the number $2051$ is met, the machine truncate it consistently with its maximum working precision, returning $2050$.
INPUT C is well written and works fine. Differently from INPUT B, this time the machine works \emph{at first} with numbers of order 1, which are manipulated without difficulties. For example, the {\it binary16} representation of $5$ would be:
%
\begin{equation}
\underbrace{0}_{\rm sign}
\underbrace{10001}_{\rm exp+bias}
\underbrace{0100000000}_{\rm mantissa -1}
~~\Rightarrow~~
+ \;
2^{17 - 15} \times
1.0100000000
=
1.01 \times 2^2 = 101_2
\end{equation}
%
where indeed $101_2=5_{10}$. After having dealt with all order-1 numbers, it finally sums them to 2050, getting 2060 which is a perfectly storable number.
In conclusion, one should be aware of the bad consequences of requiring the machine to work with more significant digits than its maximum.
\end{subtasks}
\end{solution}
\end{document}
Marcin Chrzaszcz