trunk/c_dta0/c_dta0.tex

%$Header: /home/dashley/cvsrep/e3ft_gpl01/e3ft_gpl01/dtaipubs/esrgubka/c_dta0/c_dta0.tex,v 1.5 2003/03/03 23:50:43 dtashley Exp $

\chapter[\cdtazeroshorttitle{}]{\cdtazerolongtitle{}}

\label{cdta0}

\beginchapterquote{``Under construction!''}
                     {Under construction!}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}
%Section tag: INT0
\label{cdta0:sint0}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section[Fixed-Period Process Scheduling]
        {Load Balancing For Fixed-Period Process Scheduling Using Integer Counting}
%Section tag: PSI0
\label{cdta0:spsi0}

\index{process scheduling!using integer counting}It happens in a variety of 
contexts in small microcontroller work
that one schedules processes (which may be implemented as subroutines
or functions) with a fixed period
using integer counting.  Such scheduling tends to take the form of
the code snippet in  
Figure \ref{fig:cdta0:spsi0:01}.  Typically a ``master'' scheduling function
is called at a periodic rate, and the scheduled functions are called
once every $T_i$ invocations of the master scheduling function ($T_i$ is
defined later).  Note in the figure that every scheduled function
is called with perfect periodicity, but that the invocation sequence
can be staggered.  Note also in the figure that the comments assume
that the scheduling function is called every 10ms (which is typical in
microcontroller work). 

\begin{figure}
\begin{small}
\begin{verbatim}
/* The following "stagger" values are what we are attempting to
** analytically determine at compile-time so as to minimize the
** maximum CPU time used in the worst-case tick. */ 
#define P1_STAGGER   (0)
#define P2_STAGGER   (0)
#define P3_STAGGER   (0)

/* The periods are fixed and not subject to change.  The periods
** are input to any compile-time algorithm employed. */
#define P1_PERIOD    (2)   /* Every   20ms.            */
#define P2_PERIOD    (5)   /* Every  100ms.            */
#define P3_PERIOD  (100)   /* Every 1000ms = 1 second. */

/* These are the integer counters.  Their initial load values, which
** determine the staggering, are the parameters we seek to
** determine. */
static unsigned char p1_ctr = P1_STAGGER;
static unsigned char p2_ctr = P2_STAGGER;
static unsigned char p3_ctr = P3_STAGGER;

/* This is the master scheduling function called every 10ms.  It 
** calls the periodic functions.  Note that this is an integer
** counting problem. */
void master_scheduling_function(void)
   {
   p1_ctr++;
   if (p1_ctr >= P1_PERIOD)
      {
      Process_1();  /* Call the process.   */
      p1_ctr = 0;   /* Reset the counter.  */
      }
   p2_ctr++;
   if (p2_ctr >= P2_PERIOD)
      {
      Process_2();  /* Call the process.   */
      p2_ctr = 0;   /* Reset the counter.  */
      }
   p3_ctr++;
   if (p3_ctr >= P3_PERIOD)
      {
      Process_3();  /* Call the process.   */
      p3_ctr = 0;   /* Reset the counter.  */
      }
   }
\end{verbatim}
\end{small}
\caption{Code Snippet Illustrating Fixed-Period Integer Counter Process Scheduling
        (3 Processes)}
\label{fig:cdta0:spsi0:01}
\end{figure}


It is easy to see from Figure \ref{fig:cdta0:spsi0:01} that it may happen
on a single invocation of the master scheduling function that several or all of 
the processes are scheduled.  If the scheduling of the
processes is not staggered, this will happen for the first time
on the invocation (or ``tick'')
corresponding to the least common multiple of all of the periods.  In
the case of Figure \ref{fig:cdta0:spsi0:01}, $LCM(2,5,100) = 100$, and so
on the hundredth invocation of the master scheduling function, all three processes will
run.  It may be undesirable to run all three processes on the same invocation of
the master scheduling function, because this may require a large amount of CPU time.
The general question to which we seek an answer is:  \emph{How should the
stagger values be chosen so as to minimize the maximum amount of CPU
time taken on any invocation of the master scheduling function?}

We denote the set of $N$ processes that we must schedule
by $\{ P_1, P_2, \ldots , P_N \}$.  
Process $P_i$ has period $T_i$ (measured in invocations 
or ``ticks'' of
the master scheduling function, or ``ticks'').  Note that
$T_i$ is dimensionless.  

Each process $P_i$ also has cost
$\tau_i$ 
(the cost is usually the execution
time of the function, but could in principle represent any property of
interest).  Note that there is no required relationship between 
$\{ T_i \}$ and $\{ \tau_i \}$, as we are not determining schedulability.
Thus $\{ \tau_i \}$ may be specified in any time unit, or it may not
represent time at all.

We agree that each invocation of the master scheduling function
is one ``tick'' in discrete time, and that the first invocation
of the master scheduling function is denoted $t_1$ or $t=1$.
With no staggering ($z_i = 0$) each process $P_i$ will run
whenever

\begin{equation}
\label{eq:cdta0:spsi0:01}
t \bmod T_i = 0 .
\end{equation}

We may modify the invocation sequence of a process $P_i$ by 
varying a stagger value, which we denote $z_i$.  The stagger value
specifies by how many ticks we will advance the invocation of
$P_i$.  When considering stagger values, each process $P_i$ will
run whenever

\begin{equation}
\label{eq:cdta0:spsi0:02}
(t + z_i) \bmod T_i = 0 .
\end{equation}

At each tick, each process $P_i$ is either scheduled to run or not scheduled
to run.  We define an infinite row vector, called the \emph{uncosted invocation
sequence} (or simply the \emph{invocation sequence}) 
and denoted $\rho_i(z_i)$, which contains a `1' in each column corresponding
to a tick when the process $P_i$ run or `0' if it does not run.  For example,
if $T_1 = 3$, 

\begin{eqnarray}
\nonumber
\rho_1 = \rho_1(0) & = & [ \; 0 \; 0 \; 1 \; 0 \; 0 \; 1 \; 0 \; 0 \; 1 \; 0 \; 0 \; \ldots \; ] \\
\label{eq:cdta0:spsi0:03}
\rho_1(1) & = & [ \; 0 \; 1 \; 0 \; 0 \; 1 \; 0 \; 0 \; 1 \; 0 \; 0 \; 1 \; \ldots \; ] \\
\nonumber
\rho_1(2) & = & [ \; 1 \; 0 \; 0 \; 1 \; 0 \; 0 \; 1 \; 0 \; 0 \; 1 \; 0 \; \ldots \; ] \\
\nonumber
\rho_1(3) & = & [ \; 0 \; 0 \; 1 \; 0 \; 0 \; 1 \; 0 \; 0 \; 1 \; 0 \; 0 \; \ldots \; ]
\end{eqnarray}

\noindent{}We define but avoid using stagger values $z_i \geq T_i$, but as
(\ref{eq:cdta0:spsi0:03}) shows, when it is necessary we define these so that
$\rho_i(z_i) = \rho_i(z_i \bmod T_i)$.  Also as shown in (\ref{eq:cdta0:spsi0:03}),
we use that notation
that $\rho_i = \rho_i(0)$. 

We define the \emph{costed invocation sequence}, denoted 
$\overline{\rho_i}(z_i)$, as the infinite row
vector similar to (\ref{eq:cdta0:spsi0:03}) but where
the cost $\tau_i$ is used in place of `1' when a process $P_i$ runs.
For example, if $T_1=3$ and $\tau_i = 5$,

\begin{eqnarray}
\nonumber
\overline{\rho_1} = 
\overline{\rho_1}(0) & = & [ \; 0 \; 0 \; 5 \; 0 \; 0 \; 5 \; 0 \; 0 \; 5 \; 0 \; 0 \; \ldots \; ] \\
\label{eq:cdta0:spsi0:04}
\overline{\rho_1}(1) & = & [ \; 0 \; 5 \; 0 \; 0 \; 5 \; 0 \; 0 \; 5 \; 0 \; 0 \; 5 \; \ldots \; ] \\
\nonumber
\overline{\rho_1}(2) & = & [ \; 5 \; 0 \; 0 \; 5 \; 0 \; 0 \; 5 \; 0 \; 0 \; 5 \; 0 \; \ldots \; ] \\
\nonumber
\overline{\rho_1}(3) & = & [ \; 0 \; 0 \; 5 \; 0 \; 0 \; 5 \; 0 \; 0 \; 5 \; 0 \; 0 \; \ldots \; ]
\end{eqnarray}

We define the \emph{cost calculation matrix} as the matrix formed by vertically
concatenating, in order, the first $LCM(T_1, \ldots , T_N)$ 
columns of either the uncosted invocation sequence
$\rho_i(z_i)$ or the costed invocation sequence $\overline{\rho_i}(z_i)$
of every process in the system; and then appending to this as a row vector
the sums of 
each column.  We choose only the first $LCM(T_1, \ldots , T_N)$ columns
because the contents of these columns repeat in subsequent columns forever.
We denote the cost calculation matrix as $\xi(\mathbf{z})$ (in the case
of the uncosted invocation sequences) or as $\overline{\xi}(\mathbf{z})$
(in the case of the costed invocation sequences); where $\mathbf{z}$ is the
column vector consisting of all of the staggers $z_i$.  Finally, we define the 
\emph{cost}, denoted $\xi$, as the maximum element from the last row of the 
cost calculation matrix (it is $\xi$ that we seek to minimize by choosing
$\mathbf{z}$).  These definitions are illustrated in the following example.

\begin{vworkexamplestatement}
\label{ex:cdta0:spsi0:01}
For the system of 3 processes ($P_1$, $P_2$, and $P_3$) with 
$T_1=6$, $T_2=4$, $T_3=3$, $\tau_1=2$, $\tau_2=7$, $\tau_3=5$,
$z_1 = 2$, $z_2 = 1$, and $z_3 = 0$,
form the uncosted and costed invocation sequences, the cost
calculation matrices, and the costs.
\end{vworkexamplestatement}
\begin{vworkexampleparsection}{Solution}
We first handle the uncosted case in full, followed by the costed
case in full.

\textbf{(Uncosted Case):}
With $T_1=6$ and $z_1=2$, the first invocation of $P_1$ will occur
when $(t + 2) \bmod 6 = 0$ (see Eq. \ref{eq:cdta0:spsi0:02}), at $t=4$,
and then repeat with periodicity 6.  Thus

\begin{equation}
\label{eq:ex:cdta0:spsi0:01:01}
\rho_1(2)  =  [ \; 0 \; 0 \; 0 \; 1 \; 0 \; 0 \; 0 \; 0 \; 0 \; 1 \; 
 0 \; 0 \; 0 \; 0 \; 0 \; 1 \; 0 \; \ldots \; ] .
\end{equation}

\noindent{}Applying the same definition for $P_2$ and $P_3$ yields

\begin{equation}
\label{eq:ex:cdta0:spsi0:01:02}
\rho_2(1)  =  [ \; 0 \; 0 \; 1 \; 0 \; 0 \; 0 \; 1 \; 0 \; 0 \; 0 \; 
 1 \; 0 \; 0 \; 0 \; 1 \; 0 \; 0 \; \ldots \; ] 
\end{equation}

\noindent{}and

\begin{equation}
\label{eq:ex:cdta0:spsi0:01:03}
\rho_3(0) = \rho_3 =  [ \; 0 \; 0 \; 1 \; 0 \; 0 \; 1 \; 0 \; 0 \; 1 \; 0 \; 
 0 \; 1 \; 0 \; 0 \; 1 \; 0 \; 0 \; \ldots \; ] .
\end{equation}

We note that the column vector $\mathbf{z}$ is

\begin{equation}
\label{eq:ex:cdta0:spsi0:01:04}
\mathbf{z}
=
\left[\begin{array}{c}z_1\\z_2\\z_3\end{array}\right]
=
\left[\begin{array}{c}2\\1\\0\end{array}\right] .
\end{equation}

$LCM(T_1, T_2, T_3) = LCM(6, 4, 3) = 12$, and so the cost calculation matrix
can be constructed with only 12 columns, since the columns repeat with periodicity
12:

\begin{equation}
\label{eq:ex:cdta0:spsi0:01:05}
\xi(\mathbf{z})
= 
\xi\left(\left[\begin{array}{c}2\\1\\0\end{array}\right]\right)
=
\left[
\begin{array}{rrrrrrrrrrrr}
0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\
0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 \\
0 & 0 & 2 & 1 & 0 & 1 & 1 & 0 & 1 & 1 & 1 & 1
\end{array}
\right]
.
\end{equation}

Note in (\ref{eq:ex:cdta0:spsi0:01:05}) that the last row is
the column-wise sum of the rows above it.  Note also that
the last row gives, on a per tick basis, the number of processes
that run.

The cost $\xi$ is the maximum of the last row of (\ref{eq:ex:cdta0:spsi0:01:05}),
and by inspection $\xi = 2$.

\textbf{(Costed Case):}
The costed invocation sequences are simply 
(\ref{eq:ex:cdta0:spsi0:01:01}), (\ref{eq:ex:cdta0:spsi0:01:02}), and
(\ref{eq:ex:cdta0:spsi0:01:02}) with 1's replaced by the cost appropriate
to the process being considered;  $\tau_1$, $\tau_2$, or $\tau_3$:

\begin{eqnarray}
\nonumber
\overline{\rho_1}(2)  & = &  [ \; 0 \; 0 \; 0 \; 2 \; 0 \; 0 \; 0 \; 0 \; 0 \; 2 \; 
 0 \; 0 \; 0 \; 0 \; 0 \; 2 \; 0 \; \ldots \; ] \\
\label{eq:ex:cdta0:spsi0:01:06}
\overline{\rho_2}(1)  & = & [ \; 0 \; 0 \; 7 \; 0 \; 0 \; 0 \; 7 \; 0 \; 0 \; 0 \; 
 7 \; 0 \; 0 \; 0 \; 7 \; 0 \; 0 \; \ldots \; ]  \\
\nonumber
\overline{\rho_3}(0) = \overline{\rho_3} & = &  [ \; 0 \; 0 \; 5 \; 0 \; 0 \; 5 \; 0 \; 0 \; 5 \; 0 \; 
 0 \; 5 \; 0 \; 0 \; 5 \; 0 \; 0 \; \ldots \; ] 
\end{eqnarray}

The cost calculation matrix in the costed case is formed by vertically concatenating the
first 12 columns of the rows of (\ref{eq:ex:cdta0:spsi0:01:06}), with the 
final row containing columnwise sums:

\begin{equation}
\label{eq:ex:cdta0:spsi0:01:07}
\overline{\xi}(\mathbf{z})
= 
\overline{\xi}\left(\left[\begin{array}{c}2\\1\\0\end{array}\right]\right)
=
\left[
\begin{array}{rrrrrrrrrrrr}
 0 &  0 &  0 &  2 &  0 &  0 &  0 &  0 &  0 &  2 &  0 &  0 \\
 0 &  0 &  7 &  0 &  0 &  0 &  7 &  0 &  0 &  0 &  7 &  0 \\
 0 &  0 &  5 &  0 &  0 &  5 &  0 &  0 &  5 &  0 &  0 &  5 \\
 0 &  0 & 12 &  2 &  0 &  5 &  7 &  0 &  5 &  2 &  7 &  5
\end{array}
\right]
.
\end{equation}

The cost $\overline{\xi}$ is the maximum of the last row of (\ref{eq:ex:cdta0:spsi0:01:07}),
and by inspection $\overline{\xi} = 12$.
\end{vworkexampleparsection}
\vworkexamplefooter{}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Sine And Cosine}
%Section tag: sco0
\label{cdta0:ssco0}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Rotational Transformations In 2 Dimensions}
%Section tag: RTR2
\label{cdta0:srtr2}

\index{rotation!2-D}It occurs often in microcontroller work that one needs to rotate
coordinates in 2 dimensions (Figure \ref{fig:cdta0:srtr2:01}).  In this section,
the most economical algorithms known for 2-dimensional
rotation are discussed.  We assume that the
point $\mathbf{p}$ to be rotated is specified in rectangular coordinates
$\mathbf{p} = (p_x, p_y)$ rather than polar coordinates 
$\mathbf{p} = (r, \theta)$; since if $\mathbf{p}$ is specified in polar coordinates
rotation involves only addition to $\theta$ modulo $2\pi$.  We denote the point to be
rotated $\mathbf{p} = (p_x, p_y) = \left[\begin{array}{c}p_x\\p_y\end{array}\right]$ 
and the result of the rotation 
$\mathbf{q} = (q_x, q_y) = \left[\begin{array}{c}q_x\\q_y\end{array}\right]$.
We denote the length of the vector represented by $\mathbf{p}$ or $\mathbf{q}$
by $r$, and note that 
$r = |\mathbf{p}| = \sqrt{p_x^2 + p_y^2} = |\mathbf{q}| = \sqrt{q_x^2 + q_y^2}$.
Because low-cost microcontrollers are used, we assume that
$p_x, p_y, q_x, q_y \in \vworkintset$.
We denote the desired amount of counter-clockwise rotation by $\delta$ (in radians).

\begin{figure}
\begin{huge}
\begin{center}
Reserved
\end{center}
\end{huge}
\caption{Rotation In 2 Dimensions}
\label{fig:cdta0:srtr2:01}
\end{figure}

A particularly na\"{\i}ve algorithm to use in microcontroller work is to 
convert $\mathbf{p} = (p_x, p_y)$ to polar coordinates
$\mathbf{p} = (r, \theta)$, rotate to obtain 
$\mathbf{q} = (r, (\theta + \delta) \bmod 2\pi)$, and then convert back to 
rectangular coordinates $\mathbf{q} = (q_x, q_y)$.  
This algorithm is na\"{\i}ve because trigonometric and
inverse trigonometric functions are required, which are not economical to implement 
on microcontrollers.  We seek if possible algorithms which operate exclusively in
rectangular coordinates and which require little or no evaluation of
trigonometric and inverse trigonometric functions.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Matrix Rotation In 2 Dimensions}
%Section tag: MRT0
\label{cdta0:srtr2:smrt2}

Assume we wish to rotate the vector

\begin{equation}
\label{eq:cdta0:srtr2:smrt2:01}
\mathbf{p} 
= (p_x, p_y) 
= \left[\begin{array}{c}p_x\\p_y\end{array}\right]
= (r \cos \theta, r \sin \theta) 
= \left[\begin{array}{c}r \cos \theta\\r \sin \theta\end{array}\right]
\end{equation}

\noindent{}by an angle of $\delta$ to give the vector

\begin{eqnarray}
\label{eq:cdta0:srtr2:smrt2:02}
\mathbf{q} & = & (q_x, q_y) = \left[\begin{array}{c}q_x\\q_y\end{array}\right] \\
\nonumber & = & (r \cos (\theta + \delta), r \sin (\theta + \delta)) 
= \left[\begin{array}{c}r \cos (\theta + \delta)\\r \sin (\theta+\delta)\end{array}\right].
\end{eqnarray}

\noindent{}Recall from standard trigonometry identities that for sines and cosines of 
sums of angles that

\begin{eqnarray}
\label{eq:cdta0:srtr2:smrt2:03}
\left[\begin{array}{c}r \cos (\theta + \delta)\\r \sin (\theta+\delta)\end{array}\right]
& = &
\left[\begin{array}{c}r \cos \theta \cos \delta - r \sin \theta \sin \delta \\
                      r \sin \theta \cos \delta + r \cos \theta \sin \delta \end{array}\right] \\
\label{eq:cdta0:srtr2:smrt2:04}
& = & 
\left[\begin{array}{c}p_x \cos \delta - p_y \sin \delta \\
                      p_x \sin \delta + p_y \cos \delta \end{array}\right] \\
\label{eq:cdta0:srtr2:smrt2:05}
& = & 
\left[\begin{array}{c}q_x\\q_y\end{array}\right]
=
\left[\begin{array}{cc}\cos \delta & - \sin \delta \\
                       \sin \delta & \;\;\;\cos \delta \end{array}\right]
\left[\begin{array}{c}p_x\\p_y\end{array}\right] .
\end{eqnarray}

\noindent{}Note that (\ref{eq:cdta0:srtr2:smrt2:05})
reduces the rotation problem to four multiplications and two additions
(the matrix multiplication), provided that some approximation of the sine
and cosine functions is available (see Section \ref{cdta0:ssco0}).  

To apply (\ref{eq:cdta0:srtr2:smrt2:05}), the embedded software
may or may not need to approximate the sine and cosine functions.
For some applications, if the angle of rotation is fixed, 
$\sin \delta$ and
$\cos \delta$ may be calculated at compile time and tabulated in 
ROM rather than $\delta$ (so that the embedded software does not need
to approximate these functions).  For other applications,
sine and cosine must be approximated (see Section \ref{cdta0:ssco0}).

The 2 $\times$ 2 matrix in (\ref{eq:cdta0:srtr2:smrt2:05})
is called the \index{rotation matrix}\emph{rotation matrix}.  There are
other functionally equivalent ways to derive this result, including complex
arithmetic (i.e. phasor analysis) and graphical geometric arguments.

As pointed out in Section \ref{cdta0:ssco0}, the best way to approximate
sine and cosine in low cost microcontrollers is usually by tabulation of the 
values of $\sin \delta$ for $\delta \in [0, \pi/2]$.  Using the 
techniques presented in Section \ref{cdta0:ssco0} for approximation of
sine and cosine and using (\ref{eq:cdta0:srtr2:smrt2:05}), rotation can usually
be carried out using around 20 machine instructions.

If a vector is rotated repeatedly using (\ref{eq:cdta0:srtr2:smrt2:05}), cumulative
truncation and rounding errors may eventually yield a vector 
$\mathbf{q}$ with a significantly different
magnitude $|\mathbf{q}| = \sqrt{q_x^2 + q_y^2}$ than the starting vector.
It should be possible to develop an algorithm similar in spirit to the 
Bresenham circle algorithm (see Section \ref{cdta0:srtr2:sbrt2}) to
adjust the magnitude of a vector to correct for cumulative 
errors while leaving its direction as nearly unchanged
as possible (see Exercise \ref{exe:cdta0:sexe0:01}).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Bresenham Rotation In 2 Dimensions}
%Section tag: BRT0
\label{cdta0:srtr2:sbrt2}

Depending on the application \ldots{}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Rotational Transformations In 3 Dimensions}
%Section tag: RTR3
\label{cdta0:srtr3}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Acknowledgements}
%Section tag: ACK0
\label{cdta0:sack0}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Exercises}
%Section tag: sexe0
\label{cdta0:sexe0}

\begin{vworkexercisestatement}
\label{exe:cdta0:sexe0:01}
Develop an algorithm similar in spirit to the Bresenham circle
algorithm to adjust a vector $\mathbf{q} = (q_x, q_y)$ with 
cumulative magnitude errors due to repeated rotations to 
a vector $\mathbf{z} = (z_x, z_y)$ which points as nearly as
possible in the same direction as $\mathbf{q}$ but with 
a desired magnitude $r$.
\end{vworkexercisestatement}
\vworkexercisefooter{}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\vfill
\noindent\begin{figure}[!b]
\noindent\rule[-0.25in]{\textwidth}{1pt}
\begin{tiny}
\begin{verbatim}
$RCSfile: c_dta0.tex,v $
$Source: /home/dashley/cvsrep/e3ft_gpl01/e3ft_gpl01/dtaipubs/esrgubka/c_dta0/c_dta0.tex,v $
$Revision: 1.5 $
$Author: dtashley $
$Date: 2003/03/03 23:50:43 $
\end{verbatim}
\end{tiny}
\noindent\rule[0.25in]{\textwidth}{1pt}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% $Log: c_dta0.tex,v $
% Revision 1.5  2003/03/03 23:50:43  dtashley
% Substantial edits.  Safety checkin.
%
% Revision 1.4  2003/02/27 05:00:06  dtashley
% Substantial work towards rotation algorithm section.
%
% Revision 1.3  2003/01/15 06:23:13  dtashley
% Safety checkin, substantial edits.
%
% Revision 1.2  2003/01/14 05:39:59  dtashley
% Evening safety checkin after substantial edits.
%
% Revision 1.1  2001/08/25 22:51:25  dtashley
% Complex re-organization of book.
%
%End of file C_PCO0.TEX