1 files changed, 328 insertions, 0 deletions
diff --git a/vol2/4.3.3.lyx b/vol2/4.3.3.lyx
new file mode 100644
index 0000000..80cb542
--- /dev/null
+++ b/vol2/4.3.3.lyx
@@ -0,0 +1,328 @@
+#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
+rexerc16[25]
+\end_layout
+
+\end_inset
+
+Prove that it takes only 
+\begin_inset Formula $O(K\log K)$
+\end_inset
+
+ arithmetic operations to evaluate the discrete Fourier transform (35),
+ even when 
+\begin_inset Formula $K$
+\end_inset
+
+ is not a power of 2.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+answer 
+\end_layout
+
+\end_inset
+
+Let 
+\begin_inset Formula $n=\lceil\log K\rceil$
+\end_inset
+
+,
+ and assume 
+\begin_inset Formula $n\geq5$
+\end_inset
+
+.
+ Since 
+\begin_inset Formula $\log K>4$
+\end_inset
+
+ and 
+\begin_inset Formula $n-\log K<1$
+\end_inset
+
+,
+ we have 
+\begin_inset Formula $\frac{n}{\log K}<\frac{5}{4}$
+\end_inset
+
+ and
+\begin_inset Formula 
+\[
+2^{n}\log2^{n}=2^{n}n\leq2K\cdot\frac{5}{4}\log K=\frac{5}{2}K\log K=O(K\log K).
+\]
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+rexerc19[M23]
+\end_layout
+
+\end_inset
+
+Show how to compute 
+\begin_inset Formula $uv\bmod m$
+\end_inset
+
+ with a bounded number of operations that meet the ground rules of exercise 3.2.1.1–11,
+ if you are also allowed to test whether one operand is less than another.
+ Both 
+\begin_inset Formula $u$
+\end_inset
+
+ and 
+\begin_inset Formula $v$
+\end_inset
+
+ are variable,
+ but 
+\begin_inset Formula $m$
+\end_inset
+
+ is constant.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+answer 
+\end_layout
+
+\end_inset
+
+If 
+\begin_inset Formula $m=1$
+\end_inset
+
+,
+ the result is 0,
+ and if 
+\begin_inset Formula $m=2$
+\end_inset
+
+,
+ the result is that of multiplying the least significant bit of 
+\begin_inset Formula $u$
+\end_inset
+
+ and 
+\begin_inset Formula $v$
+\end_inset
+
+;
+ either way we are done.
+ If 
+\begin_inset Formula $m=3$
+\end_inset
+
+,
+ we may compute 
+\begin_inset Formula $uv\bmod3$
+\end_inset
+
+ with 
+\begin_inset Formula $0\leq u,v<3$
+\end_inset
+
+ with the help of a table and set 
+\begin_inset Formula $s\coloneqq3$
+\end_inset
+
+,
+ and with 
+\begin_inset Formula $m\geq4$
+\end_inset
+
+,
+ there exists an integer 
+\begin_inset Formula $s\geq2$
+\end_inset
+
+ such that 
+\begin_inset Formula $s^{2}\leq m$
+\end_inset
+
+,
+ and we take the greatest such 
+\begin_inset Formula $s$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+Let 
+\begin_inset Formula $n$
+\end_inset
+
+ be such that 
+\begin_inset Formula $2^{2^{n-1}}\leq u,v<2^{2^{n}}$
+\end_inset
+
+,
+ we compute powers 
+\begin_inset Formula $2^{2^{m}}$
+\end_inset
+
+ for 
+\begin_inset Formula $1\leq m\leq n$
+\end_inset
+
+.
+ Then,
+ if 
+\begin_inset Formula $u,v<s$
+\end_inset
+
+,
+ we compute the product directly;
+ otherwise we apply decomposition (2) and use modular arithmetic for the multiplications and additions (if we can do modular subtraction,
+ we can do modular addition since 
+\begin_inset Formula $(u+v)\bmod m=(u-(0-v)\bmod m)\bmod m$
+\end_inset
+
+).
+\end_layout
+
+\begin_layout Standard
+This assumes that we have access to the bit representations of 
+\begin_inset Formula $u$
+\end_inset
+
+ and 
+\begin_inset Formula $v$
+\end_inset
+
+,
+ although the solution in the book assumes we can perform integer division with a dividend greater than 
+\begin_inset Formula $m$
+\end_inset
+
+,
+ which is not a given either,
+ so let's call it even.
+\end_layout
+
+\end_body
+\end_document