Summer of Math Exposition

So, wouldn’t it be funny if (11, 8, 19) wasn’t actually the best triplet!? And in fact, it isn’t! It’s probably (11, 5, 12), but—to be fair—that might be just marginally better.

Why?

holy, you are the one who created Pikuniku??? I AM A BIG FAN OF THE GAME!!!

hahaha, enough of chitchat. let’s focus on the article you’ve submitted

my main complaint about the article is that it is so damn long! like, i have to spend 2 days digesting it… but for this event (and i think for general “math blog”, if you don’t wanna scare the readers so they ran away), a single post should be around 10-20min digestible size, imho

here’s a breakdown by your “parts”:

part 1 → Marsaglia’s

nitpick: the correction of typo where you show two C++ codes side-by-side, i think it would be clearer to highlight with “word-diff”. alternatively, just say that he forgot to “xor-assigned” ^= on the 2nd statement

But why did Marsaglia himself recommend shifting by 13, 17, and 5 bits? Why not 42, 67, and 1729?

personally, i’d write those number in a 3-tuple style, e.g., (13,17,5). that’ll allow 2nd sentence to be longer while retaining readability: “Why not (0,0,0), (1,31,16), or (42,67,1729)”. this also helps hinting that (42,67,1729) is not special. it just some failed example --- the point is, if you gonna show example as a part of the narration, don’t show only one of them, show a few

also, your (42,67,1729) is cute (those are meme numbers, aren’t they?), but the lack of visual example of this triplet makes it awkward. especially, when you formally show three other fails triplets.

nitpick: i also don’t think you need to mention fast inverse square root. given the length of the article rightnow, that’s too much of a detour

you said (13,17,5) is special because it’s a maximal triplet. but the next sentence you said there’s 162 (triplet?) that also generates all 32-bit numbers. so (13,17,5) is not special, after all???

part 1 → finding triplets

this feels like an incomplete subsection. i get that the “So how to compute? Well, two clever tricks… [ END_OF_SUBSECTION ]” intended as a hook to parts 2-3, but i don’t think this structure works… more on this at the end of the comment

part 2

yep we can see that the xorshift can be expressed as a matrix multiplication. but we must work over GF(2), not over reals nor integers. i think this is a crucial detail that should be highlighted prominently

part 2 → xorshift

nitpick: in the matrix notation, use latex’s \vdots and \ddots, not only \dots. furthermore, don’t use \dots for every “dot dot dot” entries, just use them sparingly to improve readability.

part 3 → order test

i think after equation (13), you should show another numbered equation for T^p = I too. that’s an important equation, not just leave it buried under a paragraph ”…, then T^p is the identity matrix!” this will help readers reading it in a first-pass scanning-mode and recognizing/recalling the importance of it

also, from a com-sci viewpoint, we instinctively knew that we can just do the famous exponentiating by squaring to see if T^p = I. i think this is worth mentioning right here (within this subsection or directly in the next new subsection)

nitpick: why use p in the T^p = I? normally, for ppl working in number theory, p is for prime number. maybe use the generic k instead?

part 3 → maximal order test

this subsection is the most delightful subsection in the entire article. this is where it finally feels like we’re doing serious number theory rather than tinkering and speculating

part 4-5

honestly, i don’t think we need this stuff here. the first 3 parts already capture the “heart” of the xorshift: the “premise” behind your hook (13,17,5). those parts already contain considerably dense technical material, and the article is already very long up to this point

i think parts 4-5 should be split into 1-2 articles of their own

part 6-7

this should be combined into one section: something like “conclusion” or “discussion”

testing for randomness is the whole next level of difficult topic. this alone could span like 20 posts. so if you gonna make it this short (basically “just trust dieharder”), then only mentioned it briefly that the generator is bad. don’t subsectioning it because that’ll make readers expect on the testing details

the strength of this algorithm is speed and simplicity: tiny state, cheap native-silicon xor, unlike the insane Mersenne twister

on content structure and ordering

i think the structure should be something like this instead:

• section 1: what is xorshift
  • algorithm simplicity with only 3 constants
  • but not all triplets are good: example of failed triplets
  • some good triplets
• section 2: how to be sure a good triplet generates all 32-bit
  • infeasible to brute-force
  • representing xorshift via lin-alg
  • T^p = I
  • caution when p is composite (speaking of which, why use p in the first place???)
  • enumerate all (or a selective few) good triplets
  • 64-bit and 128-bit versions of the algorithm
• section 4: closing mark
  • it’s good at: speed, small, simple
  • it’s okay at: statistical randomness
  • it’s bad at: cryptographic purpose

nice to meet you. i wish you good luck in this event :)

P.S. i just noticed that your “abstract” is talking abt (23,17,26) which is the xorshift128+, not the simpler (13,17,5) original xorshift32… this is quite a double-edged sword:

• if you only talk abt the original 32-bit version, then your did not really answer the question posted in the abstract
• if you only talk abt the “improved” 128-bit version, then the whole article will too complicated, even for the example (and you lose historical narrative)
• if you try to talk abt both of them, you risk making the article too long (like it is now) for educational purpose, i think the whole article should stick with the 32-bit version. then spend no more than 2 subsections mentioning the extension to 128-bit around the end… otherwise maybe just use (13,17,5) in the abstract

I liked your connection to different fields.

A bit long and technical, but overall very well written and presented!

Great article, although parts 4 and 5 seemed a little disconnected from the rest. I also would’ve liked to see more details in the “Testing” section showing why the numbers actually appear random, since just because a function has a maximal period doesn’t mean the outputs appear to be random.

The inline explanations of concepts was a very nice touch and made for a much easier read. It would have been nice to see the B-M algorithm implemented or do some kind of computational experiment. Additionally, I would challenge the claim that matrix multiplication here is O(n^2) as the matrices you are working with are very sparse and structured, and n may be not very large relatively speaking.

Very interesting but the article would’ve been more engaging with some interactivity

chalkboard visualisation is cute, accessible topic well explained

This was a very interesting blog post on the generation of random numbers. I was always wondering how that works and it was cool to see how simple algorithms for random number generation can look like.

I really enjoyed the visual explanation of the three line algorithm in the Marsaglia’s Xorshift section, since it really clarified what the code does. It was also interesting to have the three different interpretations (programmatic, linear algebra, field theory) of the xorshift. However, at some point I also thought that it might be too much information, especially when I read the section on Krylov spaces I lost a bit track. Mainly because I am not that familiar with field theory and this topic comes up far down in the blog post. So I wonder if the blog post could have been made more concise, and the field theory section could have been presented in the end as an appendix for the interested reader.

After reading the post I was also wondering if there is a clever way to find the maximal triplet $(a,b,c)$. It seems like given $a$, $b$, and $c$ we can test if the triplet is maximal, but we still have to iterate over all possible combinations of these values. It is not all possible combinations, since it was stated that if a<c and (a,b,c) is maximal then (c,b,a) is also maximal, but it would have been interesting to learn more about why this is the case.

Nice read on the use case of the linear algebra to try to determine why a certain generator has good properties that it should. Most of the existing illustrations do a good job to indicate how the algorithm works in practice. I think there are a few leaps of logic and jargon that could do with better explanation as it is not clear how one follows from another (eg. what does the N=256 scatter plot represent. Is this the maximal triplet plotted for a 256 bit system? It’s also not clear where the claim of 550 triplets is coming from in terms of the derived work here. A Frobenius companion matrix isn’t defined for those not in algebra)

This was great, very interesting read ! I never knew, how computers get random numbers. Always just called random() or something and didn’t worry about it. I enjoyed reading through everything up to part 5. From there it was a quite a bit more difficult. I found myself looking up a lot of terms and using AI to explain some of the maths. For example, I don’t think that the first section of part 5 ever makes the mathematical claim . From what I’ve gathered the idea is that if xorshift generator has maximal period <=> the characteristic polynomial of T is primitive, but it’s never said explicitly. Then the Frobenius Companion Matrices section was quite confusing. I wasn’t sure what’s the point at all. How do we get a maximal triple from the matrix ? I don’t want to nit pick it, the article was long and I admit, abstract algebra isn’t my strong suit.

In any case, the first half is self contained and would be a great entry on it’s own I think, so I’m going to go high with the ranking.

This was a fun read! My first proper introduction with psuedo-random generators, and I learnt a lot. Finally understand how seeding makes a “random” generator print the same sequence!

I think this was a clear and lucid description.

The visuals were useful, I liked how you used the textures to demonstrate the “randomness” of triples or the lack of “randomness” of other triples - though I can imagine that this is probably not a rigorous or correct way to prove “randomness”, but is a really good exposition device to show your point!

The only constructive criticism I have is to be more detailed in regards to how you get to some assertions, claims, etc. I get that the audience is graduate students, but there are times where I’ll have to kind of work out on pen and paper why what you’re asserting is true. Here are some examples of where I as a reader had doubts, that I wouldn’t have had if you had additional comments for those claims:

1. The textures in the beginning: Just like you had other dropdowns that dive into more details on topics, I think a dropdown on how you constructed this texture could be useful. How exactly do you get that image for a sequence? That could’ve made the point that those tree triples are generating seemingly random sequences even more clearer

2. You mention “there are only 162 that generates all 32-bit numbers. Well, all except zero, which xorshifts can never generate anyway.” An explanation of what is special about 0 that an XOR triple wouldn’t be able to generate it would be useful. Of course one can parse what happens if x is 0 by going through the algorithm - but spelling it out does not hurt. Similarly why are total triples are (32-1)^3 and not 32^3?

3. An example of the left and right shift matrices actually shifting a bitvector left/right would’ve been useful for people for whom that point was not immediately obvious.

4. Maximal order test section: I found the flowchart that describes the algorithm to find if a given triplet is maximal hard to follow on the initial read. For example, it was not immediately clear to me that p = 2^n-1, and pi is a prime factor of p. Why is it that just checking checking if T^{p/pi} != Identity matrix for all pi is sufficient instead of doing this for all divisors? Things like this could’ve been spelled out more and would’ve made this even clearer!