From ae5b7530f812334932173c64ee08c04aa5442e48 Mon Sep 17 00:00:00 2001 From: Juan Marín Noguera Date: Wed, 6 Aug 2025 09:14:25 +0200 Subject: 4.3.2--3: Modular Arithmetic & How Fast Can We Multiply? --- vol2/4.3.3.lyx | 328 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 328 insertions(+) create mode 100644 vol2/4.3.3.lyx (limited to 'vol2/4.3.3.lyx') 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