doc/ratseries/slides/slide3.tex

   1 \magnification=\magstep3
   2 \hsize=19truecm
   3 \vsize=19truecm
   4 \nopagenumbers
   5 \parindent=0mm
   6 \font\eins=cmb10 scaled \magstep 3
   7 \font\zwei=cmr12
   8 \font\mini=cmr7
   9 \def\frac#1#2{{{#1} \over {#2}}}
  10 \hbox{}
  11 \vfill
  12
  13 \centerline{\eins Binary Splitting}
  14 \bigskip\bigskip
  15 Recursive algorithm:
  16 \medskip
  17 \centerline{$\displaystyle S_{[n_1,n_2)} = {\sum\limits_{n=n_1}^{n_2-1} \frac{a(n)}{b(n)} \, \frac{p(n_1) \cdots p(n)}{q(n_1) \cdots q(n)}}$}
  18 \medskip
  19 Compute $P = {p(n_1) \cdots p(n_2-1)}$, $Q = {q(n_1) \cdots q(n_2-1)}$,
  20 \vskip 0cm
  21 $B = {b(n_1) \cdots b(n_2-1)}$ and $T$ with
  22 \medskip
  23 \centerline{$\displaystyle S_{[n_1,n_2)} = \frac{T}{B \cdot Q}$}
  24 \bigskip
  25 \quad $n_2 - n_1 < 4$ \quad $\rightarrow$ directly
  26 \medskip
  27 \quad $n_2 - n_1 \geq 4$ \quad $\rightarrow$ split
  28 \medskip
  29 \centerline{$P = P_L \cdot P_R$}
  30 \centerline{$Q = Q_L \cdot Q_R$}
  31 \centerline{$B = B_L \cdot B_R$}
  32 \centerline{$T = B_R \cdot Q_R \cdot T_L + B_L \cdot P_L \cdot T_R$}
  33
  34 \vfill
  35 \hbox{}
  36 \eject
  37
  38 \end