%p4S.tex: 
%begin macros
\baselineskip=14pt
\parskip=10pt
\magnification=\magstephalf
\parindent=0pt
\overfullrule=0in
\def\frac#1#2{{#1 \over #2}}
\def\g{\bigtriangledown}
\def\S{\cal S}
\nopagenumbers
%end macros
 

\centerline
{
\bf Solutions to Attendance Quiz \# 4 for Dr. Z.'s Number Theory
Course for Sept. 16, 2013
}
\bigskip

{\bf 1.} Convert $24$
to binary, in (i) sparse notation (ii) dense notation (iii) positional notation.

{\bf Solution to 1.}
The largest power of $2$  $\leq 24$ is $2^4$, so
$$
B(24)=2^4 +B(24-2^4)= 2^4 + B(24-16)= 2^4 + B(8)  \quad .
$$

The largest power of $2$  $\leq 8$ is $2^3$, so
$$
B(8)=2^3 +B(8-2^3)= 2^3 + B(0)= 2^3 \quad.
$$
(Since $B(0)$ is empty).

Hence

(i) {\bf sparse notation} $24=2^4 + 2^3$ .

To get the {\bf dense notation} we include all the powers of $2$ $\leq 2^4$ that do not show up and stick coefficient $0$.
For those that {\bf do} show up, with stick coefficient $1$

(ii) {\bf dense notation} $24=1 \cdot 2^4 + 1 \cdot 2^3 + 0 \cdot 2^2 + 0 \cdot 2^1 + 0 \cdot 2^0$ .


Finally to get the positional notation, we just write down the coefficients
$$
24= 11000 \quad (base \quad 2) \quad .
$$

{\bf 2.} Use Karatsuba's algorithm (no credit for other methods!), to find
the product
$$
12 \cdot 23 \quad .
$$


{\bf Solution to 2}:

We need to compute
$$
(1 \cdot 10 +2) \cdot (2 \cdot 10 +3)  \quad .
$$
So $a=1, b=2, c=2, d=3$.

$$
a \cdot c = 1 \cdot 2 =2 \quad
$$
$$
b \cdot d = 2 \cdot 3 =6 \quad
$$
$$
(a+b)(c+d)= (1+2)(2+3)= 3 \cdot 5 =15 \quad
$$
$$
(a+b)(c+d)-ab-bd= 15-2-6=7 \quad
$$

Since
$$
(10a+b)(10c+d)= 100ac+ 10((a+b)(c+d)-ac-bd)+ bd
$$
We have
$$
(1 \cdot 10 +2) \cdot (2 \cdot 10 +3) = (2 \cdot 1) \cdot 100 + 10 \cdot 7 + 6 = 276 \quad.
$$

{\bf Ans. to 2.}: $12 \cdot 23=276$.

\end





