path: root/vol2/index.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}

\makeatletter
\newcommand{\biggg}{\bBigg@\thr@@}
\newcommand{\Biggg}{\bBigg@{3.5}}
\makeatother
\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 true
\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 10
\spacing single
\use_hyperref true
\pdf_bookmarks true
\pdf_bookmarksnumbered false
\pdf_bookmarksopen false
\pdf_bookmarksopenlevel 1
\pdf_breaklinks false
\pdf_pdfborder false
\pdf_colorlinks false
\pdf_backref false
\pdf_pdfusetitle true
\papersize custom
\use_geometry true
\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
\paperwidth 198mm
\paperheight 297mm
\leftmargin 23mm
\topmargin 33mm
\rightmargin 43mm
\bottommargin 66mm
\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 2
\paperpagestyle fancy
\tablestyle default
\listings_params "basicstyle={\ttfamily}"
\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 Title
Exercises on 
\emph on
The Art Of Computer Programming
\emph default

\begin_inset Newline newline
\end_inset


\size larger
Volume 2:
 Seminumerical Algorithms
\begin_inset Newline newline
\end_inset

Third Edition
\end_layout

\begin_layout Author
Juan Marín Noguera
\end_layout

\begin_layout Standard
\begin_inset CommandInset toc
LatexCommand tableofcontents

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Note Note
status open

\begin_layout Plain Layout
Equivalent page size can be obtained with the following layouts (in mm):
\end_layout

\begin_layout Plain Layout
\begin_inset Tabular
<lyxtabular version="3" rows="3" columns="7">
<features tabularvalignment="middle">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Height
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Width
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Top
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Bottom
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Inner
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Outer
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Recommended headers
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
297
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
198
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
33
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
66
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
23
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
43
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Fancy
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
210
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
140
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
4
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
8
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
3
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
5
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Empty
\end_layout

\end_inset
</cell>
</row>
</lyxtabular>

\end_inset


\end_layout

\begin_layout Plain Layout
The first one follows Tschichold's canon except for 
\begin_inset Formula $\unit[1]{mm}$
\end_inset

 given to the inner margin from the outer one to account for a minimal folding.
 The golden ratio resulted in way too narrow pages on A5 paper.
\end_layout

\begin_layout Plain Layout
Proposed notation for in-progress:
\end_layout

\begin_layout Plain Layout
\begin_inset listings
inline false
status open

\begin_layout Plain Layout

atom = (
\begin_inset Quotes eld
\end_inset

A
\begin_inset Quotes erd
\end_inset

|
\begin_inset Quotes erd
\end_inset

R
\begin_inset Quotes erd
\end_inset

) ?(
\begin_inset Quotes eld
\end_inset

B
\begin_inset Quotes erd
\end_inset

|
\begin_inset Quotes erd
\end_inset

M
\begin_inset Quotes erd
\end_inset

) ((
\begin_inset Quotes eld
\end_inset

0
\begin_inset Quotes erd
\end_inset

..
\begin_inset Quotes erd
\end_inset

4
\begin_inset Quotes erd
\end_inset

) (
\begin_inset Quotes eld
\end_inset

0
\begin_inset Quotes erd
\end_inset

..
\begin_inset Quotes erd
\end_inset

9
\begin_inset Quotes erd
\end_inset

) / 
\begin_inset Quotes eld
\end_inset

@
\begin_inset Quotes erd
\end_inset

) / 1DIGIT *DIGIT / *1(1DIGIT *DIGIT) 
\begin_inset Quotes eld
\end_inset

..
\begin_inset Quotes erd
\end_inset

 *1(1DIGIT *DIGIT)
\end_layout

\begin_layout Plain Layout

base = atom / 
\begin_inset Quotes eld
\end_inset

(
\begin_inset Quotes eld
\end_inset

 progress 
\begin_inset Quotes eld
\end_inset

)
\begin_inset Quotes erd
\end_inset


\end_layout

\begin_layout Plain Layout

intersection = atom / intersection 
\begin_inset Quotes eld
\end_inset

*
\begin_inset Quotes erd
\end_inset

 atom
\end_layout

\begin_layout Plain Layout

progress = intersection / progress (
\begin_inset Quotes eld
\end_inset

+
\begin_inset Quotes erd
\end_inset

/
\begin_inset Quotes erd
\end_inset

-
\begin_inset Quotes erd
\end_inset

) intersection
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout
An 
\family typewriter
atom
\family default
 represents all/recommended exercises,
 optionally excluding M or HM/excluding HM,
 and up to the given difficulty level/all difficulty levels,
 or else a single exercise with the given number,
 or a range of exercises (both ends inclusive).
 Then 
\family typewriter
*
\family default
 is used for intersection,
 
\family typewriter
+
\family default
 for union,
 and 
\family typewriter
-
\family default
 for set difference.
\end_layout

\end_inset


\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
setcounter{chapter}{2}
\end_layout

\end_inset


\end_layout

\begin_layout Chapter
Random Numbers
\end_layout

\begin_layout Section
Introduction
\end_layout

\begin_layout Standard
\begin_inset CommandInset include
LatexCommand input
filename "3.1.lyx"
literal "false"

\end_inset


\begin_inset Note Note
status open

\begin_layout Plain Layout

\family typewriter
A10+R25+16
\end_layout

\end_inset


\end_layout

\begin_layout Section
Generating Uniform Random Numbers
\end_layout

\begin_layout Subsection
The Linear Congruential Method
\end_layout

\begin_layout Standard
\begin_inset CommandInset include
LatexCommand input
filename "3.2.1.lyx"
literal "false"

\end_inset


\begin_inset Note Note
status open

\begin_layout Plain Layout

\family typewriter
A10+R25
\end_layout

\end_inset


\end_layout

\begin_layout Subsubsection
Choice of modulus
\end_layout

\begin_layout Standard
\begin_inset CommandInset include
LatexCommand input
filename "3.2.1.1.lyx"
literal "false"

\end_inset


\begin_inset Note Note
status open

\begin_layout Plain Layout

\family typewriter
A10+R25
\end_layout

\end_inset


\end_layout

\begin_layout Subsubsection
Choice of multiplier
\end_layout

\begin_layout Standard
\begin_inset CommandInset include
LatexCommand input
filename "3.2.1.2.lyx"
literal "false"

\end_inset


\begin_inset Note Note
status open

\begin_layout Plain Layout

\family typewriter
A10+R25
\end_layout

\end_inset


\end_layout

\begin_layout Subsubsection
Potency
\end_layout

\begin_layout Standard
\begin_inset CommandInset include
LatexCommand input
filename "3.2.1.3.lyx"
literal "false"

\end_inset


\begin_inset Note Note
status open

\begin_layout Plain Layout

\family typewriter
A10+R25
\end_layout

\end_inset


\end_layout

\begin_layout Subsection
Other Methods
\end_layout

\begin_layout Standard
\begin_inset CommandInset include
LatexCommand input
filename "3.2.2.lyx"
literal "false"

\end_inset


\begin_inset Note Note
status open

\begin_layout Plain Layout

\family typewriter
A10+R25
\end_layout

\end_inset


\end_layout

\begin_layout Section
Statistical Tests
\end_layout

\begin_layout Subsection
General Test Procedures for Studying Random Data
\end_layout

\begin_layout Standard
\begin_inset CommandInset include
LatexCommand input
filename "3.3.1.lyx"
literal "false"

\end_inset


\begin_inset Note Note
status open

\begin_layout Plain Layout

\family typewriter
A10+R25
\end_layout

\end_inset


\end_layout

\begin_layout Subsection
Empirical Tests
\end_layout

\begin_layout Standard
\begin_inset CommandInset include
LatexCommand input
filename "3.3.2.lyx"
literal "false"

\end_inset


\begin_inset Note Note
status open

\begin_layout Plain Layout

\family typewriter
A10+R25
\end_layout

\end_inset


\end_layout

\begin_layout Subsection
Theoretical Tests
\end_layout

\begin_layout Standard
\begin_inset CommandInset include
LatexCommand input
filename "3.3.3.lyx"
literal "false"

\end_inset


\begin_inset Note Note
status open

\begin_layout Plain Layout

\family typewriter
A10+R25
\end_layout

\end_inset


\end_layout

\begin_layout Subsection
The Spectral Test
\end_layout

\begin_layout Standard
\begin_inset CommandInset include
LatexCommand input
filename "3.3.4.lyx"
literal "false"

\end_inset


\begin_inset Note Note
status open

\begin_layout Plain Layout

\family typewriter
A10+R25
\end_layout

\end_inset


\end_layout

\begin_layout Section
Other Types of Random Quantities
\end_layout

\begin_layout Subsection
Numerical Distributions
\end_layout

\begin_layout Standard
\begin_inset CommandInset include
LatexCommand input
filename "3.4.1.lyx"
literal "false"

\end_inset


\begin_inset Note Note
status open

\begin_layout Plain Layout

\family typewriter
A10+R25
\end_layout

\end_inset


\end_layout

\begin_layout Subsection
Random Sampling and Shuffling
\end_layout

\begin_layout Standard
\begin_inset CommandInset include
LatexCommand input
filename "3.4.2.lyx"
literal "false"

\end_inset


\begin_inset Note Note
status open

\begin_layout Plain Layout

\family typewriter
A10+R25-16
\end_layout

\end_inset


\end_layout

\begin_layout Section
What Is a Random Sequence?
\end_layout

\begin_layout Standard
\begin_inset CommandInset include
LatexCommand input
filename "3.5.lyx"
literal "false"

\end_inset


\begin_inset Note Note
status open

\begin_layout Plain Layout

\family typewriter
A10+R25
\end_layout

\end_inset


\end_layout

\begin_layout Section
Summary
\end_layout

\begin_layout Standard
\begin_inset CommandInset include
LatexCommand input
filename "3.6.lyx"
literal "false"

\end_inset


\begin_inset Note Note
status open

\begin_layout Plain Layout

\family typewriter
A10+R25
\end_layout

\end_inset


\end_layout

\begin_layout Chapter
Arithmetic
\end_layout

\begin_layout Section
Positional Number Systems
\end_layout

\begin_layout Standard
\begin_inset CommandInset include
LatexCommand input
filename "4.1.lyx"
literal "false"

\end_inset


\begin_inset Note Note
status open

\begin_layout Plain Layout

\family typewriter
A10+R25
\end_layout

\end_inset


\end_layout

\begin_layout Section
Floating Point Arithmetic
\end_layout

\begin_layout Subsection
Single-Precision Calculations
\end_layout

\begin_layout Standard
\begin_inset CommandInset include
LatexCommand input
filename "4.2.1.lyx"
literal "false"

\end_inset


\begin_inset Note Note
status open

\begin_layout Plain Layout

\family typewriter
A10+R25
\end_layout

\end_inset


\end_layout

\begin_layout Subsection
Accuracy of Floating Point Arithmetic
\end_layout

\begin_layout Standard
\begin_inset CommandInset include
LatexCommand input
filename "4.2.2.lyx"
literal "false"

\end_inset


\begin_inset Note Note
status open

\begin_layout Plain Layout

\family typewriter
A10+R25
\end_layout

\end_inset


\end_layout

\begin_layout Subsection
Double-Precision Calculations
\end_layout

\begin_layout Standard
\begin_inset Note Note
status open

\begin_layout Plain Layout
7+0;
 5 (0:28) -> 3d,
 -1/3
\end_layout

\end_inset


\end_layout

\begin_layout Subsection
Distribution of Floating Point Numbers
\end_layout

\begin_layout Standard
\begin_inset Note Note
status open

\begin_layout Plain Layout
10+2;
 5,
 13,
 17 (0:58) -> 5d
\end_layout

\end_inset


\end_layout

\begin_layout Section
Multiple-Precision Arithmetic
\end_layout

\begin_layout Subsection
The Classical Algorithms
\end_layout

\begin_layout Standard
\begin_inset Note Note
status open

\begin_layout Plain Layout
16+4;
 6,
 9,
 11,
 14,
 16,
 19,
 21,
 22,
 30,
 37,
 43 (2:58) -> 12d,
 -2/3
\end_layout

\end_inset


\end_layout

\begin_layout Subsection
Modular Arithmetic
\end_layout

\begin_layout Standard
\begin_inset Note Note
status open

\begin_layout Plain Layout
8+1;
 5,
 7,
 12,
 13 (1:13) -> 4d
\end_layout

\end_inset


\end_layout

\begin_layout Subsection
How Fast Can We Multiply?
\end_layout

\begin_layout Standard
\begin_inset Note Note
status open

\begin_layout Plain Layout
22+3;
 16,
 19 (0:56) -> 10d,
 -2/3
\end_layout

\end_inset


\end_layout

\begin_layout Section
Radix Conversion
\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 Section
Rational Arithmetic
\end_layout

\begin_layout Subsection
Fractions
\end_layout

\begin_layout Standard
\begin_inset Note Note
status open

\begin_layout Plain Layout
3+1;
 5,
 6,
 8 (0:42) -> 2d,
 -2/3
\end_layout

\end_inset


\end_layout

\begin_layout Subsection
The Greatest Common Divisor
\end_layout

\begin_layout Standard
\begin_inset Note Note
status open

\begin_layout Plain Layout
19+4;
 8,
 10,
 14,
 16,
 17,
 18,
 23,
 40 (3:19) -> 13d,
 -1/3
\end_layout

\end_inset


\end_layout

\begin_layout Subsection
Analysis of Euclid's Algorithm
\end_layout

\begin_layout Standard
\begin_inset Note Note
status open

\begin_layout Plain Layout
17+6;
 1,
 17,
 39,
 50 (1:42) -> 9d,
 -2/3
\end_layout

\end_inset


\end_layout

\begin_layout Subsection
Factoring into Primes
\end_layout

\begin_layout Standard
\begin_inset Note Note
status open

\begin_layout Plain Layout
32+6;
 1,
 8,
 18,
 19,
 24,
 26,
 32,
 35 (3:17) -> 17d
\end_layout

\end_inset


\end_layout

\begin_layout Section
Polynomial Arithmetic
\end_layout

\begin_layout Standard
\begin_inset Note Note
status open

\begin_layout Plain Layout
2+0;
 1,
 4,
 5 (0:31) -> 2d,
 -1/3
\end_layout

\end_inset


\end_layout

\begin_layout Subsection
Division of Polynomials
\end_layout

\begin_layout Standard
\begin_inset Note Note
status open

\begin_layout Plain Layout
15+4;
 1,
 3,
 7,
 8,
 12,
 16,
 18 (2:08) -> 9d,
 -1/3
\end_layout

\end_inset


\end_layout

\begin_layout Subsection
Factorization of Polynomials
\end_layout

\begin_layout Standard
\begin_inset Note Note
status open

\begin_layout Plain Layout
17+5;
 1,
 2,
 10,
 12,
 18,
 22,
 34,
 40 (3:22) -> 13d,
 -2/3
\end_layout

\end_inset


\end_layout

\begin_layout Subsection
Evaluation of Powers
\end_layout

\begin_layout Standard
\begin_inset Note Note
status open

\begin_layout Plain Layout
21+4;
 3,
 5,
 9,
 10,
 12,
 24,
 26,
 36,
 39,
 40 (3:37) -> 14d,
 -2/3
\end_layout

\end_inset


\end_layout

\begin_layout Subsection
Evaluation of Polynomials
\end_layout

\begin_layout Standard
\begin_inset Note Note
status open

\begin_layout Plain Layout
29+10;
 2,
 19,
 20,
 24,
 26,
 29,
 33,
 35,
 44,
 45,
 49,
 51,
 70 (5:24) -> 20d
\end_layout

\end_inset


\end_layout

\begin_layout Section
Manipulation of Power Series
\end_layout

\begin_layout Standard
\begin_inset Note Note
status open

\begin_layout Plain Layout
8+5;
 1,
 4,
 5,
 6,
 8,
 11,
 17 (1:59) -> 7d,
 -1/3
\end_layout

\end_inset


\end_layout

\end_body
\end_document