## A very long-running program

In the interests of random number generation, I’ve been experimenting with the iteration

$x\to g^x\pmod{p}$

for a prime $p$ and a primitive root $g\mod p$.  Now, it turns out that some primes have a primitive root which generates all non-zero residues, and others don’t.  For example, consider the prime $p=19$, which has primitive roots $2, 3, 10, 13,14,15$.  Starting with $x=1$, we find the iterations produce:

$\displaystyle{\begin{array}{ll}2:&2, 4, 16, 5, 13, 3, 8, 9, 18, 1\\ 3:& 3,8,6,7,2,9,18,1\\ 10:&10,9,18,1\\ 13:&13,15,8,16,9,18,1\\ 14:&14,9,18,1\\ 15:&15,8, 5, 2, 16, 6, 11, 3, 12, 7, 13, 10, 4, 9, 18, 1 \end{array}}$

We see that no primitive root generates all non-zero residues. However, for $p=23$, we find that the primitive root 20 does generate all non-zero residues:

$20,18,2, 9, 5, 10, 8, 6, 16, 13, 14, 4, 12, 3, 19, 17, 7, 21, 15, 11, 22, 1$

Let’s call a prime such as 23, an “exponentially complete” prime. You can see a list of the first few such primes at http://oeis.org/A214876 (which has been contributed by me).

My question of the moment is: “Is $2^{31}-1$ exponentially complete?” The prime $2^{31}-1$ is one beloved by random number theorists, because modulo arithmetic can be performed very efficiently using bit shifts. In C, for example, $z \mod p$ can be computed with

(z&p)+(z>>31)

However, I can’t think of any method of finding this out except by testing each primitive root, to determine the length of its cycle. Even using GNU C, and the PARI library, and some speed-ups (for example, replacing modular exponentiation with just one multiplication from pre-computed arrays), my desktop computer has been grinding away for two days now, and is up to primitive root 1678; that is, the program has taken 2 days to test 380 primitive roots. Since there are $\phi(2^{31}-2)=534600000$ primitive roots, at this rate it will take something like $534600000/380\times 2 = 2813684.21$ days, or about $7703.66$ years. That’s a very long time.

## The HP Prime Graphics calculator

In my effort to find the perfect CAS calculator, I recently acquired one of these babies:

It has many of the hallmarks of the engineering excellence which used to be such a selling point with HP calculators: the keys are superb, the unit itself is thin with a metal back (it has a rechargeable battery, rather than using AAA’s), and its “feel” is of a superior product. The main problem with its externals is the orange letters on the white keys; especially on the numeric keys (which are darker than the others), these letters are hard to read in anything less than very good light. The cyan also on the keys (reached by using Shift) is only marginally better. The keys would be more readable if they were black rather than white or light grey, somewhat like the older HP 35s. HP have always put a lot on to their calculators, in an exemplary fashion, so I don’t know why they missed the mark here.

But that is quibbling – what’s it like for mathematics? In very many ways, absolutely excellent. The screen is crisp, clear, coloured, and also touch sensitive, so that menus can be whisked through by scrolling with the fingers, as well as by using the four-way pad just beneath the screen. My first silly test (factor $2^{67}-1$) was done instantly. Very good!

I then decided to see if I could obtain a list of the “zig-zag numbers” $z_k$; these are the number of permutations of $\{1,2,3,\ldots k\}$ in which the numbers alternately rise and fall. For example, if $k=4$ these are the zig-zag permutations:

$1,3,2,4;\qquad 1,4,2,3;\qquad 2,3,1,4;\qquad 2,4,1,3;\qquad 3,1,4,2$

There are five of them, so that $z_4=5$. It turns out that the exponential generating function for $z_k$ is $\tan x+\sec x$; so that

$\displaystyle{\tan x +\sec x=1+x+z_2\frac{x^2}{2!}+z_3\frac{x^3}{3!}+z_4\frac{x^4}{4!}+\cdots }$

You can read about these lovely things on the Wikipedia page on alternating permutations.

So:

 s:=series(TAN(x)+SEC(x),x=0,16) seq(coeff(s,x,k)*k!,k=0..16) 

produced the sequence nicely. All of the constructs in those commands are available through menus.

The calculator has two “views”: “Home” and “CAS”. In “Home” view you have floating point calculations, and variables are by default upper-case letters; in “CAS” view operations are exact, and variables are by default in lower-case. This business of lower-case/upper-case confuses me, as I don’t see the need for it. And in fact the two views seem to differ more in their restrictions than anything else. For example, the menus seem the same in both views, but if you try the above series computation in “Home” view, the screen gives you:

 CAS.series(TAN(X)+SEC(X),X=0,16) 

It looks as though all the CAS operations are available in Home as methods in a CAS class, but in fact the output of this command is simply 1. I don’t understand this at all.

I also use lists a huge amount in my CAS work, but the MAKELIST command only seems to work in Home view, even though it’s available on the same menus in CAS view. Again, I’m quite unclear about the wisdom of having menu items which don’t do anything.

When I introduce students to CAS calculators or to computer-based systems, I get them to find (by trial and error) the smallest $k$ for which

$\displaystyle{\sum_{n=1}^k\frac{1}{n}>10.}$

This gives them a tiny insight into the speed and power of computational mathematics. And I have done this over the years with Derive, Maple, Maxima, Axiom, Sage, TI-nspire, and CASIO ClassPad. But guess what? you can’t perform this computation on the HP Prime because the SUM function only allows 1000 elements to be summed! I’m told this is an “inadvertent” oversight left over from the HP 39gII, on which much of the HP Prime is based (as well as using a slightly cut-down version of Xcas). It’s a pain though.

The calculator has 14 “Apps”: you can see 12 of them in the picture above (the other two are “Polar” and “Sequence”). In each App some of the keys on the keypad have actions particular to the App. For example, in the “Function” App, the “Symb” key allows you to enter functions, but in the “Sequence” App you get to enter a sequence definition instead. However, the on-screen menus are unchanged.

When I first got the calculator I was plagued by sudden and inexplicable freezes and spontaneous reboots. These have become more rare, but they still occasionally happen. Sometimes the calculator can be unfrozen by a key combination (On+Symb usually works). There is also a “reset” hole at the back, for use with a paper-clip. At the very worst you can unscrew the battery pack cover and temporarily unseat the battery.

I like this machine very much, in spite of its annoyances: I like it a great deal more than the Casio ClassPad (even though the CP has a bigger screen). I would hope that its peculiarities: occasional menu items which don’t work, restrictions on things like SUM, confusions between upper and lower case variables and the Home/CAS views, will be ironed out in the next generation (if there is one).

## The Casio Classpad fx-CP400

The Casio ClassPad II (fx-CP400) is the latest CAS offering from Casio: building on the previous ClassPad model to provide a calculator with a large color screen, and the ability to operate it in landscape or portrait mode.

I acquired one of these babies a few months ago, and should have posted about it then, but didn’t. So here goes.

The first reaction on seeing it was that it was very big. In fact I think this is just a matter of its huge screen: the entire unit is in fact not much bigger than the TI-nspire. Here’s a shot of the two of them (in their protective cases), with a pair of spectacles and a ballpoint pen for comparison (the ClassPad is on the right):

And here with their cases off, ready for action:

The screen is absolutely gorgeous – I can’t say enough good things about it. Crisp, well saturated colors, great for things like sketching a function and its derivatives; really beautiful. What else is good about it? Well, here’s where things get a bit tricky: in fact, I can’t really find any.

Here’s a few random comments:

1. The system is not much unchanged from the previous ClassPad models. You still have the stylus-driven menus (and very good they are), and woefully underpowered hardware. I did a tiny test: to factorize Cole’s number $2^{67}-1$. Here are some timings:
• TI-nspire: Pretty quick (a few seconds; sometimes longer if the memory’s full)
• Android Maxima (on my Samsung Galaxy S III): almost instantaneous
• Casio ClassPad: a day until it ran out of batteries
2. I have long been critical of 3D graphing on the tiny screens of most CAS calculators: but here at last is a screen on which 3D graphics would work very well. But guess what: Casio, in their wisdom, have not included 3D graphing in this system!
3. The buttons below the screen are small, plasticky, and feel cheap. Because of their size they wobble a lot. (However, the buttons on the TI-nspire, in spite of comparable size, have hardly any wobble.) The feeling is of a cheap build.

I expect that Casio is aiming fully for the school market. The combination of software and hardware means that this machine would be inadequate for any but the simplest mathematics. I don’t see why this should be so – better programming and a more powerful chip would make this machine into a really useful mathematical tool. As it is I see it as a gorgeous body with not much strength underneath.

## A first look a WeBWorK

In my last post (nearly three months ago) I commented on online assessment, and in particular on Pearson’s MyMathLab Global, which we have been using for our engineering mathematics. This is quite a good, full-featured and robust package; its only fault (if indeed a fault it be) is that it’s commercial. This works fine if you are structuring your course around a set text, but over the years I have moved further and further away from such texts. I have not found a text which could be used comfortably with my extraordinarily heterogeneous student cohort, who enter our courses with all different levels of mathematics competency, and all different levels of written and spoken English.

A good text must be carefully, simply, and clearly written, with plenty of useful examples, and above all well scaffolded exercises which move gently from the very simple to the complicated. Most (all?) textbooks in my experience suffer greatly from this. Our current preferred textbook: “Modern Engineering Mathematics” by Glyn James, has quite appalling exercises. Also, it’s bit of a heavy monster of a book, like most mathematics textbooks, and I don’t see why students should have to lug it around with them. But anyway, if you do buy the book, either in hardcopy, or in electronic form, you get a code which gives you one years access to MyMathLab and all ts trimmings.

So this last semester I have used my own notes and exercises for engineering mathematics, and sent students off to MyMathLab for their weekly online tests. There were problems:

1. Students who first started over a year ago (who, for example, might have had to take a break between their mathematics subjects) found that their access codes had expired. I spent the first few weeks of the semester writing almost daily emails to the publishers begging for some more access codes. To their credit, the local Pearson reps were in every way helpful, accessible, friendly, and understanding.
2. Right towards the end of the semester I kept finding students who had fallen through the cracks, so to speak, and hadn’t been able to access their tests at all. (And had got busy with other subjects and kept forgetting about them)
3. Some answers were marked wrong, when they weren’t. I had one student who sent me a screen shot to show that he had entered “12″ as the numerical answer to a problem, which was marked wrong: the correct answer, apparently, was “12/1″. There was also confusion with decimal places: a question would ask for say 4 correct decimal places, and no matter how carefully the students entered their answers they were marked wrong.

I have wanted to experiment with WeBWorK for a while now, but I couldn’t find a way to install it locally – until I realized that I could install it (and a web server) on my desktop at work, which runs Ubuntu 12.04. I did this (it took most of a day, with only a modicum of swearing, and messages to the WeBWorK forums), but now I have a working system, even if only running on a desktop, rather than on a dedicated server.

WeBWorK has many excellent features:

1. It’s free: open source, no less. You can pay for MAA to host your course if you don’t want to set up your own local service, but even that option is very inexpensive.
2. It has a huge problem library: the Open Problem Library has something around 25,000 problems from most areas of undergraduate mathematics. You might not find problems on, say, cohomology or modular forms, but these advanced topics would hardly be well served by an online homework system. We are assuming here we have a large class (in the many 100′s) of students in their first or second year of university study. And for this sort of basic mathematics, WeBWorK is terrific.
3. The authoring system for creating new problems is very straightforward: just a matter of some elementary editing. I tried authoring a problem in MyMathLab once, and although it’s quite possible, life’s too short.
4. WeBWorK seems to play very nicely with LaTeX and Sage, so that the mathematics is properly typeset, and you can have all the power of Sage available to you if you need it.

That’s as far as I’ve got so far. You can get a feel of WeBWorK without installing it by checking out some of MAA’s “Model Courses”, of which a list is here. There doesn’t seem to be any online hosted method for browsing the problem libraries to see what’s in them, as far as I know. I think this could be something worth making available so that teaching staff can decide whether they think WeBWorK would suit them and their courses.

In my current state of thinking, if I can get a better hosted system at my work (that is, not my desktop), I may well use WeBWorK for my next teaching semester.

## Online assessment in mathematics

This semester I’ve taken over a large first year subject, for which the previous subject convenor had organized to use MyMathLab Global for weekly testing.  The subject is based around Glyn James’ “Modern Engineering Mathematics”, a book which is OK for content, and pretty awful for exercises.  This means that as users of the text, we have access to the publisher’s (Pearson) online testing service.  For educators the idea is terrific: every week I simply pull from the exercise bank a set of 10 exercises corresponding to our current topic, and make them available for a week during which time students can have unlimited goes at them.  So in theory it’s an easy way for students to get some easy marks, and reduce the burden of marking weekly tests by the lecturer (me) and the subject tutors.

The subject I am teaching “Engineering Mathematics 2″ is a follow on subject from – wait, you;ve guessed it! – “Engineering Mathematics 1″.

What could be better?  Well, aside from the extraordinary ease of testing, I have begun to have doubts about the efficacy of the system.

1. It’s a commercial system, which means that students have to buy a “personal access code” to use it.  A code comes with the book if they purchase it.  However, a code lasts for only 12 months, and if students have bought the book (and its code) for Eng Maths 1 (as they all should), and if there’s been a break in their studies for any reason, then their code may have expired by the time they come to Eng Maths 2.  Then there are all the students who have got subject exemptions from Eng Maths 1 and never had a code in the first place.  The local publishers reps have been terrific and have provided me with lots of extra codes to hand out, but the onus is on me to get these dratted codes in the first place, and ensure the students get them.
2. The system only tests the final answer.  A typical question is:

Find the partial derivatives

$\displaystyle{\frac{\partial f}{\partial x}}$, $\displaystyle{\frac{\partial f}{\partial y}}$ and $\displaystyle{\frac{\partial f}{\partial y}}$ of $f(x,y,z)=\sin^{-1}(xyz)$.

and the students get three entry boxes for their results.  MyMathLab Global is very picky about the form of a solution, and if the form of a student solution differs from the “correct one” they are marked wrong.  For example,  we find that

$\displaystyle{\frac{\partial f}{\partial x}=\frac{4yz}{\sqrt{1-16x^2y^2z^2}}}$.

if a student leaves out the “1″ of the “16″ in error, the answers is just marked wrong.  If the student decides to write

$\displaystyle{\frac{4yz}{\sqrt{(1-4xyz)(1+4xyz)}}}$

it is marked wrong.  MyMathLab Global doesn’t seem to include a CAS to check if two answers are equivalent (aside from some very simple arithmetic and operator commutativity).  This has been a source of annoyance to my students, who may enter an answer which is mathematically correct, and yet marked wrong.  A very spirited attack on MyMathLab Global can be seen here.

3. The system checks only the final answer. We might well ask: what mathematical learning is actually being tested here? Surely we want our students to show that they have mastered a mathematical technique, process, or algorithm, and we would mark them on their working, not just on the final answer. At least, that is how I mark by hand. A question for which the student’s working is fundamentally correct but the final result is wrong will still get most marks from me. I regard the final result as just one part of a question. So suppose the student sets out to answer a question, and makes a small slip somewhere along the way which effects every succeeding step, and the final result. I would give almost compete marks – there’s only been one very small slip, and aside from that the logic and the working are exemplary. But MyMathLab Global can’t do this. An answer is either correct, or wrong.

I have been hoping to check out MAA WeBWorK as a comparison, but the only server I have access to runs a linux distribution (RHEL 5.9) which can’t run it. I think WeBWorK, from my understanding, is rather more nuanced in terms of mathematical equivalence of expressions, so probably overcomes item 2 above, and being open source completely overcomes item 1. I don’t think it overcomes item 3, though.

I will continue to use MyMathLab Global – its convenience is simply too great – in spite of my misgivings. But I think that online assessment in mathematics is still a very long way from testing the students’ ability to do mathematics, as opposed to their ability to obtain an answer. This latter is not mathematics: it is applied arithmetic; and noble and useful as it may be, it is only a tiny part of what we, as mathematics educators, should be testing.

## Further comparison of TI-nspire CAS and Casio Classpad 330 calculators

I intended to post a lot about these calculators over the past few months, but, err… didn’t.  Anyway, I’ve been using both extensively (mainly to perform numerical computations), and here’s a few things I’ve found out:

1. The ClassPad 330 handles variables far better than the TI-nspire.  The TI-nspire does have a menu command for removing all variables with a single letter name, but there’s no easy way to go though a list of variables, check some (or all), and delete or move those selected.  The ClassPad provides this functionality.
2. The TI-nspire allows programming constructs to be used in a command.  For instance, you can use a for-loop to build a list.  The ClassPad, however, allows such constructs to be used only within a program.  This makes the TI-nspire slightly more efficient to use.
3. Neither calculator, as far as I can find, allows you to pull apart an expression into component parts.  This is a standard functionality of all CAS’s, and I don’t know why it’s missing here.
4. The TI-nspire has some useful matrix commands lacking on the ClassPad.  For instance, there’s no way on the ClassPad (other than writing a program) of creating a matrix whose elements are functions of the row and column indices.   The ClassPad also lacks commands for pulling out the diagonal elements of a matrix.  And curiously enough, given an $n\times n$ matrix $A$ and a $n\times 1$ column vector $b$, the ClassPad lacks a command for solving the matrix equation $Ax=b$.  You can of course compute $A^{-1}b$, but that’s it.

Both calculators lack various functionality present on the other, and so weighing one against the other they’re pretty even.  Both have room for improvement (I’m looking forward to seeing the new whizz-bang all-singing all-dancing FX CP-400 when it reaches our shores in a few months).  I personally find the TI-nspire slightly faster and easier to use.

Finally – why a calculator?  As a few correspondents have pointed out, you can get (if not now, then soon), much of the same functionality on a smartphone or tablet – and indeed TI have produced an app version of the nspire – so why buy a calculator which does only one thing, when for only a little bit more you can buy a tablet which does all of that and more?

Part of the answer lies with education: you can easily allow a calculator in a test or exam – and change the mode of questions to be more method focused than answer focused – when you would never allow a tablet (at least, I can’t think of any testing milieu which would allow a tablet).  Also, calculators are easier to use than any tablet, at least for maths.  You can enter a complicated expression such as:

$\displaystyle{\frac{d}{dx}\left(\frac{\sqrt{1+\sin x}}{1+e^x}\right)\tan^{-1}\left(\frac{1}{1+x^2}\right)}$

very easily on a CAS calculator by pressing only a few keys; whereas on a tablet such an expression may mean hunting through different menus to obtain all the symbols you need.

Calculators also tend to be more robust than tablets; they can survive being tossed around in bags and pockets without requiring after-market protection or care (both the TI-nspire and ClassPad come with hard covers as standard.)  And because of the small screens, they use less power.  So a student (or anybody else) can bung a calculator into their pocket or bag, and have it ready to use whenever they want.

For these reasons I still think calculators have a place.

## Easy Simpson’s rule

Simpson’s rule, as I’m sure all readers of this blog will know, is a simple rule for numerical integration (or quadrature). It can be obtained in two ways, either by determining the interpolating polynomial over three equally spaced points and integrating that polynomial, or by finding the values $w_i$ for which

$\displaystyle{\int_a^bf(x)\,dx = w_0f(a)+w_1f(a+h)+w_2f(b)}$

(where $h=(b-a)/2$) is accurate for $f(x)=1,x,x^2$.  Over the interval $[0,2]\,$ Simpson’s rule is

$\displaystyle{\int_0^2f(x)\,dx = \frac{1}{3}\Bigl(f(0)+4f(1)+f(2)\Bigr)}$

and over a general interval

$\displaystyle{\int_a^bf(x)\,dx = \frac{b-a}{6}\Bigl(f(a)+4f(a+h)+f(b)\Bigr)}.$

Simpson’s rule has the added advantage that it is also accurate for cubic polynomials.

On its own the rule is not hugely accurate, so one way of increasing the accuracy is to divide the interval into smaller, equally sized regions and apply Simpson’s rule to each of them. This provides the composite Simpson’s rule:

$\displaystyle{\int_a^bf(x)\,dx \approx \frac{b-a}{3n}\Bigl(f(a)+4f(a+h)+2f(a+2h)+4f(a+3h)+\cdots\Bigr.}$

$\displaystyle{\Bigl.+2f(a+(n-2)h)+4f(a+(n-1)h)+f(b)\Bigr)}$

where $n$ is even and $h=(b-a)/n$. Sometimes this rule is written

$\displaystyle{\int_a^bf(x)\,dx \approx \frac{b-a}{6n}\Bigl(f(a)+4f(a+h)+2f(a+2h)+4f(a+3h)+\cdots\Bigr.}$

$\displaystyle{\vspace{1cm}\Bigl.+2f(a+(2n-2)h)+4f(a+(2n-1)h)+f(b)\Bigr)}$

where there is no restriction on $n$ and $h=(b-a)/2n$. For a spirited criticism of this rule, both from practical and pedagogical perspectives, see here.

However, in a standard generic mathematics course, Simpson’s rule is as far as most students get with quadrature. The trouble is that the order of the weights (the coefficients of the function values):

$1,4,2,4,2,4,...,2,4,1$

is tricky to program. Either you have to run two loops, one for the 4′s and the other for the 2′s, or you have to do a little test at each stage to see whether you are at a 2 or 4 point, or you might invoke the modulus function. None of those ways are particularly straightforward, especially if, like many beginning students, you have little programming experience.

So here’s a super easy way. We start with end points $a$ and $b$ and an even integer $n$. We first create a list of all the values at which the function is to be computed:

$xs=[a+kh \mbox{\; for\;} k=0,1,2,\ldots n]$

where $h=(b-a)/n$, and then a list of the weights:

$w=[3-(-1)^k \mbox{\; for\;} k=0,1,2,\ldots n].$

This last list is $[2,4,2,4,\ldots,2,4,2]$.

We then compute

$\sum w_if(xs_i)$

However! note that our list of weights starts and finishes with 2′s instead of 1′s. We correct for this by simply subtracting $f(a)$ and $f(b)$ from the sum. Our “easy” Simpson’s rule is then:

$\displaystyle{\frac{b-a}{2n}\Bigl(\sum w_if(xs_i)-f(a)-f(b)\Bigr)}.$

This is almost trivial to compute. For example, on a TI-nspire CAS calculator, we might have:

$a:=0$

$b:=1$

$\mbox{Define\;}f(x)=e^{-x^2}$

$n:=16$

$h:=(b-a)/n$

$xs:=\mbox{seq}(a+k\cdot h,k,0,n)$

$w:=\mbox{seq}(3-(-1)^k,k,0,n)$

$(\mbox{sum}(w\cdot f(xs))-f(a)-f(b))\cdot (b-a)/n$

The TI-nspire has the nice attribute that a function applied to a list will produce a list of all function values, and the product of two lists is a list containing all the products of corresponding elements. The Casio Classpad has the same functionality with lists, and the above commands can be used.

This approach of using $3-(-1)^k$ to obtaining the weights for Simpson’s rule seems not widely used, but it seems to me to be absurdly simple. I’ve only come across it in one other place.