4.2.4 Distribution of Floating Point Numbers

1 files changed, 563 insertions, 0 deletions

diff --git a/vol2/4.2.4.lyx b/vol2/4.2.4.lyx
new file mode 100644
index 0000000..cef46ac
--- /dev/null
+++ b/vol2/4.2.4.lyx
@@ -0,0 +1,563 @@
+#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
+rexerc5[M20]
+\end_layout
+
+\end_inset
+
+Let 
+\begin_inset Formula $U$
+\end_inset
+
+ be a random real number that is uniformly distributed in the interval 
+\begin_inset Formula $0<U<1$
+\end_inset
+
+.
+ What is the distribution of he leading digits of 
+\begin_inset Formula $U$
+\end_inset
+
+?
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+answer 
+\end_layout
+
+\end_inset
+
+Assume the decimal number system,
+ and assume that we don't count the leading 0s.
+ Then,
+ with probability 
+\begin_inset Formula $\frac{9}{10}$
+\end_inset
+
+,
+ 
+\begin_inset Formula $U\geq0.1$
+\end_inset
+
+ and the leading digit will be at the first position,
+ with the same probability for each digit,
+ and with probability 
+\begin_inset Formula $\frac{1}{10}$
+\end_inset
+
+,
+ 
+\begin_inset Formula $U<0.1$
+\end_inset
+
+ and the leading digit is that of 
+\begin_inset Formula $10U$
+\end_inset
+
+,
+ which is also uniformly distributed.
+ If 
+\begin_inset Formula $\ell(U)\in\{1,\dots,9\}$
+\end_inset
+
+ is the leading digit of 
+\begin_inset Formula $U$
+\end_inset
+
+ and 
+\begin_inset Formula $k\in\{1,\dots,9\}$
+\end_inset
+
+,
+ this means that 
+\begin_inset Formula $P(\ell(U)=k)=\frac{9}{10}\frac{1}{9}+\frac{1}{10}P(\ell(U)=k)$
+\end_inset
+
+ and so 
+\begin_inset Formula $P(\ell(U)=k)=\frac{1}{9}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+Therefore all digits have the same probability.
+ In formal terms,
+ if 
+\begin_inset Formula $\ell(U)\in\{1,\dots,9\}$
+\end_inset
+
+ is the leading digit of 
+\begin_inset Formula $U$
+\end_inset
+
+,
+ for 
+\begin_inset Formula $k=1,\dots,9$
+\end_inset
+
+,
+\begin_inset Formula 
+\begin{multline*}
+P(\ell(U)=k)=P(U\geq\tfrac{1}{10})P(\ell(U)=k\mid U\geq\tfrac{1}{10})+P(U<\tfrac{1}{10})P(\ell(U)=k\mid U<\tfrac{1}{10})=\\
+=\frac{9}{10}\cdot\frac{1}{9}+\frac{1}{10}\cdot P(\ell(10U)=k\mid U<0.1)=\frac{1}{10}+\frac{1}{10}P(\ell(U)=k)\implies P(\ell(U)=k)=\frac{1}{9}.
+\end{multline*}
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+rexerc13[M20]
+\end_layout
+
+\end_inset
+
+The floating point multiplication routine,
+ Algorithm 4.2.1M,
+ requires zero or one left shifts during normalization,
+ depending on whether 
+\begin_inset Formula $f_{u}f_{v}\geq1/b$
+\end_inset
+
+ or not.
+ Assuming that the input operands are independently distributed according to the logarithmic law,
+ what is the probability that no left shift is needed for normalization of the result?
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+answer 
+\end_layout
+
+\end_inset
+
+No left shift is required if,
+ and only if,
+ 
+\begin_inset Formula $f_{u}f_{v}\geq1/b$
+\end_inset
+
+.
+ Now,
+ 
+\begin_inset Formula $f_{u}$
+\end_inset
+
+ and 
+\begin_inset Formula $f_{v}$
+\end_inset
+
+ are between 
+\begin_inset Formula $\frac{1}{b}$
+\end_inset
+
+ and 
+\begin_inset Formula $1$
+\end_inset
+
+,
+ and for 
+\begin_inset Formula $x\in[\frac{1}{b},1]$
+\end_inset
+
+,
+ 
+\begin_inset Formula 
+\[
+P(f_{u}<x)=P(\log_{b}f_{u}<\log_{b}x)=P(\log_{b}(bf_{u})<\log_{b}(bx))=\log_{b}(bx)=1+\log_{b}x,
+\]
+
+\end_inset
+
+and similarly for 
+\begin_inset Formula $f_{v}$
+\end_inset
+
+.
+ Let 
+\begin_inset Formula $\varphi(x)\coloneqq1+\log_{b}x$
+\end_inset
+
+,
+\begin_inset Formula 
+\begin{multline*}
+P(f_{u}f_{v}\geq\tfrac{1}{b})=P\big(\log_{b}(f_{u}f_{v})=\log_{b}f_{u}+\log_{b}f_{v}\geq-1\big)=\\
+=\iint_{[\frac{1}{b},1]\times[\frac{1}{b},1]}[\log_{b}f_{u}+\log_{b}f_{v}\geq-1]\text{d}\varphi(f_{u})\,\text{d}\varphi(f_{v})=\\
+=\iint_{[\frac{1}{b},1]\times[\frac{1}{b},1]}[\varphi f_{u}\geq1-\varphi f_{v}]\text{d}\varphi(f_{u})\,\text{d}\varphi(f_{v})=\int_{0}^{1}\int_{1-y}^{1}\text{d}x\,\text{d}y=\int_{0}^{1}y\,\text{d}y=\frac{1}{2}.
+\end{multline*}
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+rexerc17[HM25]
+\end_layout
+
+\end_inset
+
+(M.
+ Tsuji.) Another way to define the value of 
+\begin_inset Formula $\text{Pr}(S(n))$
+\end_inset
+
+ is to evaluate the quantity 
+\begin_inset Formula $\lim_{n\to\infty}(H_{n}^{-1}\sum_{k=1}^{n}[S(k)]/k)$
+\end_inset
+
+;
+ it can be shown that this 
+\emph on
+harmonic probability
+\emph default
+ exists and is equal to 
+\begin_inset Formula $\text{Pr}(S(n))$
+\end_inset
+
+,
+ whenever the latter exists according to Definition 3.5A.
+ Prove that the harmonic probability of the statement 
+\begin_inset Quotes eld
+\end_inset
+
+
+\begin_inset Formula $(\log_{10}n)\bmod1<r$
+\end_inset
+
+
+\begin_inset Quotes erd
+\end_inset
+
+ exists and equals 
+\begin_inset Formula $r$
+\end_inset
+
+.
+ (Thus,
+ initial digits of integers satisfy the logarithmic law 
+\emph on
+exactly
+\emph default
+ in this sense.)
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+answer 
+\end_layout
+
+\end_inset
+
+Consider the integral
+\begin_inset Formula 
+\[
+\int_{1}^{x}\frac{1}{t}\text{d}t=\left[\ln t\right]_{t=1}^{x}=\ln x.
+\]
+
+\end_inset
+
+This means that,
+ for any given 
+\begin_inset Formula $\varepsilon>0$
+\end_inset
+
+,
+ there is a natural number 
+\begin_inset Formula $N$
+\end_inset
+
+ such that,
+ if 
+\begin_inset Formula $m>N$
+\end_inset
+
+,
+ then
+\begin_inset Formula 
+\[
+\left|\ln x-\sum_{10^{m}\leq k<10^{m}x}\frac{1}{10^{m}}\frac{1}{k/10^{m}}\right|=\left|\ln x-\sum_{10^{m}\leq k<10^{m}x}\frac{1}{k}\right|<\varepsilon.
+\]
+
+\end_inset
+
+Now,
+ let 
+\begin_inset Formula $N$
+\end_inset
+
+ be such that the above applies for both 
+\begin_inset Formula $x=1$
+\end_inset
+
+ and 
+\begin_inset Formula $x=10^{r}$
+\end_inset
+
+,
+ and let 
+\begin_inset Formula $n=10^{p}-1$
+\end_inset
+
+ for some positive integer 
+\begin_inset Formula $p>N$
+\end_inset
+
+,
+ then
+\begin_inset Formula 
+\begin{multline*}
+H_{n}^{-1}\sum_{k=1}^{n}\frac{[S(k)]}{k}=\frac{\sum_{0\leq m<p}\sum_{10^{m}\leq k<10^{m+r}}\frac{1}{k}}{\sum_{0\leq m<p}\sum_{10^{m}\leq k<10^{m+1}}\frac{1}{k}}=\frac{\sum_{0\leq m<p}\sum_{10^{m}\leq k<10^{m+r}}\frac{1}{k}/p}{\sum_{0\leq m<p}\sum_{10^{m}\leq k<10^{m+1}}\frac{1}{k}/p}=\\
+=\frac{\sum_{0\leq m<p}(\ln10^{r}+\delta_{m})}{\sum_{0\leq m<p}(\ln10+\delta'_{m})}=\frac{\ln10^{r}+\frac{D}{p}+d_{p}}{\ln10+\frac{D'}{p}+d'_{p}},
+\end{multline*}
+
+\end_inset
+
+where 
+\begin_inset Formula $\delta_{m}\coloneqq\sum_{10^{m}\leq k<10^{m+r}}\frac{1}{k}-\ln10^{r}$
+\end_inset
+
+,
+ 
+\begin_inset Formula $\delta'_{m}\coloneqq\sum_{10^{m}\leq k<10^{m+1}}\frac{1}{k}-\ln10$
+\end_inset
+
+,
+ 
+\begin_inset Formula $D\coloneqq\sum_{0\leq m<N}\delta_{m}$
+\end_inset
+
+,
+ 
+\begin_inset Formula $D'\coloneqq\sum_{0\leq m<N}\delta'_{m}$
+\end_inset
+
+,
+ 
+\begin_inset Formula $d_{p}\coloneqq\sum_{N\leq m<p}\delta_{m}/p$
+\end_inset
+
+,
+ and 
+\begin_inset Formula $d'_{p}\coloneqq\sum_{N\leq m<p}\delta'_{m}/p$
+\end_inset
+
+.
+ Since 
+\begin_inset Formula $|d_{p}|,|d'_{p}|<\varepsilon$
+\end_inset
+
+,
+ if we 
+\begin_inset Formula $p$
+\end_inset
+
+ to be big enough that 
+\begin_inset Formula $\left|D/p\right|,\left|D'/p\right|<\varepsilon$
+\end_inset
+
+,
+ then,
+ let 
+\begin_inset Formula $e\coloneqq\frac{D}{p}+d_{p}$
+\end_inset
+
+ and 
+\begin_inset Formula $e'\coloneqq\frac{D'}{p}+d'_{p}$
+\end_inset
+
+ (so that 
+\begin_inset Formula $|e|,|e'|<2\varepsilon$
+\end_inset
+
+),
+ for small enough 
+\begin_inset Formula $\varepsilon$
+\end_inset
+
+,
+\begin_inset Formula 
+\begin{multline*}
+\left|\frac{\ln10^{r}+e}{\ln10+e'}-\frac{\ln10^{r}}{\ln10}\right|\leq\left|\frac{\ln10^{r}+e}{\ln10+e'}-\frac{\ln10^{r}+e}{\ln10}\right|+\left|\frac{\ln10^{r}+e}{\ln10}-\frac{\ln10^{r}}{\ln10}\right|=\\
+=\left|\ln10^{r}+e\right|\left|\frac{e'}{(\ln10+e')\ln10}\right|+\left|\frac{e}{\ln10}\right|\leq3\frac{\varepsilon}{2\ln10}+\frac{\varepsilon}{\ln10}=\frac{5}{2\ln10}\varepsilon.
+\end{multline*}
+
+\end_inset
+
+Therefore,
+ the limit for the subsequence made up of the elements where 
+\begin_inset Formula $n=10^{p}-1$
+\end_inset
+
+ for some 
+\begin_inset Formula $p$
+\end_inset
+
+ is precisely 
+\begin_inset Formula $\frac{\ln10^{r}}{\ln10}=r$
+\end_inset
+
+.
+ Note that other elements of the sequence can be written in the form
+\begin_inset Formula 
+\[
+\frac{\sum_{0\leq m<p}(\ln10^{r}+\delta_{m})+\sum_{10^{p}\leq k\leq\min\{n,10^{p+r}+1\}}\frac{1}{k}}{\sum_{0\leq m<p}(\ln10+\delta'_{m})+\sum_{10^{p}\leq k\leq n}\frac{1}{k}},
+\]
+
+\end_inset
+
+where 
+\begin_inset Formula $10^{p}\leq n<10^{p+1}-1$
+\end_inset
+
+,
+ but then,
+ dividing this by the element at position 
+\begin_inset Formula $10^{p}-1$
+\end_inset
+
+,
+ we find that the terms in the right hand side of both sums in the numerator and denominator tend to 0,
+ so the whole sequence converges to 
+\begin_inset Formula $r$
+\end_inset
+
+.
+\end_layout
+
+\end_body
+\end_document