#LyX 2.4 created this file. For more info see https://www.lyx.org/
\lyxformat 620
\begin_document
\begin_header
\save_transient_properties true
\origin unavailable
\textclass book
\begin_preamble
\input defs
\end_preamble
\use_default_options true
\maintain_unincluded_children no
\language english
\language_package default
\inputencoding utf8
\fontencoding auto
\font_roman "default" "default"
\font_sans "default" "default"
\font_typewriter "default" "default"
\font_math "auto" "auto"
\font_default_family default
\use_non_tex_fonts false
\font_sc false
\font_roman_osf false
\font_sans_osf false
\font_typewriter_osf false
\font_sf_scale 100 100
\font_tt_scale 100 100
\use_microtype false
\use_dash_ligatures true
\graphics default
\default_output_format default
\output_sync 0
\bibtex_command default
\index_command default
\float_placement class
\float_alignment class
\paperfontsize default
\spacing single
\use_hyperref false
\papersize default
\use_geometry false
\use_package amsmath 1
\use_package amssymb 1
\use_package cancel 1
\use_package esint 1
\use_package mathdots 1
\use_package mathtools 1
\use_package mhchem 1
\use_package stackrel 1
\use_package stmaryrd 1
\use_package undertilde 1
\cite_engine basic
\cite_engine_type default
\biblio_style plain
\use_bibtopic false
\use_indices false
\paperorientation portrait
\suppress_date false
\justification true
\use_refstyle 1
\use_formatted_ref 0
\use_minted 0
\use_lineno 0
\index Index
\shortcut idx
\color #008000
\end_index
\secnumdepth 3
\tocdepth 3
\paragraph_separation indent
\paragraph_indentation default
\is_math_indent 0
\math_numbering_side default
\quotes_style english
\dynamic_quotes 0
\papercolumns 1
\papersides 1
\paperpagestyle default
\tablestyle default
\tracking_changes false
\output_changes false
\change_bars false
\postpone_fragile_content false
\html_math_output 0
\html_css_as_file 0
\html_be_strict false
\docbook_table_output 0
\docbook_mathml_prefix 1
\end_header

\begin_body

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
rexerc1[25]
\end_layout

\end_inset

Generalize Method 1b so that it works with arbitrary mixed-radix notations,
 converting
\begin_inset Formula 
\begin{align*}
 & a_{m}b_{m-1}\cdots b_{1}b_{0}+\dots+a_{1}b_{0}+a_{0} &  & \text{into} & A_{M}B_{M-1}\cdots B_{1}B_{0}+\dots+A_{1}B_{0}+A_{0},
\end{align*}

\end_inset

where 
\begin_inset Formula $0\leq a_{j}<b_{j}$
\end_inset

 and 
\begin_inset Formula $0\leq A_{J}<B_{J}$
\end_inset

 for 
\begin_inset Formula $0\leq j<m$
\end_inset

 and 
\begin_inset Formula $0\leq J<M$
\end_inset

.
\end_layout

\begin_layout Standard
Give an example of your generalization by manually converting 
\begin_inset Quotes eld
\end_inset

3 days,
 9 hours,
 12 minutes,
 and 37 seconds
\begin_inset Quotes erd
\end_inset

 into long tons,
 hundredweights,
 stones,
 pounds,
 and ounces.
 (Let one second equal one ounce.
 The British system of weights has 
\begin_inset Formula $\unit[1]{stone}=\unit[14]{pounds}$
\end_inset

,
 
\begin_inset Formula $\unit[1]{hundredweight}=\unit[8]{stone}$
\end_inset

,
 
\begin_inset Formula $\unit[1]{long\ ton}=\unit[20]{hundredweight}$
\end_inset

.) In other words,
 let 
\begin_inset Formula $b_{0}=60$
\end_inset

,
 
\begin_inset Formula $b_{1}=60$
\end_inset

,
 
\begin_inset Formula $b_{2}=24$
\end_inset

,
 
\begin_inset Formula $m=3$
\end_inset

,
 
\begin_inset Formula $B_{0}=16$
\end_inset

,
 
\begin_inset Formula $B_{1}=14$
\end_inset

,
 
\begin_inset Formula $B_{2}=8$
\end_inset

,
 
\begin_inset Formula $B_{3}=20$
\end_inset

,
 
\begin_inset Formula $M=4$
\end_inset

;
 the problem is to find 
\begin_inset Formula $A_{4},\dots,A_{0}$
\end_inset

 in the proper ranges such that 
\begin_inset Formula $3b_{2}b_{1}b_{0}+9b_{1}b_{0}+12b_{0}+37=A_{4}B_{3}B_{2}B_{1}B_{0}+A_{3}B_{2}B_{1}B_{0}+A_{2}B_{1}B_{0}+A_{1}B_{0}+A_{0}$
\end_inset

,
 using a systematic method that generalizes Method 1b.
 (All arithmetic is to be done in a mixed-radix system.)
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer 
\end_layout

\end_inset

First,
 we set 
\begin_inset Formula $A_{M},\dots,A_{0}\gets0,\dots,0$
\end_inset

.
 Then,
 for 
\begin_inset Formula $k\gets m-1$
\end_inset

 to 0,
 we do the following:
 first,
 we multiply each 
\begin_inset Formula $A_{i}$
\end_inset

 by 
\begin_inset Formula $b_{k+1}$
\end_inset

,
 except in the first iteration.
 Then,
 we set 
\begin_inset Formula $A_{0}\gets A_{0}+b_{k}$
\end_inset

.
 Finally,
 we normalize the result by setting 
\begin_inset Formula $c\gets0$
\end_inset

 and then,
 for 
\begin_inset Formula $i\gets0$
\end_inset

 to 
\begin_inset Formula $M-1$
\end_inset

,
 
\begin_inset Formula $c'\gets\lfloor A_{i}/B_{i}\rfloor$
\end_inset

,
 
\begin_inset Formula $A_{i}\gets(c+A_{i})\bmod B_{i}$
\end_inset

,
 and 
\begin_inset Formula $c\gets c'$
\end_inset

,
 and then 
\begin_inset Formula $A_{M}\gets A_{M}+c$
\end_inset

.
\end_layout

\begin_layout Standard
We can join the last two steps by not incrementing 
\begin_inset Formula $A_{0}$
\end_inset

 and instead initializing 
\begin_inset Formula $c\gets b_{k}$
\end_inset

,
 as we do in the following example.
 Note that the above algorithm essentially computes 
\begin_inset Formula $(\dots(a_{m}b_{m-1}+a_{m-1})b_{m-2}+\dots+a_{1})b_{0}+a_{0}$
\end_inset

 in the mixed-radix system given by 
\begin_inset Formula $(B_{M-1},\dots,B_{0})$
\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\begin{array}{c|ccccc}
 &  & 20 & 8 & 14 & 16\\
\hline\hline +3 &  &  &  &  & 3\\
\hline \times24 &  &  &  &  & 72\\
+9 &  &  &  & 5 & 1\\
\hline \times60 &  &  &  & 300 & 60\\
+12 &  & 2 & 5 & 10 & 8\\
\hline \times60 &  & 120 & 300 & 600 & 480\\
+37 & 8 & 3 & 1 & 2 & 5
\end{array}
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Note Note
status open

\begin_layout Plain Layout
9+2;
 1,
 3,
 12,
 13,
 19 (2:22) -> 8d,
 -2/3
\end_layout

\end_inset


\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
rexerc3[25]
\end_layout

\end_inset

(D.
 Taranto.) When fractions are being converted,
 there is no obvious way to decide how many digits to give in the answer.
 Design a simple generalization of Method 2a that,
 given two positive radix-
\begin_inset Formula $b$
\end_inset

 fractions 
\begin_inset Formula $u$
\end_inset

 and 
\begin_inset Formula $\epsilon$
\end_inset

 between 0 and 1,
 converts 
\begin_inset Formula $u$
\end_inset

 to a rounded radix-
\begin_inset Formula $B$
\end_inset

 equivalent 
\begin_inset Formula $U$
\end_inset

 that has just enough places 
\begin_inset Formula $M$
\end_inset

 to the right of the radix point to ensure that 
\begin_inset Formula $|U-u|<\epsilon$
\end_inset

.
 (In particular if 
\begin_inset Formula $u$
\end_inset

 is a multiple of 
\begin_inset Formula $b^{-m}$
\end_inset

 and 
\begin_inset Formula $\epsilon=b^{-m}/2$
\end_inset

,
 the value of 
\begin_inset Formula $U$
\end_inset

 will have just enough digits so that 
\begin_inset Formula $u$
\end_inset

 can be recomputed exactly,
 given 
\begin_inset Formula $U$
\end_inset

 and 
\begin_inset Formula $m$
\end_inset

.
 Note that 
\begin_inset Formula $M$
\end_inset

 might be zero;
 for example,
 if 
\begin_inset Formula $\epsilon\leq\frac{1}{2}$
\end_inset

 and 
\begin_inset Formula $u>1-\epsilon$
\end_inset

,
 the proper answer is 
\begin_inset Formula $U=1$
\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer 
\end_layout

\end_inset

We do like Method 2a except that,
 before writing the 
\begin_inset Formula $(k+1)$
\end_inset

th digit,
 we check if 
\begin_inset Formula $u-U<\epsilon$
\end_inset

,
 in which case we stop,
 or whether 
\begin_inset Formula $U+B^{-k}-u<\epsilon$
\end_inset

,
 in which case we add 
\begin_inset Formula $B^{-k}$
\end_inset

 to the result with carry and stop;
 then we remove the trailing zeros.
\end_layout

\begin_layout Standard
In order to implement this efficiently,
 we may use an auxiliary variable 
\begin_inset Formula $d$
\end_inset

 that starts with value 
\begin_inset Formula $u$
\end_inset

,
 and start with 
\begin_inset Formula $M\gets0$
\end_inset

.
 Then,
 if 
\begin_inset Formula $d<\epsilon$
\end_inset

,
 we stop.
 If 
\begin_inset Formula $d>1-\epsilon$
\end_inset

,
 we set 
\begin_inset Formula $k\gets M$
\end_inset

;
 then we set 
\begin_inset Formula $a_{M}\gets a_{M}+1$
\end_inset

 and we stop.
 Otherwise we set 
\begin_inset Formula $M\gets M+1$
\end_inset

,
 
\begin_inset Formula $a_{M}\gets\lfloor Bd\rfloor$
\end_inset

,
 
\begin_inset Formula $d\gets\{Bd\}$
\end_inset

,
 
\begin_inset Formula $\epsilon\gets B\epsilon$
\end_inset

,
 and repeat.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
rexerc12[22]
\end_layout

\end_inset

Invent a rapid pencil-and-paper method for converting integers from ternary notation to decimal,
 and illustrate your method by converting 
\begin_inset Formula $(1212011210210)_{3}$
\end_inset

 into decimal.
 How would you go from decimal to ternary?
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer 
\end_layout

\end_inset

We first group pairs of ternary digits to convert the number to base 9;
 then we operate as in the method for converting octal to decimal but without multiplying by two.
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\begin{array}{rrrrrrr}
1 & 21 & 20 & 11 & 21 & 02 & 10\\
\hline 1 & .7 & 6 & 4 & 7 & 2 & 3\\
- & 1\\
\hline 1 & 6 & .6\\
- & 1 & 6\\
\hline 1 & 5 & 0 & .4\\
- & 1 & 5 & 0\\
\hline 1 & 3 & 5 & 4 & .7\\
- & 1 & 3 & 5 & 4\\
\hline 1 & 2 & 1 & 9 & 3 & .2\\
- & 1 & 2 & 1 & 9 & 3\\
\hline 1 & 0 & 9 & 7 & 3 & 9 & 3\\
- & 1 & 0 & 9 & 7 & 3 & 9\\
\hline  & 9 & 8 & 7 & 6 & 5 & 4
\end{array}
\]

\end_inset


\end_layout

\begin_layout Standard
To convert from decimal to ternary,
 we would operate like this except adding instead of subtracting and using base-9 arithmetic;
 the resulting base-9 number would be converted to ternary by unpacking each digit into two.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
rexerc13[25]
\end_layout

\end_inset

Assume that locations 
\begin_inset Formula $\mathtt{U}+1$
\end_inset

,
 
\begin_inset Formula $\mathtt{U}+2$
\end_inset

,
 ...,
 
\begin_inset Formula $\mathtt{U}+m$
\end_inset

 contain a multiple-precision fraction 
\begin_inset Formula $(.u_{-1}u_{-2}\dots u_{-m})_{b}$
\end_inset

,
 where 
\begin_inset Formula $b$
\end_inset

 is the word size of 
\family typewriter
MIX
\family default
.
 Write a 
\family typewriter
MIX
\family default
 routine that converts this fraction to decimal notation,
 truncating it to 180 decimal digits.
 The answer should be printed on two lines,
 with the digits grouped into 20 blocks of nine each separated by blanks.
 (Use the 
\family typewriter
CHAR
\family default
 instruction.)
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer 
\end_layout

\end_inset

The following code has not been tested.
\end_layout

\begin_layout Standard
\begin_inset listings
inline false
status open

\begin_layout Plain Layout

BUF   ALF  .
    
\end_layout

\begin_layout Plain Layout

      ORIG *+47
\end_layout

\begin_layout Plain Layout

CARRY CON  0
\end_layout

\begin_layout Plain Layout

MAIN  JOV  OFLO
\end_layout

\begin_layout Plain Layout

      ENN1 48     ;
 Index in output buffer
\end_layout

\begin_layout Plain Layout

4H    ENT3 10     ;
 Output iteration counter
\end_layout

\begin_layout Plain Layout

1H    ENT2 m      ;
 Multiplication position
\end_layout

\begin_layout Plain Layout

      ENTX 0
\end_layout

\begin_layout Plain Layout

2H    STX  CARRY  ;
 Multiply one position
\end_layout

\begin_layout Plain Layout

      LDA  =1000000000=
\end_layout

\begin_layout Plain Layout

      MUL  U,2
\end_layout

\begin_layout Plain Layout

      SRC  5
\end_layout

\begin_layout Plain Layout

      ADD  CARRY
\end_layout

\begin_layout Plain Layout

      JNOV *+2
\end_layout

\begin_layout Plain Layout

      INCX 1
\end_layout

\begin_layout Plain Layout

      STA  U,2
\end_layout

\begin_layout Plain Layout

      J2P  2B
\end_layout

\begin_layout Plain Layout

3H    SLAX 5      ;
 Write integer part to buffer
\end_layout

\begin_layout Plain Layout

      CHAR 0
\end_layout

\begin_layout Plain Layout

      STA  BUF+48,1(2:5)
\end_layout

\begin_layout Plain Layout

      STX  BUF+49,1(1:5)
\end_layout

\begin_layout Plain Layout

      INC1 2
\end_layout

\begin_layout Plain Layout

      DEC3 1
\end_layout

\begin_layout Plain Layout

      J3P  1B     ;
 Are we done?
\end_layout

\begin_layout Plain Layout

      INC1 4      ;
 Lines are 24 words,
 not 20
\end_layout

\begin_layout Plain Layout

      OUT  BUF+24,1(18)
\end_layout

\begin_layout Plain Layout

      J1N  4B     ;
 Repeat to print both lines
\end_layout

\end_inset


\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
rexerc19[23]
\end_layout

\end_inset

Let the decimal number 
\begin_inset Formula $u=(u_{7}\dots u_{1}u_{0})_{10}$
\end_inset

 be represented as the binary-coded decimal number 
\begin_inset Formula $U=(u_{7}\dots u_{1}u_{0})_{16}$
\end_inset

.
 Find appropriate constants 
\begin_inset Formula $c_{i}$
\end_inset

 and masks 
\begin_inset Formula $m_{i}$
\end_inset

 so that the operation 
\begin_inset Formula $U\gets U-c_{i}(U\&m_{i})$
\end_inset

,
 repeated for 
\begin_inset Formula $i=1,2,3$
\end_inset

,
 will convert 
\begin_inset Formula $U$
\end_inset

 to the binary representation of 
\begin_inset Formula $u$
\end_inset

,
 where 
\begin_inset Quotes eld
\end_inset


\begin_inset Formula $\&$
\end_inset


\begin_inset Quotes erd
\end_inset

 denotes extraction (bitwise 
\family typewriter
AND
\family default
).
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer 
\end_layout

\end_inset

Let
\begin_inset Formula 
\begin{align*}
c_{1} & =\frac{6}{16}, & c_{2} & =\frac{156}{256}, & c_{3} & =\frac{56536}{66536},\\
m_{1} & =\mathtt{0xF0F0F0F0}, & m_{2} & =\mathtt{0xFF00FF00}, & m_{3} & =\mathtt{0xFFFF0000}.
\end{align*}

\end_inset

The first step converts the number to 
\begin_inset Formula $((u_{7}u_{6})_{10}\dots(u_{1}u_{0})_{10})_{256}$
\end_inset

,
 the second one to 
\begin_inset Formula $((u_{7}u_{6}u_{5}u_{4})_{10}(u_{3}u_{2}u_{1}u_{0})_{10})_{65536}$
\end_inset

,
 and the first one to the desired answer.
\end_layout

\end_body
\end_document