Exercise 4.1.33 (There is a carry in the $i$th place iff $\{m/d^{i+1}\}+ \{n/d^{i+1}\} \geq 1$)

Question

Let the positive integers $m$ and $n$ be written in base $d$, say $m =\sum_i a_i d^i$ and $n = \sum_j b_i d^i$. Show that when $m$ and $n$ are added, that there is a carry in the $i$th place (the place corresponding to $d^i$) if and only if $\{m/d^{i+1}\}+ \{n/d^{i+1}\} \geq 1$.

Richard Ganaye · Accepted Answer

\begin{proof} 
We write the integers $m,n,m+n$ in base $d$:
$$m = \sum_{j = 0}^k a_j d^j,\qquad n =  \sum_{j = 0}^k b_j d^j, \qquad m+n =  \sum_{j = 0}^k c_j d^j,$$
where $0 \leq a_i < d, 0 \leq b_i < d, 0 \leq c_i < d$ (we can take the same $k$, greater than the lengths of the representations of $m,n$ and $m+n$ in base $d$).

Reducing modulo $d^{i+1}$, where $0\leq i < k$, we obtain 
$$\sum_{j = 0}^i a_j d^j + \sum_{j = 0}^i b_j d^j \equiv \sum_{j = 0}^i c_j d^j \pmod{ d^{i+1}},$$
 so there is some integer $r_{i+1}$ such that
\begin{align}
\sum_{j = 0}^i a_j d^j + \sum_{j = 0}^i b_j d^j = \sum_{j = 0}^i c_j d^j  + r_{i+1} d^{i+1}.
\end{align}
This equality defines $r_{i+1}$. We put also $r_0 = 0$. We want to compute $c_i, r_{i+1}$, knowing $a_i, b_i$. By equation (1) for two successive values of $i$,
\begin{align*}
&\sum_{j = 0}^i a_j d^j + \sum_{j = 0}^i b_j d^j = \sum_{j = 0}^i c_j d^j  + r_{i+1} d^{i+1},\
&\sum_{j = 0}^{i-1} a_j d^j + \sum_{j = 0}^{i-1} b_j d^j = \sum_{j = 0}^{i-1} c_j d^j  + r_{i} d^{i}.
\end{align*}
By subtracting these two equalities, we obtain
$$(a_i  + b_i) d^i = c_i d^i + r_{i+1} d^{i+1} - r_i d^i,$$
thus 
$$a_i + b_i +r_i = c_i + r_{i+1} d.$$
Since $0 \leq c_i < d$,
$$r_{i+1} \leq \frac{a_i + b_i + r_i}{d} = r_{i+1} + \frac{c_i}{d} < r_{i+1} + 1,$$
so 
$$r_{i+1} = \left \lfloor \frac{a_i + b_i + r_i}{d}  ight floor,$$
and $r_1 =  \left \lfloor \frac{a_0 + b_0 }{d} ight floor = \left \lfloor \frac{a_0 + b_0 + r_0}{d}ight floor $.

To summarize, we compute $c_i, r_i$ by the following induction rules, for $i \in [\![0, k ]\!]$:
\begin{align}
&r_0 = 0\
&
\left\{
\begin{array}{lll}
r_{i+1} &= \left \lfloor \frac{a_i + b_i + r_i}{d}  ight floor &= (a_i + b_i + r_i)\  //\  d,\
c_i &= (a_i +b_i +r_i) - dr_{i+1} &=(a_i +b_i +r_i) \ \%\  d,
\end{array}
ight.
\end{align}
where $ x // y$ and $x \% y$ denote the quotient and remainder in the Euclidean division of $x$ by $y$ (as in computer programs). This is the usual algorithm to compute a sum in base $d$. This shows that $r_{i+1}$ is the carry corresponding to the sum of coefficients of $d^i$, reported to the coefficient $c_{i+1}$ of $m+n$, and this carry satisfies equation (1).

We note that $r_i \geq 0$. Moreover, $r_0 = 0 \leq 1$. If $r_i \leq 1$, then $a_i + b_i +r_i \leq 2d-1$, so $a_i + b_i +r_i < 2d$, thus $r_{i+1} = \left \lfloor \frac{a_i + b_i + r_i}{d}  ight floor \leq 1$. This induction shows that $r_i = 0$ or $r_i = 1$ for all $i$.

\bigskip
Now we can answer to the question.

We note that
\begin{align*}
\left \{ \frac{m}{d^{i}} ight \} &=  \frac{m}{d^{i}}  - \left \lfloor  \frac{m}{d^{i}}  ight floor\
&=\frac{m - d \left \lfloor  \frac{m}{d^{i}}  ight floor}{d^i}.
\end{align*}
Here
\begin{align*}
m &= (a_k d^{k-i} + \cdots +a_i)d^i +a_{i-1} d^{i-1} + \cdots +a_0,
\end{align*}
where $0 \leq a_{i-1} d^{i-1} + \cdots +a_0 < d^i$ (see Problem 31). Therefore 
\begin{align*}
 \left \lfloor  \frac{m}{d^{i}}  ight floor &= a_k d^{k-i} + \cdots +a_i,\
 d^i \left \lfloor  \frac{m}{d^{i}}  ight floor &= a_k d^{k} + \cdots +a_i d^i,\
 m -  d^i \left \lfloor  \frac{m}{d^{i}}  ight floor  &= a_{i-1} d^{i-1} + \cdots +a_0,
 \end{align*}
 Therefore
 $$\left \{ \frac{m}{d^{i}} ight \}  = \frac{a_{i-1} d^{i-1} + \cdots +a_0}{d^i},$$
 and replacing $i$ by $i+1$,
 \begin{align}
 \left \{ \frac{m}{d^{i+1}} ight \}  = \frac{1}{d^{i+1}} \sum_{j = 0}^i a_j d^j.
 \end{align}
Similarly
  \begin{align}
  \left \{ \frac{n}{d^{i+1}} ight \}  = \frac{1}{d^{i+1}} \sum_{j = 0}^i b_j d^j.
   \end{align}
   By equation (1),
   \begin{align*}
   r_{i+1} 
e 0  \iff& r_{i+1}=1\
   \iff& \sum_{j = 0}^i a_j d^j + \sum_{j = 0}^i b_j d^j - \sum_{j = 0}^i c_j d^j  =d^{i+1}\
   \Rightarrow & \sum_{j = 0}^i a_j d^j + \sum_{j = 0}^i b_j d^j   \geq d^{i+1}\
   \end{align*}
   By equations (4) and (5), this implies that
   $$ \left \{ \frac{m}{d^{i+1}} ight \} +  \left \{ \frac{n}{d^{i+1}} ight \} \geq 1.$$
   
   \bigskip
   Conversely, if $ \left \{ \frac{m}{d^{i+1}} ight \} +  \left \{ \frac{n}{d^{i+1}} ight \} \geq 1$, then by the same equations (4) and (5),
 \begin{align}
  \sum_{j = 0}^i a_j d^j + \sum_{j = 0}^i b_j d^j   \geq d^{i+1}.
  \end{align}
   Assume,  for the sake of contradiction,  that $r_{i+1} = 0$. Then equation (1) gives
   $$\sum_{j = 0}^i a_j d^j + \sum_{j = 0}^i b_j d^j = \sum_{j = 0}^i c_j d^j  \leq (d-1)(1 + d + \cdots + d^i) = d^{i+1} - 1,$$
   so 
   $$\sum_{j = 0}^i a_j d^j + \sum_{j = 0}^i b_j d^j < d^{i+1},$$
   in contradiction with (5). Therefore $r_{i+1} 
e 0$.
   
   In conclusion
   $$r_{i+1} 
e 0 \iff  \left \{ \frac{m}{d^{i+1}} ight \} +  \left \{ \frac{n}{d^{i+1}} ight \} \geq 1.$$
\end{proof}

Note: to give an example of the algorithm given by (2) and (3), consider the sum $59237 + 73715 = 132952$. The following Python program compute this sum using (2) and (3):
\begin{verbatim}
d = 10
a = [7, 3, 2, 9, 5, 0]
b = [5, 1, 7, 3, 7, 0]
k = len(a)
c = [0] * len(a) 
          
r = 0
for i in range(k):
    u = a[i] + b[i] + r
    c[i] = u % d
    r    = u // d
         
print(c)
         [2, 5, 9, 2, 3, 1]
\end{verbatim}

Exercise 4.1.33 (There is a carry in the $i$th place iff $\{m/d^{i+1}\}+ \{n/d^{i+1}\} \geq 1$)

Answers

Comments

Exercise 4.1.33 (There is a carry in the $i$th place iff $\{m/d^{i+1}\}+ \{n/d^{i+1}\} \geq 1$)

Answers

Comments

Add answer