Posts
Latest Posts

Tube, DLR, and Overground disruption calendar
I wrote a Python script that uses TFL’s helpful API to produce calendars of planned disruption on tube lines, on the Overground, and the DLR. The calendars are shared through Google Calendar; you can use the
ics
files to add them to any calendar app. 
How sin and cos are computed in c and Python
This post is about how sin and cos are calculated in the c language standard math library on a typical Linux system. Because Python floats are really c doubles, what I write here will apply to Python too. For background on how floating point arithmetic works, What Every Computer Scientist Should Know About FloatingPoint Arithmetic by David Goldberg is useful as is the wikipedia page on double precision floating point format.

do_cos
This post is about the
do_cos(double x, double dx)
function froms_sin.c
, following on from my previous post ondo_sin
. The function computes an approximation of \(\cos(x + dx)\) whendx
is so small that the floating point additionx + dx
might not be exact.do_cos
is defined on lines 95117 of thes_sin.c
source code. 
do_sin
This post is about the
do_sin(double x, double dx)
function froms_sin.c
. The source code is here. 
Range reduction in glibc with reduce_sincos
This post is about the
reduce_sincos
range reduction function from the glibc math library. You can find the source here, starting on line 151.. 
Memoization and closures in Scheme and Python
SICP exercise 3.27 discusses memoization in Scheme (get a large piece of paper if you want to draw the full environment diagram!). We make a couple of definitions

Expressing reverse as a left fold
Right fold has the laws

gcc optimizations and the sin function
It is wellknown that
gcc
optimization levels affect the results of floating point calculations, and the link says it can even happen with simple statements likex * y + z
. This has an unfortunate corollary: how accurate a compiled c program’s floating point calculations will be is not a function of the source code alone. 
How to use the accelerometer in a ThinkPad x220
Older ThinkPads had builtin accelerometers so they could detect falls and protect the hard disk. It’s really easy to get access to the accelerometer data in Linux: just install
tp_smapi
and then load the hdaps module withsudo modprobe hdaps
(or add it to the list of modules to be loaded at boot in/etc/modules
or/etc/modulesload.d/modules.conf
). You should then be able to get the accelerometer output from the file/sys/devices/platform/hdaps/position
, which will contain a single line of the form(<roll>,<pitch>)\n
whereroll
andpitch
are numbers. If the only acceleration of your ThinkPad is due to gravity you can work out the roll and pitch angles from these. On my x220, holding the keyboard dead level (i.e. in a plane perpendicular to the direction of gravity) gives readings of (505, 505), and the individual readings run from about 360 to 650 as the angle varies from 90 to 90 degrees. 
In Python, why is sin(pi/2) exactly 1 but cos(pi/2) not exactly 0?
A student in my introductory Python class asked me why this happens. Try it yourself:
from math import sin, cos, pi print(sin(pi/2)) # 1.0 print(cos(pi/2)) # 6.123233995736766e17

Containment of Bruhat intervals modulo a maximal parabolic subgroup
Susama Agarwala, Colleen Delaney, and Karen Yeats just published a preprint Rado matroids and a graphical calculus for boundaries of Wilson loop diagrams that references some old unpublished notes of mine, done when I was a postdoc of Stéphane Launois at the University of Kent. I’ve uploaded my notes Containment of certain Bruhat intervals modulo a maximal parabolic subgroup in type A in case anyone reading their preprint wants to see them.

UCL shower facilities
If you cycle to work, like me, you probably want to take a shower when you arrive. UCL has a page about their shower facilities but it’s a bit vague about which ones can be accessed and where they are. Here are the ones I’ve found or tried to find.

Converting LaTeX to html with PlasTeX
PlasTeX is a Python program that parses tex files and can output to several formats, including html, using MathJax to render mathematics. It has an impressive list of users including the Stacks project, Kerodon, SAS, the Liquid Tensor Experiment, the sphere eversion project, and others. Stacks and Kerodon use gerby in conjunction with plasTeX which in turn uses flask. The most recent plasTeX release was January 2023 (see here).

Permutations whose images are a basis of the endomorphism algebra of a module
If \(G\) is a finite group and \(S\) is a \(\mathbb{C}G\)module then the linear maps \(\rho_g: s \mapsto gs\), as \(g\) varies, span a subspace of \(\operatorname{End}_\mathbb{C}(S)\). We can ask for a “nice” subset of \(G\) such that the corresponding linear maps are a basis of that subspace. In the case that \(S\) is simple, the subspace will be all of \(\operatorname{End}_\mathbb{C}(S)\), by the Jacobson density theorem.

Fuzzy text matching in Python
Imagine that you’ve been given a spreadsheet recording which of your students will attend which of 9 computer classes. You just have the names and classes, but you need to know the email addresses of the students in each class so that you can contact the students in a specific class (e.g. to tell them that it is cancelled because you are going on strike). Asking for a spreadsheet containing the emails as well as the names doesn’t help.

Using QR codes in lectures
I teach the first year UCL maths module MATH0005 Algebra 1, a compulsory module for about 320 maths first years covering logic, sets, functions, permutations, matrices, and linear algebra. I took over this module two years ago, so this is the first time that we have inperson lectures  for the past two years the course was delivered through a long series of videos (YouTube playlist link).

Teaching Python with CoCalc
I teach the Python part of UCL’s first year module MATH0011 Mathematical Methods 2, a four week long introduction to Python for total beginners, taken by 200250 maths and joint schools students. We cover the basics of Python data types, loops and conditionals, objects and classes, and finish off with a quick look at mathematical applications of the NumPy and Matplotlib modules.

Naive Decision Making
Naive Decision Making by Tom Körner is a really interesting and wideranging book and I recommend you buy it. Read all the journal reviews for details, I am too lazy to write more. Obviously if you’re reading it as a beginner you should be doing almost all of the many exercises, but unfortunately they have a few bugs. This post is just to give a link to the new ones I found which I’ll leave up until they get incorporated into the author’s list of errata

Elements appearing with prescribed frequency in a list
Suppose you have a list
A
of sizen
and a numberk
which is at mostn
, and you want to find all elements ofA
which appear more than \(n/k\) times inA
in \(O(n \log k)\) time. You can do this using algorithm (3) of Finding repeated elements by J. Misra and D. Gries in Science of Computer Programming Volume 2, Issue 2, November 1982, pp.143152, which I’m going to describe here. 
What is the largest primorial fitting in a 32 bit signed int?
Let the prime numbers be \(p_1 = 2, p_2 = 3, p_3 = 5, \ldots\). The primorial \(p_k\#\) is \(p_1p_2\cdots p_k\). What is the largest primorial that fits in a 32 bit signed int?

The Python Tutorial
I read through the Python 3.9 tutorial and wrote up these notes to help me remember certain things. Section headings and numberings follow those in the tutorial.

The Python Language Reference
I’ve been reading the Python 3.7 Language Reference and will use this post to write up bits that were new to me so that I don’t forget them immediately. Sections are named after the corresponding section of the language reference.

Using offlineimap with a UCL email account
The below won’t work now that UCL has mandated OAUTH2. You can instead get isync and msmtp to work with OAUTH2 although it takes some configuration. oauth2ms and the mbsync configuration it suggests worked for me, but you must make sure the Azure app you create is set to web not mobile/desktop. To get smtp working you must change the msmtp config file to read

Maximum area under a histogram
Suppose you have an 0indexed array
h
of nonnegative integers with length \(n\) and want to maximise the quantity(ji) min(h[i:j])
over all \(0\leq i < j \leq n\). This is an old chestnut coding exercise found on all the algobashing sites, often called the “maximum area under a histogram” problem because if you consider the histogram which has a bar of heighth[0]
above the interval \([0, 1)\), a bar of heighth[1]
above \([1, 2)\), and so on, then this(ji) min(h[i:j])
is the area of the largest rectangle sitting on the \(x\)axis whose lefthand edge is part of the line \(x = i\) and whose righthand edge is part of the line \(x=j\) and whose height is the minimum value inh
between indexi
(inclusive) andj
(exclusive), so that the rectangle is completely contained within the histogram. 
Proof of a sine identity
Claim: \(\sum_{k=1}^n \sin(k) = \frac{\sin(n/2) \sin((n+1)/2)}{\sin(1/2)}\).

Automatically opening files
This summer we had thousands of exam scripts submitted as pdf files which had to be marked by annotation. They arrived as folders containing pdf files named by alphanumeric candidate ‘number’, and marks had to be recorded in a spreadsheet sorted by candidate number.

Subtitling lecture videos
This is about making subtitles for lecture videos.

A STACK maxima package
I have spent a lot of this summer writing STACK questions. STACK uses Maxima as its back end, so I ended up writing a lot of Maxima code. Some of this is now publicly available on github, as the
maximalinalg
repo. 
Basic data structures
Some rough notes on basic data structures and the complexities of associated operations, with usage notes in Java and Python.

Bidirectional Dijkstra
Dijkstra’s algorithm computes lengths of shortest paths from a start vertex \(s\) to every other vertex in a weighted graph with nonnegative weights. It works by successively improving an approximation \(d[v]\) to the shortest path length \(\delta(s,v)\) from \(s\) to \(v\), which is initially \(d[s]=0\) and \(d[v]=\infty\) for \(v \neq s\). The algorithm maintains a priority queue \(Q\) of vertices which haven’t yet been processed, initially containing just \(s\) with priority 0, and a set \(S\) of vertices whose true distance to \(s\) is known. It works as follows, in pseudoPython:

PSB regulations accessibility requirements for video
This is a continuation of my earlier post about the requirements of The Public Sector Bodies (Websites and Mobile Applications) Accessibility Regulations 2018 for documents supplied to students. It is quite possible that there will be extensive online teaching in autumn 2020, much of which would be delivered through live or prerecorded video. This post is about what the PSB regulations require for this sort of content.

Connect to the UCL VPN in linux
Update 20211220. The below no longer works. I get an error telling me “Your environment does not meet the access criteria defined by your administrator” when I try to activate the VPN.

6.004 and CS143 (Compilers)
This post is about MIT’s 6.004 Computation Structures course and the edX version of Stanford’s CS143 Compilers.

Echelon form, inverses, and determinants in Numbas
This post is about authoring questions about row reduced echelon form, matrix inverses, and determinants in the Numbas eassessment system.

A Numbas permutation quiz
This post is about authoring questions in the Numbas eassessment system.

Which side are you on?

Numbas questions with no unique answer
This post is about authoring questions in the Numbas eassessment system. The good thing about Numbas is that you can install a local editor and export questions as scorm objects which can then be imported into Moodle without having to get plugins installed, unlike STACK say.

PreTeXt
PreTeXt is an xml vocabulary promising “the best of DocBook, LaTeX, and HTML.” It used to be called MathBook XML. There are examples online, like this abstract algebra text. PreTeXt makes it easy to incorporate runnable sage cells into your text, and it also has WeBWorK integration.

Compiling LaTeX to xml with Tralics
Tralics converts LaTeX to xml, you can download it from their website or install it from the Debian repos. The last official release was in 2015 but it was modified in 2018. There’s a github page. I had some hopes for Tralics because it is mentioned on the MathJax FAQ page at the bottom.

Bookdown
This post is about creating and publishing accessible lecture notes using bookdown. I converted my unfinished first year algebra course notes to bookdown format and uploaded the results.

6.002
I finally finished the edX version of MIT’s 6.002 Circuits and Electronics course. It’s a second year course there designed as a first introduction to digital and analogue circuits.

Simulating Markov chains
Let \(X_0\) be a random variable taking values in a countable set \(I\), and \(Y_1, Y_2, \ldots\) be independent and identically distributed (say \(Y_i \sim U[0,1]\)). I think we also need to assume they are independent of \(X_0\). Suppose \(G: I \times [0,1] \to I\) is a function, and define \(X_{i+1} = G(X_i, Y_{i+1})\). The problem (from Richard Weber’s Markov chain course) is to prove that \((X_i)_{i\geq 1}\) is a Markov chain  the point being that by choosing \(G\) and \(X_0\) appropriately we can simulate any Markov chain starting at \(X_0\) given only the ability to draw from \(X_0\) and to draw uniform random numbers.

Programming in the Undergraduate Mathematics Curriculum conference
This was a oneday conference at Middlesex University with short talks from NoelAnn Bradshaw, Peter Rowlett, James DenholmPrice, Vincent Knight, Matthew Jones, Stephen Lynch, and Chris Sangwin. There were so many interesting aspects of people’s talks that I can’t write them all up, but I will try to put down a few of my favourites (especially the things I thought would be useful for next year’s Python course).

Compiling LaTeX to html with the internet document class
The internet document class takes a different approach to the other programmes we’ve used so far. It is a LaTeX document class used with
\documentclass[<options>]{internet}
<options>
can specify an output format likexhtml
orepub
ormarkdown
amongst others. The document is then compiled to pdf, and text is extracted from the pdf. This text is in the requested format. 
Diversifying the curriculum workshop
Yesterday I went to a workshop called “Diversifying the Curriculum” organised by Christopher Hollings and Vicky Neale at the University of Oxford. Their aim was to

Compiling LaTeX to html with LaTeX2HTML
LaTeX2HTML (home page) is a perl script that does what the name suggests it will do i.e. translates latex to html.

Compiling LaTeX to html with HeVeA
HeVeA (home page) is an ocaml project which converts LaTeX to pure html: math is displayed as html using tables for positioning and unicode math characters. There’s no MathML or mathjax. Here is how it renders some extracts from the “Comprehensive LaTeX symbol list” to give you an idea of how well it works.

Compiling LaTeX to html with LaTeXML
LaTeXML (homepage) was developed for the DLMF (the online Abramowitz and Stegun). There is a tool
latexml
which converts.tex
to an xml representation and another toollatexmlpost
which converts the xml file to html5 and uses MathML for the math content. MathML equations are tagged with their latex source as alt text. 
IMA Workshop in Cardiff: Effective Feedback in Mathematics
Yesterday I went to a workshop organised by Rob Wilson and Matthew Pugh at Cardiff University. It was a very interesting day, although it’s disappointing to still see allmale speaker lists in 2019. I’m going to try to write up a couple of key points from each of the three scheduled talks  please don’t take these as summaries of the talks which had a great deal more content.

Compiling LaTeX to html with pandoc
Pandoc is a hugely versatile document converter written in Haskell. It is in active development with many contributors. There are many pandoc questions on tex.stackexchange.

Compiling LaTeX to html with TeX4ht
TeX4ht was created by Eitan Gurari, who sadly died in 2009. It is still under active development, but upgrading is difficult.

Compiling LaTeX to html with lwarp
This post is about my first attempt at using the
lwarp
package to compile LaTeX documents into accessible html, using MathJax to render the mathematics. I picked lwarp because it seems to be under active development, and it has a very comprehensive (over 1000 pages) manual. 
Accessibility requirements for pdf files
Mathematicians tend to supply lecture notes and problem sheets to their students in the form of pdf files created by LaTeX. This post is about what requirements the Public Sector Bodies (Websites and Mobile Applications) Accessibility Regulations 2018 legislation (“the regulations”) imposes on this sort of documents when they are supplied to students via the web, and to what extent we can meet those requirements. It will not cover requirements for other content, for example web pages, video, or audio. All of this is my legallyuneducated opinion, not that of UCL or its maths department.

Installing the STACK Moodle question type
The official instructions are here. They seem to work well, although when you clone the question behaviours in step 3 I think you’ll need to do something to make the permissions correct (in Debian everything needs to be visible to the
wwwdata
user). Prefixing the git commands withsudo u wwwdata
is one way to do this. 
Setting up a Moodle server in Debian
Getting university IT departments to install Moodle plugins is not always trivial. In order to try out the STACK question type, I decided to set up my own Moodle server on a spare computer running Debian 9 (stretch).

A MathJax test
Here’s a test of my MathJax configuration.