Understanding M. E. O'Neill’s PCG generator. Part 3

This is the third and final part of a three-part article about my attempt to understand the PCG generator. If you haven't read the previous one then it may be a good idea to do so (assuming you want to read this one, that is). The previous part looked at the structure of the various output functions that are described in O'Neill’s report and paper. This part looks at the so-called ‘named generators’ that are provided by the C++ implementation and tries to reconstruct one of them.

ONeill (2014) says:

‘… although the generators are presented with mnemonic names based on the permutations they perform, users of the PCG library should rarely select family members by these mnemonics. The library provides named generators based on their properties, not their underlying implementations …’

The file ‘/include/pcg_random.hpp’ in the archive pcg-cpp-0.98.zip contains 42 such ‘named generators’, but a single article only has enough space to to look at one. The question is, which one?

Read more

Understanding M. E. O'Neill’s PCG generator. Part 2

This is the second part of a three-part article about my attempt to understand the PCG generator. If you haven't read the first one then it may be a good idea to do so (assuming you want to read this one, that is). In particular, you may find yourself needing to refer to the descriptions of O'Neill’s creative new symbols, which are located at the end. The previous part looked at the underlying ideas that motivated the development of the method, and this one begins to delve into the details by looking at the various output functions that are described in O'Neill’s report and paper. The next and final one will try to reconstruct one of ‘named generators’ that are provided by the C++ implementation.

Read more

Understanding M. E. O'Neill’s PCG generator. Part 1

Since it was first made public in 2014 M. E. O'Neill’s ‘permuted congruential generator’ (PCG) has become very popular and has been adopted by several high profile projects. For example the ‘Numpy’ package for the Python programming language and the ‘dqrng’ package for the ‘R’ programming language both include a PCG generator.

O'Neill describes its origin thus:

… Thanksgiving break of 2013. Looking for an escape from a stack of midterms I had to grade, … I saw a fun programming challenge …
(O'Neill, 2017)

Not bad for a holiday diversion!

Read more

Hull and Dobell’s first theorem


One of the most widely used types of pseudo-random number generator is the linear congruential sequence. These are defined by recurrence relations of the form \begin{equation}\label{eq:genrandnum_hull_dobell_01} x_{i+1} \ \equiv \ ax_{i} + c \quad (\operatorname{mod} m) \end{equation} where all the terms are non-negative integers. The usual terminology is that \(a\) is called the ‘multiplier’, \(c\) the ‘increment’ and \(m\) the ‘modulus’.

Any such sequence must be periodic since it contains at most \(m\) different numbers each of which is determined only by its predecessor. The period can therefore never exceed \(m\) but even that cannot be guaranteed. A long period is necessary but not sufficient for good pseudo-randomness, so it is important to understand the conditions that determine its length.

That is the objective of a paper published in 1962 by T. E. Hull and A. R. Dobell (Hull and Dobell, 1962). If you have read anything about the subject you have probably heard of something commonly referred to as ‘the Hull-Dobell theorem’. The paper actually presents two theorems, but it seems that only the first gets called ‘the’.

Read more

The mathematics of lockdowns

During the pandemic the death rate per 100,000 of population has varied widely between countries. For example at the time of writing the UK's rate is 72.51 while Germany's is 13.40, a factor of 5 smaller despite the two countries being superficially similar in other ways (see here for the current Wikipedia article containing these data and here for a snapshot at time of writing).

There are obviously many things that the UK and Germany did differently but the media have particularly focused on the fact that Germany locked down earlier than the UK. Coronavirus was first confirmed in Germany on January 27 and they locked down on March 13, a period of 46 days, whereas the first two cases in the UK were confirmed on January 31 and lockdown began on March 23, a period of 52 days, six days later than in Germany.

This doesn't seem like a huge difference. Could it really be that locking down a mere six days earlier could have reduced the UK's death rate by four fifths? This article attempts to answer this question.

Read more

The failures of political journalism

I've just watched a video of an interesting talk entitled ‘The failures of political journalism’ delivered by the journalist Helen Lewis on 29 May 2019 at a seminar organised by Oxford University's ‘Reuters Institute’. It can be seen on the institute's website and also on Youtube. The talk identified ‘seven deadly sins’ that political journalists perpetrated over the course of last two general elections and the two referendums. This article will first briefly discuss them then suggest some new ones. The sins are:

Read more

Review of ‘Dangerous Hero: Corbyn's ruthless plot for power’, by Tom Bower

This book posits that the hard left plans to end democracy in Britain. Describing the aftermath of the 2015 Labour leadership election, Bower writes:

‘Commentators criticised Corbyn's ‘poverty of ambition’ for failing to win the political centre, but they misunderstood. As unwilling as ever to compromise, he planned to defeat the PLP, transform Labour into a genuinely Marxist party, and win sufficient electoral votes to become prime minister. Just the one victory would be enough. Thereafter, McDonnell boasted, their changes would be ‘irreversible’. [ … ] Just as Corbyn and McDonnell intended to revise the Labour Party's rules to permanently protect their coup from any challenge by social democrats, they would change the British constitution to cement their victory. The result of the second general election would be a foregone conclusion.’

This may seem like a paranoid conspiracy theory but by telling Jeremy Corbyn's life story Tom Bower tries to show that it isn't as paranoid as it sounds.

The book is a tabloid hatchet job, its nature given away by the large typeface. Throughout the book Bower regularly assumes the reader holds a number of conservative attitudes thereby potentially alienating readers who don't, probably the very ones he is most trying to convince, in whose minds those of the book's criticisms that are genuinely valid may be devalued. For example:

Read more

Book review: ‘Fossil Capital: The Rise of Steam Power and the Roots of Global Warming’, by Andreas Malm.

When I bought this book I thought it was going to be a history of steam power in the textile industry in the eighteenth and nineteenth centuries. I was looking forward to reading about cross‑compound engines, Corliss valve gear, centrifugal governors and indicator diagrams.

When I opened it I was surprised to discover that it is, in fact, a sequel to Karl Marx’s Capital. It attempts to weave (no pun intended) the idea of fossil fuel into the fabric of Marx’s theory of class struggle. It aims to show that capitalism and fossil energy are so intimately connected that they cannot be separated, from which it follows, according to the author, that only the overthrow of capitalism can avert climate change.

The book is full of words and phrases that only Marxists use, such as ‘structural crisis’, ‘surplus value’, ‘historical process’, ‘commodity fetishism’, ‘primitive accumulation’, ‘subsumption of labour’, ‘property relations’ and even ‘bourgeois property relations’. The author appears to have a checklist of ideas from Das Kap and to be ticking them off one by one.

I should have guessed from its title that it would be something like this, in which case I wouldn’t have bought it. If you are tempted to buy it for the same reason as I was you now know everything you need to know about it and I will forgive you if you don’t read any further.

Read more

What’s happening with Swansea Bay tidal lagoon?

Am I the only person who’s bemused about what’s happening to the Swansea Bay tidal lagoon? It looks like precisely nothing, though it would be just my luck for a deal to be announced five minutes after I post this article. If that happens, then don’t bother reading the rest!

As far back as July the FT reported that the project’s investors were warning that the delay in making a decision was putting the project at risk. According to Wales Online, a bunch of Swansea councillors met with Secretary of State for Business, Energy and Industrial Strategy Greg Clark on 30 October to urge him to speed things up, but two weeks later there have still been no announcements about what is happening. I wondered whether an announcement might have been made at the recent International Tidal Energy Summit earlier this week, but there’s still no news.

I don’t understand why the government couldn’t have given it a definitive unambiguous yes or no several years ago. But I have a theory, and here it is.

Read more