diff options
Diffstat (limited to 'vol2')
| -rw-r--r-- | vol2/4.4.lyx | 973 | ||||
| -rw-r--r-- | vol2/index.lyx | 18 |
2 files changed, 984 insertions, 7 deletions
diff --git a/vol2/4.4.lyx b/vol2/4.4.lyx new file mode 100644 index 0000000..75bda30 --- /dev/null +++ b/vol2/4.4.lyx @@ -0,0 +1,973 @@ +#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 diff --git a/vol2/index.lyx b/vol2/index.lyx index b8b0249..27530d8 100644 --- a/vol2/index.lyx +++ b/vol2/index.lyx @@ -1203,17 +1203,21 @@ Radix Conversion \end_layout \begin_layout Standard +\begin_inset CommandInset include +LatexCommand input +filename "4.4.lyx" +literal "false" + +\end_inset + + \begin_inset Note Note status open \begin_layout Plain Layout -9+2; - 1, - 3, - 12, - 13, - 19 (2:22) -> 8d, - -2/3 + +\family typewriter +A10+R25 \end_layout \end_inset |