\documentclass[12pt]{article}
\usepackage{fullpage}
\newcommand{\bea}{\begin{eqnarray*}}
\newcommand{\eea}{\end{eqnarray*}}
% \newcommand{\doteq}{\stackrel{.}{=}}

\title{CSC 371 homework 2 \\
due 9 Oct, 1995}
\author{Dr. Bloch}

\newenvironment{code}{\setlength{\topsep}{0pt}\texttt\bgroup\begin{tabbing}%
longlabel::\= opcode\= extremelylongoperands\= reallyreallylongcomments\kill}%
{\end{tabbing}\egroup}

\begin{document}
\maketitle
\begin{description}
\item[3.8]
\begin{tabular}{|r|r|r|r|}
\hline
\textbf{Binary} & \textbf{Octal} & \textbf{Decimal} & \textbf{Hexadecimal} \\
\hline
\hline
101100 & 054 & 44 & 0x2C \\
\hline
11101100 & 0354 & 236 & 0xEC \\
\hline
1010110111 & 01267 & 695 & 0x2B7 \\
\hline
110011 & 063 & 51 & 0x33 \\
\hline
1011010 & 0132 & 90 & 0x5A \\
\hline
111111 & 077 & 63 & 0x3F \\
\hline
1100011 & 0143 & 99 & 0x63 \\
\hline
101010111111 & 05277 & 2751 & 0xABF \\
\hline
\end{tabular}

\item[3.10]
The price $P$ of storing a number $N$ is $(X-1) \cdot D$ where $X$ is the
radix and $D$ is the number of digits.  The largest number you can store in
$D$ base-$X$ digits is $X^D-1$, so we can solve for $D$ in terms of $X$
and $N$:
\bea
D & = & \left\lceil\log_X(N+1)\right\rceil \\*
& = & \left\lceil\frac{\ln(N+1)}{\ln(X)}\right\rceil \\
P & = & (X-1) \cdot \left\lceil\frac{\ln(N+1)}{\ln(X)}\right\rceil \\*
& \doteq & \frac{(X-1) \cdot \ln(N+1)}{\ln(X)} \\
\frac{dP}{dX} & \doteq & \ln(N+1)\cdot
\frac{\ln(X)-\frac{X-1}{X}}{\ln(X)^2}
\eea
To minimize $P$, we must find a zero of $\frac{dP}{dX}$, \emph{i.e.}
\bea
\ln(X)-\frac{X-1}{X} & = & 0 \\*
\ln(X) & = & \frac{X-1}{X}
\eea
This last equation is satisfied at $X=1$, but that's a useless solution:
with $X=1$, the price per digit is 0 but we need infinitely many digits.
So let's look for any other zeroes of $\frac{dP}{dX}$.
Taking derivatives of both sides, we get
\bea
\frac{1}{X} & <?> & \frac{1}{X^2}
\eea
Since $\frac{1}{X} > \frac{1}{X^2}$ for all $X>1$, it follows that the
$\ln(X)$ grows more rapidly than $\frac{X-1}{X}$, so
$\ln(X)-\frac{X-1}{X}$ can only grow with increasing $X$,
and in particular it'll always be positive for $X>1$.  That is, as $X$
increases, $P$ will increase too, so to minimize $P$ we must choose the
smallest possible $X$.  Since $X$ can only be an integer, and $X=1$
doesn't make sense, we are left with $X=2$ as the next-best choice.

\item[3.12] The basic algorithm for converting any positive number from
decimal to binary is
\begin{verse}
while $(X > 0.0)$ $\{$
   \begin{verse}
   let $n$ be the largest integer such that $2^n \leq X$ \\
   write a 1 in the $n$-th position \\
   update $X = X - 2^n$ \\
   $\}$
   \end{verse}
\end{verse}

Applying this to the specific numbers we're given,
\begin{itemize}
\item $X=64.5$. \\
Since $2^6 = 64 \leq X < 128 = 2^7$, we pick $n=6$,
write $1000000.$, and update $X = X - 64 = 0.5$. \\
Since $2^{-1} = 0.5 \leq X < 1.0 = 2^0$, we pick $n=-1$,
write $1000000.1$, and update $X = X - 0.5 = 0.0$, which terminates the
loop.

\item $X=0.025$. \\
Since $2^{-6} = 0.015625 \leq X < 0.03125 = 2^{-5}$, we pick $n=-6$,
write $0.000001$, and update $X = X - 0.015625 = 0.009375$. \\
Since $2^{-7} = 0.0078125 \leq X < .015625 = 2^{-6}$, we pick $n=-7$,
write $0.0000011$, and update $X = X - 0.0078125 = 0.0015625$. \\
Since $2^{-10} = 0.0009765625 \leq X < 0.001953125 = 2^{-9}$, we pick
$n=-10$, write $0.0000011001$, and update $X = X - 0.0009765625 =
0.0005859375$. \\
Since $2^{-11} = 0.00048828125 \leq X < 0.0009765625 = 2^{-10}$, we
pick $n=-11$, write $0.00000110011$, and update $X = X-0.00048828125 =
0.00009765625$, \\
and so on.

Another approach is somewhat more illuminating in this case.  Note
that $0.025 = \frac{25}{1000}$.  We can also find the
solution by simply dividing $25$ by $1000$ using ordinary long division in
base 2.  Writing $25$ and $1000$ in base 2 we get $11001$ and
$1111101000$ respectively, so
\pagebreak
% \begin{verbatim}
%            0.0000011001100 ...
%            -------------------
%    101000 |1.0000000000000 ...
%            - 101000
%              ------
%               110000
%             - 101000
%               ------
%                 1000000
%                - 101000
%                 -------
%                   110000
%                 - 101000
%                   ------
%                     1000000
%                        ...
% \end{verbatim}
\begin{verbatim}
                      0.0000011001 ...
                  --------------------
      1111101000 |11001.0000000000 ...
                 - 1111 101000
                  ------------
                   1001 0110000
                  - 111 1101000
                   ------------
                      1 1001000000
                         ...
\end{verbatim}

In this form, it becomes obvious that the binary expansion will repeat
the pattern $0011$ forever, so the answer could be written
$0.000\overline{0011}$.  

We might have noticed that $0.025 = \frac{25}{1000} = \frac{1}{40}$ and
done the long division of $1.0000$ by $40$ ($101000$ in base 2) instead;
this, of course, produces the same result.

\item $X=18.0625$.  \\
Since $2^4 = 16 \leq X < 32 = 2^5$, we pick $n=4$, write $10000.$, and
update $X = X - 16 = 2.0625$. \\
Since $2^1 = 2 \leq X < 4 = 2^2$, we pick $n=1$, write $10010.$, and
update $X = X - 2 = 0.0625$. \\
Since $2^{-4} = 0.0625 \leq X < 0.125 = 2^{-3}$, we pick $n=-4$, write
$10010.0001$, and update $X = X - 0.0625 = 0.0$, which terminates the
algorithm.

We can do the same long-division trick on this example, using 
the fraction $\frac{180625}{10000}$; I leave it to the reader to check
that this gives the same result.
\end{itemize}

\item[4.5] A 6-bit unsigned number can range from 0 to $2^6-1 = 63$.
A 6-bit two's complement number can range from $-2^5=-32$ to $2^5-1=31$.

\item[4.7]
I've added an extra column to the following table, containing the binary
representation of the absolute value of the number.

\begin{tabular}{|r|r|r|r|r|}
\hline
$x$ in decimal & $|x|$ in binary & 2's comp. & sign-mag. & 1's comp. \\
\hline
\hline
-68 & 01000100 & 10111100 & 11000100 & 10111011 \\
\hline
108 & 01101100 & 01101100 & 01101100 & 01101100 \\
\hline
-120 & 01111000 & 10001000 & 11111000 & 10000111 \\
\hline
-85 & 01010101 & 10101011 & 11010101 & 10101010 \\
\hline
85 & 01010101 & 01010101 & 01010101 & 01010101 \\
\hline
101 & 01100101 & 01100101 & 01100101 & 01100101 \\
\hline
38 & 00100110 & 00100110 & 00100110 & 00100110 \\
\hline
127 & 01111111 & 01111111 & 01111111 & 01111111 \\
\hline
125 & 01111101 & 01111101 & 01111101 & 01111101 \\
\hline
0 & 00000000 & 00000000 & 00000000 & 00000000 \\
\hline
\end{tabular}

\item[4.9] Given the 16-bit sign-magnitude representation of a number,
the 8-bit sign-magnitude representation of the same number must have
the same sign bit and the same rightmost 7 bits.  However, if any of
bits 8 through 14 of the given 16-bit number (where bit 0 is the
rightmost bit and bit 15 the leftmost) is 1, the absolute value of the
number is too large to represent in 7 bits and so the number cannot be
represented in 8-bit sign-magnitude.

\pagebreak
\item[4.11]
\begin{code}
\# read three integers, add them up, and print the result. \\
\# I/O is done one character at a time. \\
 \\
\> .data \\
sum: \> .word \>  \# the running sum of the numbers \\
ionum: \> .word \> \# buffer used for communicating with I/O routines \\
read\_ret: \> .word \> \# return address for readnum \\
write\_ret: \> .word \> \# return address for writenum \\
 \\
\> .text \\
\_\_start: \> move \> sum,0 \\
\> la \> read\_ret,gotfirst \> \# call readnum \\
\> b \> readnum \\
 \\
gotfirst: \> move \> sum,ionum \> \# sum = number read \\
\> la \> read\_ret,gotsecond \> \# call readnum again \\
\> b \> readnum \\
 \\
gotsecond: \> add \> sum,sum,ionum \> \# sum += number read \\
\> la \> read\_ret,gotthird \> \# call readnum again \\
\> b \> readnum \\
 \\
gotthird: \> add \> ionum,sum,ionum \> \# add sum and number read, \\
\>  \>  \> \# prepare to print result \\
\> la \> write\_ret,end \>  \# call writenum \\
\> b \> writenum \\
 \\
end: \> put \> '$\backslash$n' \\
\> done \\
\\
\> \> \> \# Continued on next page \\
\\
\\
\\
\\
\\
\\
\\
\\
\\
\\
\\
\\
\> .data \>  \> \# variables for readnum procedure \\
ch\_in: \> .byte \\
digit\_in: \> .word \\
 \\
\> .text \\
readnum: \> move \> ionum,0 \> \# based on textbook, p. 185 \\
\> get \> ch\_in \\
procch: \> bgt \> ch\_in,'9',notadigit \\
\> sub \> digit\_in,ch\_in,'0' \\
\> bltz \> digit\_in,notadigit \\
\> mul \> ionum,ionum,10 \\
\> add \> ionum,ionum,digit\_in \\
\> get \> ch\_in \\
\> b \> procch \\
notadigit: \> b \> (read\_ret) \\
 \\
\> .data \> \> \# variables for writenum procedure \\
outstring: \> .space \> 12 \\
pos: \> .word \\
ch\_out: \> .byte \\
digit\_out: \> .word \\
 \\
\> .text \\
writenum: \> la \> pos,outstring \\
\> add \> pos,pos,11 \> \# point to last char \\
\> move \> m[pos],'$\backslash$0' \> \# put terminating null char at end \\
 \\
writeloop: \> rem \> digit\_out,ionum,10 \\
\> add \> ch\_out,digit\_out,'0' \\
\> sub \> pos,pos,1 \\
\> move \> m[pos],ch\_out \> \# insert least-significant digit \\
\> div \> ionum,ionum,10 \\
\> bgtz \> ionum,writeloop \\
 \\
print\_it: \> putc \> m[pos] \>
         \# Now we have a string to print.  \\
\> \> \> \# I'd like to do this with \\
\> \> \> \# "puts m[pos]", but SPIMSAL \\
\> \> \> \# doesn't like that.  So I'll \\
\> \> \> \# write my own "puts". \\
\> add \> pos,pos,1 \\
\> bgtz \> m[pos],print\_it \\
 \\
\> b \> (write\_ret)
\end{code}
\end{description}
\end{document}
