path: root/vol2/4.3.3.lyx

#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