<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[onecolumn,letterpaper,11pt]{article}

%===================================================================
% Include common packages, environments, counters etc
\input{../common_latex_packages}
\input{../common_latex_lab_format}
\input{../common_latex_definitions}
%===================================================================
\setcounter{tocdepth}{2}
%===================================================================

\begin{document}
\wikidoc{file=Lab.ClassPrimeFactors}
\wikidoc{auth=mikerb@mit.edu}
\helplevelsubsec

%===================================================================
% Build the Cover Page in an environment style easy for wiki parsing
\begin{labcover}
\labtitle{Lab 5 Pre Lab - MOOS Programming - Calculating Prime Factors}
\vspace{0.1in}
\labcourse{2.680 Unmanned Marine Vehicle Autonomy, Sensing and Communications}
\vspace{0.15in}
\labpng{0.42}{figures/arturo_rnd.png}
\vspace{0.15in}
\labdate{Mar 2nd, 2021}
\vspace{0.1in}
\labauth{Michael Benjamin, mikerb@mit.edu}
\labauth{Henrik Schmidt, henrik@mit.edu}
\labauth{Department of Mechanical Engineering}
\labauth{MIT, Cambridge MA 02139}
\labtoc{footnotesize}
\end{labcover}

%===================================================================
% Add a blank page so first body page is on the right when doubleside
\blankpage

%===================================================================
% Begin the body of the text
%===================================================================
\section{Overview}
%===================================================================
In Lab 5 we will build our next MOOS application. The function
performed by the app is a bit harder: it handles a series of integers
and determines, for each, the list of prime factors.

\vspace{0.1in}
\noindent
An example input: (via incoming mail)

\prevgreen[0in]
\begin{verbatim}
   NUM_VALUE = "90090"
\end{verbatim}
\postverb

\noindent
An example output: (via posted mail)

\prevgreen[0in]
\begin{verbatim}
  PRIME_RESULT = "orig=90090,primes=2:3:3:5:7:11:13"
\end{verbatim}
\postverb

\noindent
A primary issue addressed in this exercise is how to build an app that
performs an operation that may be considerably longer than the time
allotted to a typical \var{Iterate()} loop. We ask you to write
and test your app to run at 4Hz.  Test input will be generated by another
app at 4Hz or higher. But some test numbers will contain very large
prime factors and may not be answerable in the quarter second time window
of the \var{Iterate()} loop. The goal is to construct your app to continue
to handle the smaller numbers at the 4Hz rate, while also handling the
larger numbers, incrementally working toward their solution on each loop.

%===================================================================
\subsection{Getting Started}

Begin by repeating the same steps from the previous example:

\begin{packed_enumerate}[3]
\item Enter the \var{moos-ivp-extend/src} directory and run the
  \app{GenMOOSApp\_AppCasting} script to build the bare-bones application:
  
\begin{consoleverb}
 $ GenMOOSApp_AppCastng PrimeFactor p "John Doe"
\end{consoleverb}
\postverb[0in]

\item Let's all use the app name \app{pPrimeFactor}. It makes testing
  much easier for the TAs.

\item Add your new app to the build system as before by editing the
  \var{CMakeLists.txt} and test that it builds.
\end{packed_enumerate}

\vspace{0.1in}
\noindent
At the end of the previous lab, we recommended a few additional steps:

\begin{packed_itemize}
\item Initially augment your brand new \app{pPrimeFactor} app to read
  in mail, \mvar{NUM\_VALUE}, and determine if it is even or odd, and
  post new mail accordingly. Testing was done via \app{uPokedDB}.
  
\item Use \app{uTimerScript} to test the above with a set of values
  from the script instead of \app{uPokeDB}.

\item Handle the even/odd determination inside the \var{Iterate()} loop.
  Build a C++ list of incoming numbers in \var{OnNewMail()} and
  handle this list inside \var{Iterate()}.

\end{packed_itemize}

\vspace{0.05in}
\noindent
If you haven't done this "pre-lab" work, it's still a good idea to go
back and do this. But technically it's not required if you want just
jump into the task of prime factorization below. 


%===================================================================
\subsection{The Specs of Your pPrimeFactor Application}
\label{sec_specs}

Your application should meet the following specifications:

\begin{packed_enumerate}[2]

\item Your app should be called \app{pPrimeFactor}.

\item Your app should register for and handle the variable
  \mvar{NUM\_VALUE}. Your app should accept mail on this variable
  containing a 64-bit integer value. The maximum value will be $2^{64}-1$,
  or 18,446,744,073,709,551,615, the maximum for a 64 bit unsigned
  integer. You can assume only positive integers as input.

\item The incoming variable is of type {\em string}. You must convert
  it to a numerical value in your code.

\item Your app should determine the list of prime factors for a given
  input, and generate the following output for each:

\begin{packed_itemize}[2]
  \item the original number, 
  \item an index indicating the order in which it was received,
  \item an index indicating the order in which it was calculated,
  \item the time it took to solve the factorization. This is in normal
    clock time, not CPU time. Use the \cmd{MOOSTime()} function to get
    the time when it was received and the time it was finished.
  \item the list of prime factors.
  \item a unique id specifying you, e.g., your Athena username.
\end{packed_itemize}

\item Your output variable should be \mvar{PRIME\_RESULT} with the
  below format. Note if a number can be evenly divided by a prime
  factor more than once, like the example below with two 3's, list
  each in the result:

\prevgreen[0in]
\begin{verbatim}
PRIME_RESULT = "orig=90090,received=34,calculated=33,solve_time=2.03,
                  primes=2:3:3:5:7:11:13,username=jane"
\end{verbatim}
\postverb

\item Your application should not be blocked by large numbers. We should
  be able to see a response to low-number queries almost immediately, regardless
  of the size of the preceding query.

\item Do not use a cache of known prime numbers. 

\end{packed_enumerate}

%===================================================================
\subsection{Key Aspects of this Lab}

The key issue in this exercise is to design your \app{pPrimeFactor}
app to handle any size number, but not "block" on difficult numbers,
e.g., large primes. Certain small numbers, and numbers with a short
list of small primes, lend themselves to very quick calculation of
their sets of prime factors. Other numbers, such as any 20 digit prime
number, require many more steps before determining their result. Your
app will be rapidly receiving incoming mail, receiving numbers both
hard and easy.

\vspace{0.1in}
\noindent
The objective is to design your app to quickly handle and post the
results for the easy numbers, and not delay the results for easy
numbers when a harder number is received. You will need to establish
a work queue (in the form of a C++ list) to hold newly arrived and
unsolved numbers. You will need to populate this queue in your
\var{OnNewMail()} function. And you will need to "work" on this queue
inside your \var{Iterate()} method.

\vspace{0.1in}
\noindent
The key idea is that each time \var{Iterate()} is invoked, a fixed
amount of prime factorization calculations will be applied to each
item in the queue. For some elements, this will be enough to complete
the calculation. They can be removed from the queue, and have their
answer posted in the form of outgoing mail to the MOOSDB. For elements
that cannot be finished in the current round, they will remain in the
queue to be continued in the next call of \var{Iterate()}. The trick
will be to save the "state" for any unfinished work.

\vspace{0.1in}
\noindent
In the end we will check for a properly working \app{pPrimeFactor} app
by using our a \app{uTimerScript} sequence of numbers, with easy and
hard numbers mixed. We'll check for correct calculation of the factors,
and check that the hard numbers didn't block the easy numbers.


%======================================================================
\newpage
\section{Further C++ Notes for this Lab}
%======================================================================

%===================================================================
\subsection{Unsigned Long Integers}

Your \app{pPrimeFactor} application needs to accept and handle non-negative
integers up to the maximum value for a 64 bit integer, up to $2^{64}-1$.
Traditionally this is accomplished by using the following C++ data
type:

\vspace{0.1in}
\begin{fileverb}
  unsigned long int value = 184467440739429084;
\end{fileverb}

\vspace{0.1in}
\noindent
However, in some older C++ compilers, the \var{"unsigned long int"}
data type was only 32 bits. In most newer compilers they are 64
bits. To be sure, the following data type has become more common, and
in newer compilers the older style will produce a warning. We will use
the newer style in this lab:

\vspace{0.1in}
\begin{fileverb}
  #include &lt;cstdint&gt;

  uint64_t value = 184467440739429084;
\end{fileverb}

\vspace{0.1in}
\noindent
Note that you need to include the \var{cstdint} library.


%===================================================================
\subsection{Why Our MOOS Input is Generated as a String Value}
\label{sec_double_trouble}

MOOS messages are either of type \var{string} or \var{double}. The
\var{string} type allows virtually any other complex data type to
be represented, so essentially the possible types of messages are
limitless. The \var{double} type is convenient but has limitations
in precision discussed here.

\vspace{0.1in}
\noindent
The \var{double} type in C++ is 8 bytes, or 64 bits long.  The type
\var{uint64\_t} is also 64 bits. They are both capable of representing
$2^{64}$ or \var{18,446,744,073,709,551,615} distinct numbers. The
difference is that with \var{uint64\_t} variables, there is an
understanding that only the integer numbers in the range \var{[0,
    18446744073709551615]} will be represented. With \var{double}
variables, all the negatives numbers, all the floating point
non-integer values, e.g. $23.87432$, and numbers higher than
18,446,744,073,709,551,615 are stuffed into the same 64 bits. This
inevitably means that some numbers are not representable, and instead
are mapped to a nearby "close" number. This is the case with some
large integer values beginning with numbers greater than about 15
digits.

\vspace{0.1in}
\noindent
As an experiment, you can try the sample code in a simple \var{main.cpp}
file. Note both variables are assigned the same literal value, but the
\var{double} variable is rounded to a nearby number.


\vspace{0.1in}
\begin{fileverb}
  uint64_t value1 = 184467440739429084;
  double   value2 = 184467440739429084;

  cout &lt;&lt; "value 1: " &lt;&lt; value1 &lt;&lt; endl;
  cout &lt;&lt; "value 2: " &lt;&lt; fixed &lt;&lt; value2 &lt;&lt; endl;
\end{fileverb}

\begin{consoleverb}
  value 1: 184467440739429084
  value 2: 184467440739429088;
\end{consoleverb}

\vspace{0.1in}
\noindent
The implications of this mean that if we want to precisely pass large
numbers through MOOS messages, we should use the string representation
of the number instead. So in our case if we want to post a large 18-20
digit prime number, we need to use strings.



%===================================================================
\subsection{String to Number, and Number to String Conversion}

In this lab you will need to perform some conversions between strings and
numerical values. To represent a 64 bit integer you will want to use the 
type \var{uint64\_t}. 

\vspace{0.1in}
\begin{fileverb}
 #include &lt;cstdint&gt;
 uint64_t  value = 0;
\end{fileverb}
\vspace{0.1in}

\noindent
In this lab, if you use the \app{uTimerScript} script provided in the
lab, the numbers will be posted to the variable \mvar{NUM\_VALUE} as a
string value. For example, if the posting were:

\vspace{0.1in}
 \mvar{NUM\_VALUE="5674032334252535"}. 
\vspace{0.1in}

\noindent
At some point, in the MOOS App you will write for this lab, to convert
from the string, \var{str="5674032334252535"} to a \var{int64\_t},
use:

\vspace{0.1in}
\begin{fileverb}
#include &lt;cstdlib&gt;   // for the strtoul() function

string str = "5674032334252535"
uint64_t value = strtoul(str.c_str(), NULL, 0);
\end{fileverb}
\vspace{0.1in}


\noindent
In the other direction, converting numerical values into strings, you
can use the C++ \var{stringstream} class for this:

\vspace{0.1in}
\begin{fileverb}
// Include the stringstream header file
#include &lt;sstream&gt;
....

// Create the biggest unsigned long int possibe
uint64_t ival = 18446744073709551615;

// Convert it to a string
stringstream ss;
ss &lt;&lt; ival;
string str = ss.str();

// Confirm it works
cout &lt;&lt; "Value:" &lt;&lt; str &lt;&lt; endl;
\end{fileverb}


%===================================================================
\subsection{Super Handy Utilities for String Parsing}

In this lab you will be generating posted results in the form of a
string with comma-separated variable=value pairs, such as the
following.

\prevgreen[0in]
\begin{verbatim}
PRIME_RESULT = "orig=90090,received=34,calculated=33,solve_time=2.03,
                  primes=2:3:3:5:7:11:13,username=jane"
\end{verbatim}
\postverb

\vspace{0.1in}
\noindent
At many various points in later labs, you will also want to parse these
kinds of strings into their various components. You may even want to do
so in this lab if you choose to write a testing mechanism to check your
own answers. Fortunately there are a few tools in the MOOS-IvP library
\var{mbutil} for making this an easy task. These tools are listed below
with links to a more full discussion of each.

\begin{packed_itemize}[2]
\item \var{vector&lt;string&gt; parseString(string, char);} 
\item \var{string         biteString(string, char);}
\item \var{string         stripBlankEnds(string);}
\end{packed_itemize}

\noindent
They can be found here:
\urlx{http://oceanai.mit.edu/ivpman/help/string_parse_utils}.

\vspace{0.1in}
\noindent
You will also find useful a few utilities for quickly converting numerical
or Boolean values to strings:

\begin{packed_itemize}[2]
\item \var{string   intToString(string);} 
\item \var{string   uintToString(string);} 
\item \var{string   ulintToString(string);} 
\item \var{string   doubleToString(double, int precision);}
\item \var{string   boolToString(bool);}
\end{packed_itemize}

\noindent
They can be found here:
\urlx{http://oceanai.mit.edu/ivpman/help/string_utils}.




%======================================================================
\newpage
\section{Suggestions for Development Progression of this Lab}
%======================================================================

An effective strategy for building complex code is the identification
of relatively easier distinct stages where each stage is (a)
verifiable, (b) closer to the overall solution, and (c) doesn't
require much re-working between each stage. With that in mind,
we offer the following distinct stages progressing on this lab:

%===================================================================
\subsection{Create the New App, Augment Your Build Tree}

The first steps in the Prime Factors lab will be the same as this lab.

\begin{packed_itemize}
\item Generate a new app template using \app{GenMOOSApp}, as described
  in the previous lab for \app{pOdometry}. Be sure to call this new
  app \app{pPrimeFactor}.
\item Add your \app{pPrimeFactor} app to the build tree, as described
  in the previous lab for \app{pOdometry}.
\item Verify that it builds and is in your shell path.
\item Since most of us are still new to version contol, this would be
  a great time for some simple practice. Add your new \app{pPrimeFactor}
  folder to your tree and commit it (check it in). Learning your version
  control tools is best done by using it regularly.
\end{packed_itemize}

%===================================================================
\subsection{Augment Your App to Accept and Process Numerical Entries}

A good first step is to begin to edit your \app{pPrimeFactor} MOOS app
to accept numerical input. Augment your \var{OnNewMail()} function to
handle this input. As a first step, you can simply determine if the
number is odd or even, and immediately post the result. For now you
can do this all in \var{OnNewMail()}, leaving your \var{Iterate()}
method empty. The result should be posted as a string, with the
original number, and the "odd/even" evaluation. For example:

\vspace{0.1in}
\noindent
\var{NUM\_RESULT = "37,odd"}

\vspace{0.1in}
\noindent
To test this, launch your new app in a simple mission
(\var{primes.moos}) file, of your own making. This will just launch a
\app{MOOSDB} and your \app{pPrimeFactor} app. In two seperate terminal
windows, launch a \app{uXMS} scope, and use the second window for
poking the \app{MOOSDB}

\vspace{0.1in}
\begin{consoleverb}
$ uXMS myfile.moos NUM_VALUE NUM_RESULT
\end{consoleverb}
\vspace{0.1in}

\noindent
Then in the other window:

\vspace{0.1in}
\begin{consoleverb}
$ uPokeDB myfile.moos NUM_VALUE:=37
$ uPokeDB myfile.moos NUM_VALUE:=22
\end{consoleverb}
\vspace{0.1in}

\noindent
Verify it's all working in your scope window. Note in the above that we
are posting \mvar{NUM\_VALUE} as a string with the \var{:=} operator.
We do this here simply because we will need to do things this way when
handling large primes for the reasons discussed in Section
\ref{sec_double_trouble}.

%===================================================================
\subsection{Augment Your Testing to use uTimerScript}

In this next step, use \app{uTimerScript} to test your
\app{pPrimeFactor} app rather than manually poking the MOOSDB with
\app{uPokeDB}. You will need to add a \app{uTimerScript} configuration
block to your \var{primes.moos} mission file.

\vspace{0.1in}
\noindent
The \app{uTimerScript} app was introduced in Lab 3, and the full
documentation is online. The goal here is to repeatedly post the same
few numbers. By setting it to repeat, it can just be active upon the
mission launch. The following script or similar should suffice.

\vspace{0.1in}
\begin{fileverb}
 ProcessConfig = uTimerScript  
 {
   event = var=NUM_VALUE, val=53,  time = 0.50
   event = var=NUM_VALUE, val=234, time = 1.00
   event = var=NUM_VALUE, val=117, time = 1.50
   reset_max  = nolimit
   reset_time = all-posted
 }
\end{fileverb}
\vspace{0.1in}

\vspace{0.1in}
\noindent
As before, verify with \app{uXMS} open in another terminal to verify that
your app is working properly on these auto-generated values.

%===================================================================
\subsection{Handling your Work Inside the Iterate Method}

The next step in developing your \app{pPrimeFactor} app is to handle
your mail by creating a C++ list of numbers. In your \var{OnNewMail()}
function, don't do any work determining the even or odd nature of your
incoming numbers. And don't post mail from within your
\var{OnNewMail()} method.  In the mail loop, just build a C++ list of
received mail. You may need to read up a bit on C++ STL lists, but see
the refresher on lists at the end of the previous lab.  An STL list is
a doubly linked list, meaning you can access from the beginning, or
the end of the list.  For now, in your mail function, push new numbers
onto the beginning of the list.

\vspace{0.1in}
\noindent
Since this list will need to be accessed by \var{OnNewMail()} and your
\var{Iterate()} loop, it should be a member variable of your
\var{PrimeFactor} class definition. Declare it in your app's header
file.

\vspace{0.1in}
\noindent
In your \var{Iterate()} loop, access the list by repeatedly popping a
value off the end of the list, determine if it is even or odd, and post
as before. At the end of each \var{Iterate()} loop, the list should be
empty.


%===================================================================
\subsection{Write a Stand-Alone C++ Test Program for Calculating Primes}

Step aside from MOOS issues for a moment and focus on the issue of
calculating prime factors. For this step you can create and build the
program along the style of the mini C++ labs, compiling with \cmd{g++}
on the command line. Or you can generate a throw-away MOOS app in the
\var{moos-ivp-extend} structure that just has a \var{main.cpp}
file. Further hints for calculating prime factors is provided below in
Section \ref{sec_primes}. In this step, your test program can just
take a single command line argument, with simple output:

\vspace{0.1in}
\begin{consoleverb}
$ mytest 90090
primes=2:3:3:5:7:11:13
\end{consoleverb}
\vspace{0.1in}


%===================================================================
\subsection{Calculate Primes Instead of Even/Odd}

With the results of the previous two steps, you should now be comfortable
with both:

\begin{packed_itemize}
\item Having an app that reads numerical input (as strings) and populates
  a work queue (an STL list), which is then acted on inside the app's
  \var{Iterate()} loop.

\item Calculating the prime factors of a given number.
\end{packed_itemize}
\vspace{0.1in}

\noindent
In this next step, rather than calculate whether a number is even
or odd, calculate the prime factors instead. In your \var{Iterate()} loop,
step through the list of input values, and determine the primes and
post a string answer according to the specs given in Section
\ref{sec_specs}.

\vspace{0.1in}
\noindent
At this point, you're mostly done, but still missing a very important
design spec of this app. By stepping through the list of numbers, and
calculating the prime factors completely, before going on to the next
item in the list, large primes will block easier numbers. The remaining
stage of the lab, addressing this issue, is described next.

%===================================================================
\subsection{Modify Your App to be Non-Blocking}

In the final stage, as before, work is added to a list in
\var{OnNewMail()}, and processed from the list in \var{Iterate()}.
The key difference is that rather than working to completion on each
element of the list, a finite amound of work is done on each
element. Work, in this case, amounts to a fixed number of modulo
arithmetic operations. (By the way 100,000 is a good number to
start with for a block of modulo arithmetic operations. But experiment
yourself.)

\vspace{0.1in}
\noindent
During each visit to an element in the list, if all the primes are
found within this fixed number of steps, it is removed from the list,
and its answer is posted in outgoing mail. Otherwise it is left on the
list until the next time the \var{Iterate()} method is invoked. But
presumably new numbers may be added in the meanwhile as the
\var{OnNewMail()} function is once again invoked.

\vspace{0.1in}
\noindent
The key addition of this stage of development is that the elements of
a list need some way of saving partial work. Rather than maintiaing a
list of 64-bit integers, it will be convenient to maintain a list of
something else. That something else needs to be something that can not
only store the original integer, but also the list of primes found so
far, and some indication where the previous work left off.

\vspace{0.1in}
\noindent
A class for representing the above is discussed in Section \ref{sec_pclass}


%======================================================================
\newpage
\section{Technical Suggestions}
%======================================================================

%======================================================================
\subsection{Calculating the Set of Prime Factors for a Given Number}
\label{sec_primes}

You can find several descriptions on the web of the algorithm for
calculating the prime factors of a given number. We describe it in our
own words here, partly because we want to emphasize the notion of {\em
  partially} calculating the answer. Initially this isn't our focus,
but later on it will be important - we will want an algorithm that we
can pause and resume where we left off.

\pskip
\noindent
First, let's discuss the notion of the problem {\em state}. The state
consists of two parts:

\begin{packed_itemize}
\item A list {\bf L} of prime factors, initially empty,
\item A number {\bf N} with a perhaps presently unknown set of prime factors.
\end{packed_itemize}

\noindent
As the algorithm progresses, the state will evolve with the list {\bf L} 
growing and the number {\bf N} shrinking until {\bf L} holds the list
of prime factors, and {\bf N} is $1$. For example:

\vspace{0.1in}
\begin{fileverb}
  L = {}, N=2310          &lt;- Initial condition with input 2310
  L = {2}, N=1155
  L = {2,3}, N=385
  L = {2,3,5}, N=77
  L = {2,3,5,7}, N=11
  L = {2,3,5,7,11}, N=1   &lt;- Final condition, solution {2,3,5,7,11}
\end{fileverb}
\vspace{0.1in}

\noindent
How do you find the next prime factor at each stage? One simple way to
do this is to iterate between $i=2$ and the square root of {\bf N} and
checking if $i$ divides evenly into {\bf N}. Checking if a number
divides evenly into another number, in C++, is done with the modulo
operator \var{'\%'}

\vspace{0.1in}
\begin{fileverb}
  (a % b == 0)  // if b divides evenly into a 
\end{fileverb}
\vspace{0.1in}

\noindent
Confirm for yourself why going beyond the square root is redundant.


\pskip
\noindent
You may notice that the simple for-loop has some inefficiencies in
it. For example, checking if \var{(N\%4)==0} is not necessary if we
already know \var{(N\%2)!=0}. In fact that for-loop should only
include prime numbers \var{i=2,3,5,7,11,13...} rather than
\var{i=2,3,4,5,6,7...}. Here it may become tempting to keep a look-up
table of "small" primes to make your for-loop faster. Resist this
temptation.  This isn't what the lab is about, and it's not the huge
performance boost that it would seem at the outset.


\pskip
\noindent
This key aspect here for our lab is the idea of iterating step-by-step
through a for-loop.  Think of a {\em step} in the above algorithm as a
single \var{a\%b} calculation. Rather than proceeding from 2 to the
square root of {\bf N} without pause, the algorithm could instead be
paused along the way, stopping at some number $k$ between 2 and the
square root of {\bf N}. When the calculation resumes, the for-loop
simply picks up where we left off. Normally we wouldn't be interested
in calculating things in this manner, but this approach allows us to
pause our work on big potentially-hard-to-solve numbers, to quickly
handle an easy number that has arrived on the scene while working on
that big number.

\subsubsection*{Recursion}
This algorithm naturally lends itself to a recursive solution. A recursive
algorithm is just one that calls itself as part of the algorithm, with a
condition for termination. A well known one 

\begin{itemize}
\item \var{0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...}
\end{itemize}

\vspace{0.1in}
\begin{fileverb}
  Fib(n) = Fib(n-1) + Fib(n-2)
  Fib(1) = 0
  Fib(2) = 1
\end{fileverb}
\vspace{0.1in}

\vspace{0.1in}
\begin{fileverb}
  Primes(n) = k + Primes(n/k), if k devides evenly into n
  Primes(n) = n, if n is prime
\end{fileverb}
\vspace{0.1in}


%===================================================================
\subsection{A Class to Represent a Prime Number Solution-in-Progress}
\label{sec_pclass}

It will be helpful to build a C++ class to store instances of partially 
calculated entries. One example of this class is given here. The
class implementation (the \var{.cpp} file) is up to you.

\vspace{0.1in}
\noindent
NOTE: When/if you do create a \var{PrimeEntry.cpp} file, don't forget
to add it to your build list in your \var{pPrimeFactor/CMakeLists.txt}
file so it will be compiled!!


\vspace{0.15in}
\noindent
Key parts of this class are:

\begin{packed_itemize}
 \item A holder of the original prime number (\var{m\_orig}),
 \item A holder of prime factors found so far (\var{m\_factors}),
 \item The index at which it was received (\var{m\_received\_index}),
 \item The index at which it was solved (\var{m\_calculated\_index}),
 \item The index in the for-loop to start searching for prime
   (\var{m\_start\_index}),
 \item A function for finding the next prime, given a maximum number
   of steps to search (\var{factor()}),
 \item A function for generating a string report of the results
   (\var{getReport()}),
\end{packed_itemize}
\vspace{0.1in}

\begin{fileverb}
// File: PrimeEntry.h

#include &lt;string&gt; 
#include &lt;vector&gt; 
#include &lt;cstdint&gt;

#ifndef PRIME_ENTRY_HEADER
#define PRIME_ENTRY_HEADER

class PrimeEntry
{
public:

  PrimeEntry();
  ~PrimeEntry() {};

  void setOriginalVal(unsigned long int v);
  void setReceivedIndex(unsigned int v)    {m_received_index=v;};
  void setCalculatedIndex(unsigned int v)  {m_calculated_index=v;};
  void setDone(bool v)                     {m_done=v;};

  bool   done() {return(m_done);};

  bool   factor(unsigned long int max_steps);

  std::string  getReport();
  
protected:
  uint64_t      m_start_index;
  uint64_t      m_orig;
  bool          m_done;
  unsigned int  m_received_index;
  unsigned int  m_calculated_index;
  
  std::vector&lt;uint64_t&gt; m_factors;
};
#endif 
\end{fileverb}

\vspace{0.1in}
\noindent
Your MOOS app may contain a list of such elements. It will grow as new
mail comes in. And it will shrink during the \var{Iterate()} loop as 
work is done on each element. The \var{Iterate()} loop should try to 
perform some number of steps on each element, then scan the list for
those marked as done. For any done element, remove it from the list, and
generate a posting to the MOOSDB of the results.

%===================================================================
\newpage
\section{How to Test Your Application}
%===================================================================

%===================================================================
\subsection{Test with a Simple Poke}

To test your application you will need to launch \app{pPrimeFactor},
along with a \var{MOOSDB}, and generate an input. So your first
step will be to create a simple \var{primes.moos} file with the two apps
in the Antler block. Then you can simply poke the DB with:

\vspace{0.1in}
\begin{consoleverb}
  $ uPokedDB primes.moos  NUM_VALUE:=90090
\end{consoleverb}
\vspace{0.1in}

\noindent
Note the \var{:=} operator in \var{NUM\_VALUE:=90090}. This will
ensure that the value is posted as a string and not a double.

\vspace{0.1in}

\noindent
The next step is to verify your result with the simple scope:

\vspace{0.1in}
\begin{consoleverb}
  $ uXMS primes.moos PRIME_RESULT
\end{consoleverb}
\vspace{0.1in}


%===================================================================
\subsection{Test with a Simple One-Event Script}

You can make your testing a bit more streamlined by replacing the single
poke in the previous section:

\vspace{0.1in}
\begin{consoleverb}
  $ uPokedDB primes.moos  NUM_VALUE:=90090
\end{consoleverb}
\vspace{0.1in}

\noindent
You can replace this with a one-line script in \app{uTimerScript}. You
will add \app{uTimerScript} to your Antler block in your
\var{primes.moos} file.  And the below script is added also in your
\var{primes.moos} mission file:

\vspace{0.1in}
\noindent
The next step is to verify your result with the simple scope:

\vspace{0.1in}
\begin{fileverb}
 ProcessConfig = uTimerScript  
 {
   event = var=NUM_VALUE, val="90090"
   event = quit 
 }
\end{fileverb}
\vspace{0.1in}

\noindent
The last step, same as before, is to verify your result with the
simple scope:

\vspace{0.1in}
\begin{consoleverb}
  $ uXMS primes.moos PRIME_RESULT
\end{consoleverb}
\vspace{0.1in}

\noindent
You now have one less step to do, one less command to launch, to test
your work. And now that you have a mission file with a script in it,
you're ready for more fancy testing described next.


%===================================================================
\subsection{Test with a Script Generating Random Input}

When you're pretty sure that your app is generating correct answers,
you will turn your attention to {\em how fast} your app is working.
In particular, can it handle big numbers quickly? Of course the
magnitude of the number is not really the issue. For example

\vspace{0.1in}
\noindent
\var{2**48 = 281474976710656}

\vspace{0.1in}
\noindent
is a big number, but should be very fast to solve, essentially requiring
no more than 48 modulo operations.

\vspace{0.1in}
\noindent
In the below recommended test, a \app{uTimerScript} script is provided
to repeatedly generate random numbers of specified length. Following
the steps in the previous section, you will create a \var{primes.moos}
mission file with \app{MOOSDB}, \app{pPrimeFactor}, and
\app{uTimerScript} in your Antler block, and then use the below
recommended script.

\vspace{0.1in}
\begin{fileverb}
ProcessConfig = uTimerScript
{
  AppTick   = 4
  CommsTick = 4

  paused     = false
  event      = var=NUM_VALUE, val="$(15)", time=0.25
  event      = var=NUM_VALUE, val="$(9)", time=0.50
  event      = var=NUM_VALUE, val="$(7)", time=0.75
  event      = var=NUM_VALUE, val="$(5)", time=1.00
  reset_max  = nolimit
  reset_time = all-posted
}
\end{fileverb}
\vspace{0.1in}

\noindent
The \var{"\$(15)"} notation above indicates that a 15-digit number is
desired, but posted as type string. Recall the reason why we choose to
pass the number as a string is that really big numbers are not able to
be precisely represented as a \var{double}, as discussed in Section
\ref{sec_double_trouble}.

\vspace{0.1in}

\noindent
To prepare for the next testing step, the test we will use to grade
your lab, you can add one or more events to your script using known
large prime numbers. 


%===================================================================
\subsection{Grading: Test with Script Containing Large Primes}

In the test used for grading this lab, rather than leaving things to
chance, we post some really big numbers {\em that we know are prime},
and then a couple small composite numbers. We should see that the
small numbers don't get blocked by the big ones:

\vspace{0.1in}
\begin{consoleverb}
ProcessConfig = uTimerScript
{
  AppTick   = 4
  CommsTick = 4

  event  = var=NUM_VALUE, val="112582705942171", time=0.25
  event  = var=NUM_VALUE, val="115797848077099", time=0.50
  event  = var=NUM_VALUE, val="117463495419967", time=0.75

  event  = var=NUM_VALUE, val="125", time=1.00
  event  = var=NUM_VALUE, val="225", time=1.25
  event  = var=NUM_VALUE, val="325", time=1.50

  event  = var=NUM_VALUE, val="123939877913659", time=1.75
  event  = var=NUM_VALUE, val="126794093929207", time=2.00
  event  = var=NUM_VALUE, val="129263144299543", time=2.25

  reset_max  = 0
  reset_time = all-posted
}
\end{consoleverb}

\vspace{0.15in}
\noindent
Note also that we set \var{reset\_max=0} so that the script is only
executed once.

\vspace{0.15in}
\noindent
To facilate testing, add \app{pLogger} to your mission, in your
\var{primes.moos} file. Make sure you add \app{pLogger} to your Antler
block with a line like:

\vspace{0.1in}
\begin{consoleverb}
  Run = pLogger         @ NewConsole = false
\end{consoleverb}
\vspace{0.1in}

\noindent
And configure \app{pLogger} with its own configuration block:

\vspace{0.1in}
\begin{consoleverb}
ProcessConfig = pLogger
{
  AsyncLog = true
  WildCardLogging = true
  WildCardOmitPattern = *_STATUS

  LOG =  PRIME_RESULT @ 0
  LOG =  NUM_VALUE @ 0
}
\end{consoleverb}
\vspace{0.1in}

\noindent
Re-launch your mission and let it run for say a minute or so, which should
give your app enough time to process all the incoming values, even the
long ones. Then let's check the log file. Your mission should have created
a folder like:

\vspace{0.1in}
\begin{consoleverb}
  MOOSLog_2_1_2018_____09_02_19/
\end{consoleverb}
\vspace{0.1in}

\noindent
This is where \app{pLogger} generated all its output. The key file in
here is the \var{.alog} file:

\vspace{0.1in}
\begin{consoleverb}
  $ cd MOOSLog_2_1_2018_____09_02_19/
  MOOSLog_2_1_2018_____09_02_19._moos  MOOSLog_2_1_2018_____09_02_19.blog
  MOOSLog_2_1_2018_____09_02_19.alog   MOOSLog_2_1_2018_____09_02_19.ylog  
\end{consoleverb}
\vspace{0.1in}

\noindent
Now you can see the sequencing of your application by "grepping" on the
the \mvar{PRIME\_RESULT} variable:

\vspace{0.1in}
\begin{consoleverb}
  $ aloggrep MOOSLog_2_1_2018_____09_02_19.alog PRIME_RESULT NUM_VALUE
\end{consoleverb}
\vspace{0.1in}

\noindent
Verify that the solutions to the three small numbers were posted quickly,
almost immediately after their input was posted.

\vspace{0.1in}

\subsubsection*{Grading Criteria}

This lab will be graded on the specs given in Section \ref{sec_specs}.
Additionally, the coding guidelines described in the following two
C++ labs will be used to grade the quality of code used in your solution.

\vspace{0.1in}
\noindent
\urlx{http://oceanai.mit.edu/ivpman/cpplabs/coding_guidelines}

\vspace{0.1in}
\noindent
\urlx{http://oceanai.mit.edu/ivpman/cpplabs/style_guidelines}



\end{document}
</pre></body></html>