TAOCP 4.3.2 Exercise 10

Suppose an integer $u$ satisfies $-m/2 < u < m/2$, where $m = m_1 m_2 \cdots m_r$, and consider a modular representation of $u$ using symmetric residues $u_1, \ldots, u_r$ such that $-m_j/2 < u_j < m_...

taocpmathematicsalgorithmsvolume-2math-medium

Section 4.3.2: Modular Arithmetic

Exercise 10. [M25] An integer $u$ that lies in the symmetrical range (10) might be represented by finding the numbers $u_1, \ldots, u_r$ such that $u \equiv u_j \pmod{m_j}$ and $-m_j/2 < u_j < m_j/2$, instead of insisting that $0 \le u_j < m_j$ as in the text. Discuss the modular arithmetic procedures that would be appropriate in connection with such a symmetrical representation (including the conversion process, (24)).

Verified: yes
Solve time: 2m14s

Solution

Suppose an integer $u$ satisfies $-m/2 < u < m/2$, where $m = m_1 m_2 \cdots m_r$, and consider a modular representation of $u$ using symmetric residues $u_1, \ldots, u_r$ such that

$-m_j/2 < u_j < m_j/2 \quad \text{and} \quad u \equiv u_j \pmod{m_j} \quad (1 \le j \le r).$

The usual modular arithmetic formulas for addition, subtraction, and multiplication given in equations (2), (3), and (4) must be adapted to account for the fact that the residues may now be negative.

For addition, consider $u + v$ with residues $u_j$ and $v_j$. The sum of residues satisfies $-m_j < u_j + v_j < m_j$, so the residue of the sum modulo $m_j$ can be computed as

$$ (u_j + v_j) \bmod m_j = \begin{cases} u_j + v_j, & -m_j/2 \le u_j + v_j < m_j/2, \ u_j + v_j - m_j, & u_j + v_j \ge m_j/2, \ u_j + v_j + m_j, & u_j + v_j < -m_j/2. \end{cases} $$

Similarly, for subtraction, $u_j - v_j$ lies in $(-m_j, m_j)$, and the symmetric residue is obtained as

$$ (u_j - v_j) \bmod m_j = \begin{cases} u_j - v_j, & -m_j/2 \le u_j - v_j < m_j/2, \ u_j - v_j - m_j, & u_j - v_j \ge m_j/2, \ u_j - v_j + m_j, & u_j - v_j < -m_j/2. \end{cases} $$

For multiplication, the product $u_j v_j$ lies in $(-(m_j/2)^2, (m_j/2)^2)$, and reduction modulo $m_j$ to the symmetric range $(-m_j/2, m_j/2)$ is accomplished analogously:

$$ (u_j v_j) \bmod m_j = \begin{cases} u_j v_j, & -m_j/2 \le u_j v_j < m_j/2, \ u_j v_j - m_j, & u_j v_j \ge m_j/2, \ u_j v_j + m_j, & u_j v_j < -m_j/2. \end{cases} $$

The conversion process from the symmetric residues $u_j$ to the mixed-radix representation $v_1, \ldots, v_r$ as in equation (24) requires careful treatment of the negative residues. Let $C_j = c_{1j} c_{2j} \cdots c_{j-1,j} \bmod m_j$, as in the notation of Exercise 7. Then the mixed-radix digits are obtained by

$$ v_1 \leftarrow u_1 \bmod m_1, $$

$$ v_2 \leftarrow \bigl(u_2 - (v_1 \bmod m_2)\bigr) C_2 \bmod m_2, $$

$$ v_3 \leftarrow \bigl(u_3 - (v_1 + m_1 v_2) \bmod m_3\bigr) C_3 \bmod m_3, $$

$$ \vdots $$

$$ v_r \leftarrow \bigl(u_r - (v_1 + m_1(v_2 + m_2(v_3 + \cdots + m_{r-2}v_{r-1})\cdots)) \bmod m_r\bigr) C_r \bmod m_r. $$

In each step, the subtraction $u_j - (\text{accumulated sum})$ is performed modulo $m_j$, and the result is reduced to the symmetric interval $(-m_j/2, m_j/2)$. The multiplication by $C_j$ is performed modulo $m_j$, followed by a symmetric reduction if necessary.

This ensures that the reconstructed integer

$$ u = v_1 + m_1 (v_2 + m_2(v_3 + \cdots + m_{r-1} v_r) \cdots) $$

satisfies $-m/2 < u < m/2$, and that each $u_j \equiv u \pmod{m_j}$, as required by equation (26). The symmetric residue arithmetic guarantees that overflow is avoided during intermediate computations, because each operation is confined to the range $(-m_j/2, m_j/2)$.

This completes the solution. ∎