\font\largerbold = cmbx10 scaled \magstep1
\font\largerrm =cmr10 scaled \magstep1
\nopagenumbers
\def\H{\char `\^}
\def\map{{\tt Maple}}
\font\sc=cmcsc10.tfm
\font\show = cmdunh10.tfm
\magnification=\magstep1
\rightline{\sevenrm February 16, 2000}
\centerline{\largerbold Experimental mathematics}
\bigskip

\def\e{$\ldots$\ }

\noindent {\bf Some \map\ instructions}

\medskip

In this assignment we will explore how rapidly \map\ can solve some
simple modular equations. Remember: you can't break the program -- you
can always exit it and try again if something goes wrong. You should
be \underbar{at a terminal using \map} when you read the remainder of
what is written here. Two new instructions will be needed, and trying
them as you read this will almost certainly improve your
understanding.

\medskip
\noindent {\sc The first instruction} {\it msolve}
\medskip

{\it msolve}\/ solves modular equations. Suppose you want to solve
$$7x=3\quad{\rm mod\ } 13.$$
Type the instruction {\it msolve(7*x=3, 13);} 
(remember that you must end an instruction with
a semicolon so that \map\ will know you're done telling it what to
do). The answer should be {\it $\{$x=6$\}$ } and I hope you realize
that $7\cdot 6= 42$, and that 42 is $(3\cdot 13) + 3$, so the
remainder of 42 after division by 13 is 3. 

Now go to the keyboard and be sure you know the answers to these
questions:

\smallskip

{\parindent=.5\parindent

{$\bullet$} Type {\it msolve(2*x=4,8);} and explain the result.

{$\bullet$} Type {\it msolve(2\H x=1,8);} and explain the result.
  {\it \H}\/ is exponentiation, not multiplication.


\smallskip


\noindent Remember you can type {\it help(msolve);} if you want
information about {\it msolve}.

}
\medskip

\noindent {\sc The second instruction} {\it showtime}

\medskip

This instruction will allow you to see how much computer processing
time \map\ uses. Type the two instructions {\it readlib(showtime);
  showtime(on);} and see what happens. 

The first instruction tells \map\ to load the command {\it showtime}\/
and the second turns {\it showtime}\/ on. In order to tell you that
{\it showtime}\/ is on, the \map\ prompt {\bf\tt [>} has changed to
{\bf [01 :=}.  Now type {\it 3333\H 4444;} and look at the result.
First, you should get lots and lots of output (3333 multiplied 4444
times with itself is quite a big number as you can see) -- don't
worry.  The output should end with the digits {\it 81521}. Then {\it
  showtime}\/ will report the time and computer ``space'' used by the
computation.  I'm checking \map\ on three computer systems as I type
this: on one, the instruction took 3.69 seconds, on another, it took
0.29 seconds, and on the third, 0.04 seconds. Computers run at
different speeds. If you want, you can type {\it help(showtime);} to
see what showtime does and what it reports.

%\vfil
%\rightline{\sevenbf OVER}
%\eject

\bigskip

\noindent{\bf Your assignment}

\medskip

This will be a purely empirical\footnote*{\sevenrm A dictionary's
  definition of this word begins: ``based or acting on observation or
  experiment, not on theory.''} study of how fast \map\ solves some
modular equations. You will need to use {\it showtime}\/ and {\it
  msolve}\/ to do this assignment. Please record some observations,
try to see patterns and make some guesses.

Choose some {\bf 4}-digit odd number. How long does \map\ take to
solve the two equations $2x=1$ and $2^x=1$ mod the odd number you
chose?\footnote*{\sevenrm Why should the modulus be odd? How many
solutions would you expect if the modulus were even?} Do this again
for a {\bf 8}-digit odd number. And again for a {\bf 12}-digit odd
number, and again \e Repeat these instructions for a bit, increasing
the number of the digits each time by 4. Report the timing results to
me.

For instance, I chose my first number to be 2335.  I typed {\it
msolve(2*x=1,2335);} and got the answer {\it $\{x = 1168\}$} along
with a line reading {\tt time = 0.01, bytes = 22462}.  Then I typed
{\it msolve(2\H x=1,2335);} and got the answer {\it $\{x =
932_{-}NN1\!\!\sim\}$} (which means that every integer multiple of 932
is also a solution to that equation) along with a line reading {\tt
time = 0.15, bytes = 1183898}.  Below is a table in which you can fill
in the times you get. As an example, I have already filled in what I
got for my 4 digit number, 2335.

One useful format for the report would be to draw a bar graph or a
line graph of the results (on the same axes) of the two series of
experiments in a pair of contrasting colors. The horizontal axis of
the graph should be the number of digits. The vertical axis should be
the time taken by \map\ to find the solutions.  In addition, give a
very brief written qualitative description of the graphs: explain how
difficult \map\ finds solving the two series of equations as the
number of digits increases.

I tried this on {\tt Eden}'s version of \map\ recently. I began to get
embarrassed at around 30-35 digits -- very likely you will see why.
You may be able to push things to about 40 digits, but don't do too
much, or we'll all get in trouble for trying this ``exercise''!

\medskip
\overfullrule=0pt

\hskip .4in\vbox{
{\offinterlineskip
\def\tablerule{\noalign{\hrule}}
\def\tableskip{\omit&height 4pt&&&&&\omit\cr}
\halign to 3.8in{\tabskip=.7em plus 1em\ \ \  #\strut
&\vrule#&\hfil#\hfil&\vrule #&#&&\hfil #\cr \tableskip
\hfil
{\hsize=1.in\vtop{\lineskip=.04in\noindent\bf\# of digits in
$\hphantom{!}$ $\bf \hphantom{,}the\ modulus$}}\hfil 
&&
{\hsize=1.in\vtop{\lineskip=.04in\noindent\bf \hfil Time to solve 
$\bf\hphantom{a} 2x=1\ {\bf mod}\ n$}}
&&
{\hsize=1.in\vtop{\lineskip=.04in\noindent\bf Time to solve $\bf\hphantom{,}  2^x=1\ {\bf mod}\ n$}}\hfil\cr
\tableskip\noalign{\hrule height1pt depth1pt}\tableskip
\hfil 4\hfil &&\hfil 0.01\hfil&&\hfil
0.15\hfil\cr
\tableskip\tablerule\tableskip
  && &&  \cr
\tableskip\tablerule\tableskip
  && &&  \cr
\tableskip\tablerule\tableskip
  && &&  \cr
\tableskip\tablerule\tableskip
  && &&  \cr
\tableskip\tablerule\tableskip
  && &&  \cr
\tableskip\tablerule\tableskip
  && &&  \cr
\tableskip\tablerule\tableskip
  && &&  \cr
\tableskip\tablerule\tableskip
  && &&  \cr
\tableskip\tablerule\tableskip
  && &&  \cr
\tableskip\tablerule\tableskip
  && &&  \cr
\tableskip\tablerule}}
}
\medskip
\noindent {\bf Note} S.~Greenfield wrote a first draft of this
assignment. It was then edited and improved by S.~Radimirovic, who
knows quite a lot more about \map.
\vfil\eject\end \tableskip
\hfil 77777777 \hfil &&\hfil
115\thinspace\raise 1ex \hbox{\fiverm
3}\qquad && &&\cr
\tableskip\tablerule\tableskip
\hfil 919191 \hfil &&\hfil
378\thinspace\raise 1ex \hbox{\fiverm
4}&&\hfil 11,035\qquad&&\cr
\tableskip\tablerule\tableskip
\hfil 7878787\hfil &&\hfil 95\thinspace\raise 1ex \hbox{\fiverm
5}&&\hfil 
2,670\qquad&&\cr
\tableskip\tablerule}
}


\vfil\eject\end


