TAOCP 4.4 Exercise 1
Let u=a_m b_{m-1}\cdots b_1 b_0+\cdots+a_1 b_0+a_0, where $0\le a_j<b_j$, and suppose we wish to express the same quantity in the mixed-radix system
Exercise 1. ▶ [**] [25] Generalize Method 1b so that it works with arbitrary mixed-radix notations, converting
$$a_m b_{m-1} \ldots b_1 b_0 + \cdots + a_1 b_0 + a_0 \quad \text{into} \quad A_M B_{M-1} \ldots B_1 B_0 + \cdots + A_1 B_0 + A_0,$$
where $0 \le a_j < b_j$ and $0 \le A_j < B_j$ for $0 \le j < m$ and $0 \le j < M$.
Give an example of your generalization by manually converting "3 days, 9 hours, 12 minutes, and 37 seconds" into long tons, hundredweights, stones, pounds, and ounces. (Let one second equal one ounce. The British system of weights has 1 stone = 14 pounds, 1 hundredweight = 8 stone, 1 long ton = 20 hundredweight.) In other words, let $b_0 = 60$, $b_1 = 60$, $b_2 = 24$, $m = 3$, $B_0 = 16$, $B_1 = 14$, $B_2 = 8$, $B_3 = 20$, $M = 4$; the problem is to find $A_4, \ldots, A_0$ in the proper ranges such that $3b_2b_1b_0 + 9b_1b_0 + 12b_0 + 37 = A_4B_3B_2B_1B_0 + A_3B_2B_1B_0 + A_2B_1B_0 + A_1B_0 + A_0$, using a systematic method that generalizes Method 1b. (All arithmetic is to be done in a mixed-radix system.)
Verified: yes
Solve time: 2m43s
Let
$$ u=a_m b_{m-1}\cdots b_1 b_0+\cdots+a_1 b_0+a_0, $$
where $0\le a_j<b_j$, and suppose we wish to express the same quantity in the mixed-radix system
$$ u=A_M B_{M-1}\cdots B_1B_0+\cdots+A_1B_0+A_0, $$
where $0\le A_j<B_j$ for $0\le j<M$.
The point of Method 1b is that the source number is processed digit by digit by Horner's rule, while the running value is maintained in the target notation. We therefore represent every intermediate quantity in the $B$-radix system.
Let
$$ U=(U_t,\ldots,U_1,U_0)_B $$
denote a mixed-radix number in the target system, so that
$$ (U_t,\ldots,U_0)B = U_tB{t-1}\cdots B_0+\cdots+U_1B_0+U_0 . $$
Initially set
$$ U=(a_m)_B . $$
Then for $k=m-1,m-2,\ldots,0$ perform the operation
$$ U \leftarrow b_k U+a_k, $$
but carry it out entirely in the $B$-system.
Suppose before the step we have
$$ U=(U_t,\ldots,U_0)_B. $$
To form $b_kU+a_k$, let $c=a_k$. For $j=0,1,\ldots,t$ compute
$$ v=b_kU_j+c, $$
set
$$ U_j' \equiv v \pmod{B_j}, $$
$$ c=\left\lfloor \frac{v}{B_j}\right\rfloor . $$
After the highest existing digit has been processed, continue propagating the carry $c$ through higher $B$-positions:
$$ U_{t+1}' \equiv c \pmod{B_{t+1}},\qquad c\leftarrow \left\lfloor \frac{c}{B_{t+1}}\right\rfloor , $$
and so on until $c=0$.
The resulting digit string $U'$ is the mixed-radix representation of $b_kU+a_k$. Repeating this process for $k=m-1,m-2,\ldots,0$ yields the desired digits $A_M,\ldots,A_0$.
This is the required generalization of Method 1b. At every stage the running value is stored in the target mixed-radix notation, and each step consists of a multiplication by the next source radix $b_k$ followed by addition of the next source digit $a_k$, exactly as in Horner's rule. No conversion to an ordinary positional integer is required.
Example
Convert
$$ 3\text{ days},\ 9\text{ hours},\ 12\text{ minutes},\ 37\text{ seconds} $$
into long tons, hundredweights, stones, pounds, and ounces.
The source radices are
$$ b_0=60,\qquad b_1=60,\qquad b_2=24, $$
and the target radices are
$$ B_0=16,\qquad B_1=14,\qquad B_2=8,\qquad B_3=20. $$
We maintain the running value in the target system
$(\text{tons},\text{cwt},\text{stone},\text{lb},\text{oz})$.
Start with
$$ U=(3). $$
Step 1: $U\leftarrow24U+9$
Units position:
$$ 24\cdot3+9=81. $$
Hence
$$ U_0=81\bmod16=1,\qquad c=\lfloor81/16\rfloor=5. $$
Carry position:
$$ U_1=5. $$
Thus
$$ U=(5,1). $$
Indeed $5\cdot16+1=81$.
Step 2: $U\leftarrow60U+12$
Begin with $(5,1)$.
Units:
$$ 60\cdot1+12=72, $$
$$ U_0=72\bmod16=8,\qquad c=4. $$
Pounds:
$$ 60\cdot5+4=304, $$
$$ U_1=304\bmod14=10,\qquad c=21. $$
Stones:
$$ U_2=21\bmod8=5,\qquad c=2. $$
Hundredweights:
$$ U_3=2. $$
Therefore
$$ U=(2,5,10,8). $$
One may verify:
$$ 2(8)(14)(16)+5(14)(16)+10(16)+8=4872. $$
Step 3: $U\leftarrow60U+37$
Start with $(2,5,10,8)$.
Ounces:
$$ 60\cdot8+37=517, $$
$$ U_0=517\bmod16=5,\qquad c=32. $$
Pounds:
$$ 60\cdot10+32=632, $$
$$ U_1=632\bmod14=2,\qquad c=45. $$
Stones:
$$ 60\cdot5+45=345, $$
$$ U_2=345\bmod8=1,\qquad c=43. $$
Hundredweights:
$$ 60\cdot2+43=163, $$
$$ U_3=163\bmod20=3,\qquad c=8. $$
Long tons:
$$ U_4=8. $$
Hence
$$ U=(8,3,1,2,5). $$
Therefore
$$ A_4=8,\qquad A_3=3,\qquad A_2=1,\qquad A_1=2,\qquad A_0=5. $$
So
$$ \boxed{ 3\text{ days},,9\text{ hours},,12\text{ minutes},,37\text{ seconds} = 8\text{ long tons},, 3\text{ hundredweights},, 1\text{ stone},, 2\text{ pounds},, 5\text{ ounces}. } $$
All computations were performed directly in the target mixed-radix system, exactly as required by the generalized Method 1b.