Simon Tatham

RE: https://hachyderm.io/@simontatham/117201594980991062 #Zoom 7.2 appears to have fixed this unwanted paste request issue.

What's the right way to generate a floating-point number representing a sample of a uniformly random variable in the range [0,1]? You might think: choose the exponent to be 2⁻¹ with probability 1/2, 2⁻² with probability 1/4, etc (with some fudge when the range runs out). And then, once you've chosen an exponent, choose uniformly at random from the mantissas. Wrong! The #IEEE754 ethos is to calculate the mathematically perfect result, and then round that to the nearest representable number. So you must choose each floating-point number x with probability in proportion to its rounding 'catchment area': the range of real numbers above and below x that will round to x. Well, isn't that what I just said? No, it isn't – because powers of 2, at the boundary between two exponents, have a catchment area half as big on the left as on the right. So you must choose _most_ numbers with probability 2⁻ⁿ where n varies with the exponent, except that powers of 2 are chosen with probability 2⁻ⁿ + 2⁻ⁿ⁺¹. Arrgh!

I noticed today that an update to the #Linux #Zoom client has made it start proactively reading _everything_ written to the X11 clipboard. If you keep interesting secrets in your clipboard – particularly, if a password manager uses it as a means of getting the password to where it needs to be – this might be a thing you need to know about!

A couple of weeks ago I showed a preview of a new mode for Mines, in my puzzle collection. I'm pleased to say that the new Mines is now completed and live! You can now play Minesweeper on a wide range of tilings in your browser https://www.chiark.greenend.org.uk/~sgtatham/puzzles/js/mines.html or download a desktop version from the parent page which supports the same set of grids. As well as the support for lots of grid types, there's also a new user preference (off by default) to make it easier to play on them. When you click on a clue square to potentially clear around it, the existing flags adjacent to the square light up, to make it easier to count them and work out how many more mines you're still expecting. Particularly useful in the hat tiling, where it's easy to mistake exactly what is adjacent to what! I expect different people will prefer different grids. Personally I think the triangular grid is particularly tricky and puzzly; the hexagonal honeycomb makes a gentle introduction; the Cairo, Floret and Kites tilings are a nice set in between those extremes; and of course the aperiodic tilings are there to keep you on your toes and ready for anything. Many thanks to Anders Höglund for this excellent piece of work.

Always a good moment when you get to type, incredulously, git commit -am 'OMG WTF IT ACTUALLY WORKED?!'

Just found a machine in my house that was still running Debian 11, which went out of support recently. Upgraded it to 12, and for good measure, straight to 13 (trixie). The best thing about this is that I'm no longer running any of the three consecutive releases that begin with b. No more struggling to remember which of buster, bullseye and bookworm is older and which is newer!

A further announcement related to #PuTTY: we are retiring the 'putty-announce' mailing list for release announcements. Today's release, 0.85, was announced by email to that list, but it's the last one that we will announce that way. Running a mailing list always involved a lot of work dealing with bounces from defunct addresses and email from ticketing systems that people had subscribed to the list. But now we've been starting to find that we're accused of spam, because people will leave a company, forget to unsubscribe from putty-announce, and after a few months, their ex-employer will turn their old address into a spam trap. As an alternative announcement mechanism, I've set up an RSS feed. See https://www.chiark.greenend.org.uk/~sgtatham/putty/updates.html (Of course, anyone reading this toot is probably receiving release announcements anyway via my Mastodon account! But if you were also using the mailing list, please spread the word that it's going away.)

Bah, why isn't the 🔍 emoji at U+221B?

New quasi-blog post: "Analysing 2048 on a 3×3 board" https://www.chiark.greenend.org.uk/~sgtatham/quasiblog/small2048/ A rather late writeup of a project I did some years ago, to scale down the puzzle game 2048 to a smaller board, allowing it to be analysed exhaustively, and learn from the results. Includes a Javascript implementation inline in the article, and a second much more evil version that chooses the tile drops maliciously.

Sneak preview of a not-yet-production-quality contribution to Mines. I expected this particular mode to be brain-meltingly confusing, and it is, but not for quite the reasons I'd guessed.

But a thing I was particularly pleased with, and with hindsight I still am: my mother found it easy to use. This was a surprise because I hadn't deliberately made it that way! Usability by people other than me wasn't much on my radar yet, at that age. But, by luck, I made a good UI choice, which was to write all the menus so that they could be read as English sentences. So a user wouldn't need to learn any of the various complicated 'visual grammars' that sophisticated UIs use to signal the available keystrokes, mouse actions etc. They'd only need to read an English sentence telling you what options you have and what key to press to do each one, then pick one of them, and press that key. The online help screens had the same feature: instead of containing obscure notations like ^B, they said "Press Ctrl with: B for bold, ...", and at the bottom, the all-important prompt for what to do next: "Now press any key to exit Help". 3/3

Around 2002, at work, I was involved in implementing support for Japanese character sets in an embedded library. A colleague from our Japanese office visited, and we worked together on it for about a week. Before she left, she gave me a small present in thanks, labelled "Japanese Luck Bringer". Two years later, it fell off a high shelf on to my head.

Wordbench was pure symbiosisware: its only features were ones that I wanted, or someone else in my family wanted. Nothing else. Just look at this collection of printer drivers! These are _exactly_ the printers that I or my family owned during the lifetime of the software. 2/3

Firefox, in some unwelcome new feature: "Shake your device to summarise this page in seconds" Me:

@robinhouston@mathstodon.xyz reminds me of a friend who once asked Wolfram Alpha for a graph of "tan tan x", and got a graph of tan x, drawn in a light brown colour. I think they fixed it, though. (Disappointingly.)

I wonder, actually, if the _very simplest_ problem that demands recursion is just generating a Cartesian product of variable arity. If I have a function taking 3 arguments, each taken from a finite set, and I want to call it with all possible combinations of arguments, then I can write three nested for loops: for a in values: for b in values: for c in values: f(a, b, c) But this only works if the number of arguments is known at the time I write the code. If f takes a single list argument instead of three separate values, and I need to specify the length of the list at run time, then the only sensible thing to do is write a recursive function, containing _one_ of those for loops; give it a parameter to control the recursion depth, and at the deepest level it calls f with the list it built up. Of course you _can_ write some fiddly loop that iterates on a partial list, sometimes appending a new item and sometimes deleting the last one, calling f whenever the list gets full and terminating when it becomes empty. But that's in the category of "simulate recursion in a way that's less obvious than just doing the recursion". And you _could_ do breadth-first search, keeping a queue of partial lists. But then your memory usage becomes Θ(2^n) instead of Θ(n).

(Brought to you by a conversation yesterday about 'ifconfig' and 'route' being deprecated in favour of 'ip'. So not very topical. But the point about trust erosion was a thought I hadn't had before, and retrospectively realised I was feeling it myself. And I think it applies more widely than Linux network management utilities.)

The best example I've ever managed to come up with is the search problem in the game of Boggle: find a path through a grid of letters, never revisiting a square, that spells out a word. You can simplify the problem by giving a _specific_ word as input rather than a whole dictionary: "is there any path in this grid that spells BANANA?" It's a bit awkward because "never revisit a square" means you have to maintain a set of disallowed squares, either passing a modified copy to each recursive call or modifying a single copy in place. But unfortunately that property is also what makes the problem need recursion in the first place: if you take away that rule, it becomes a much simpler BFS problem – in particular, polynomial time, whereas the proper Boggle search problem is NP-complete. Boggle is in my second category: it's not _impossible_ to solve it non-recursively, but the most obvious alternative technique is breadth-first search, and the "never revisit a square" rule means each entry in the BFS queue has to contain a set of squares, so that lots of queue entries can share the same (grid square, position in word) values and still need to be kept separate. So you can see that there's a memory-use disadvantage: the recursive solution considers all the same cases, but keeps far fewer of them in memory at a time.

I have a Zoom meeting at 10:00, in one minute's time (as I type this). Zoom is reporting that the meeting is in 2 minutes. Outlook already says "now". When did timekeeping on computers become this difficult?

The thing about writing "I've never got round to debugging this" in a Mastodon post is that then you feel silly, and get round to debugging it. (Result!) The reason why VLC was failing to inhibit my laptop screensaver, it appears, is because I was accidentally running two of them. light-locker was answering the D-Bus org.freedesktop.ScreenSaver Inhibit request and agreeing to not blank the screen. And then xfce4-screensaver, which hadn't got the memo, was blanking the screen anyway.

I went to a school run by Quakers. I'm not a Quaker and never have been, but the school seemed like a good choice to my parents for other reasons. A valuable thing I learned from Quaker silent worship meetings is the skill of keeping my mind occupied for half an hour or an hour at a time without external help. I've been grateful for that any number of times in adulthood when, for example, I forgot to bring a book with me on a train journey. And why do I happen to mention this now? Oh, er, no reason. (D'oh.)

Sauron Had only got One Ring Shelob Sat down on someone's Sting The Witchking Has stopped his bitching And no-one knows if The Balrog Had wings. (Gondor Army marching song, Fourth Age, apocryphal)

This month I've been using xlogo as a workaround for the fact that VLC is failing to inhibit my laptop's screensaver, so that if I connect to a TV to show a video, there's a risk of it blanking part way through. $ while xlogo -geometry 2000x1000; do sleep 240; done Now every 4 minutes a huge xlogo pops up (and my WM placement algorithm reliably puts it on the built-in monitor, because the other one is full of VLC). So I use the mouse to dismiss it, and that _does_ inhibit the screensaver. (One of these days I'll get round to actually _debugging_ the screensaver situation, but that's a faff, because every time you try something you have to wait 5 minutes to find out if it worked.)

Sometimes the only hint you need to solve a puzzle is that it can be solved without a hint. Last week a colleague and I were staring in puzzlement at something weird in a terminal window. After 30 seconds I said "Oh! I've worked out why that happens!". Five seconds later, she got it too, because _now_ she knew that it was possible to get the answer without going off to do an hour of research, and that narrowed the search space of what the answer could possibly be. And this week, I was puzzled by a compiler error message referring to a particular C++ header, so I went and looked in (one implementation of) that header to see what it did. I found it did nothing interesting, or magic, or tied in to the internals of the compiler, at all. And that was enough to make me figure out what was going on with the error message – again, because there just weren't that many options left. When it happens, it feels like one of those deliberate puzzles in which Paul says "Ah, now I know what the numbers are!" and Sophie replies "Ah, in that case, so do I!" Only somehow reality managed to create the same effect by accident.

In programming languages with exceptions, there is a fundamental divide between • those in which you're tempted to call an exception type "Tantrum" • those in which you're tempted to call an exception type "Eyebrow".

If I do, then perhaps I should also get round to making the alias 'got doff'.

#TIL that you can turn off the newfangled annoying "download stuff from debuginfod.ubuntu.com?" prompt every time #gdb runs, by unsetting DEBUGINFOD_URLS in the environment. That must have been annoying me ever since Ubuntu 24.04 came out, and I just sighed and said no to the prompt every time. But this evening a program of mine hung mysteriously on shutdown, and on investigation that turned out to be because Leak Sanitiser had invoked llvm-symbolizer to print backtraces, which defaults to trying to talk to the Ubuntu debuginfod servers, which currently seems to be ill and not answering questions. And llvm-symbolizer's man page mentioned that environment variable, which seems to be what triggers gdb to offer the same feature. If I'd known that two years ago I could have avoided two years of that annoying gdb prompt!

@csk@mathstodon.xyz @pieter@mathstodon.xyz with my computer-arithmetic hat on, I want to quibble with the 'constant work' and 'never run out of information' parts. I think those things would be true if your GPU had _true real numbers_ as a data type. But all it has is finitely large floating-point approximations. And this whole technique relies on the translation symmetry lattices of the grid points and the fractal pattern being irrational multiples of each other. That irrational multiplier will be imperfectly represented in floating point, so sooner or later as you pan away from the origin you'll reach a point where rounding errors start to affect the results. (If nothing else, from first principles, even within a single hat tiling of the whole plane, the non-periodicity implies that every tile in the plane must be distinguishable, and therefore there's no way a finite amount of information could even tell you where you are within _that_ hat tiling – and that's before considering the uncountable number of distinct tilings of the whole plane.) But perhaps you have to get 2^52 tiles away from the origin before this becomes a problem!

@andrewducker@mastodon.scot INDEPENDENT GREEN VOICE is an anagram of "GREEN VOTE DENIED!" "NICE!" "NP."

@minego@pdx.social cancelling a search with backspace: I think I initially discovered it by accident. Changed my mind about what I wanted to search for; held down backspace to delete everything I'd already typed; if you hold it down for one repeat too long, you cancel the search operation completely. Then once you've done it by accident, you know it's a thing you can do on purpose too. I agree that it wouldn't be the obvious thing you'd try as a cancel button. Esc is a more obvious choice, or ^C on general Unix grounds, or ^G on emacs grounds (less is more vi-like, but it'd be worth a try). But it is at least somewhat discoverable because of the possibility of that accident.

@csk@mathstodon.xyz @pieter@mathstodon.xyz ah, the floating-point analogue of the distinction between Monte Carlo and Las Vegas algorithms! (Though I never liked those terms, because I have no good mnemonic for which is which.)

@losttourist@social.chatty.monster by sheer coincidence, half an hour after I posted that, an ice cream van drove down my street playing the same tune. So I have the same problem, but not quite for the reason I'd expected!

@erisceleste@tech.lgbt @thephd@pony.social unfortunately, nesting Generics brings us back to the original problem, that even the unselected branches have to be semantically valid, so that if you want to accept types (T,T), (T,U), and (U,T), but not (U,U), then you're in trouble, because the sub-Generic in the (U,x) branch which has no case for x=U will fail when you pass types (T,U) to select the other branch. I suppose it's true that if it's feasible to write each branch of the doubly-switched Generic in the form of a function, then you can use the typeof trick to switch between those functions, in the good old-fashioned style of only selecting the function name: inline void foo_ii(int a, int b) { /* ... */ } inline void foo_ip(int a, char *b) { /* ... */ } inline void foo_pi(char *a, int b) { /* ... */ } # define foo(x, y) _Generic( (void (*)(typeof(x), typeof(y)))NULL, void (*)(int, int): foo_ii, void (*)(int, char *): foo_ip, void (*)(char *, int): foo_pi) (x, y) and then you do get both a non-orthogonal set of type pairs, and an identifier for each of the two things at the point of actually using them (in the body of each function).

@thephd@pony.social Out of interest, what's your best recommendation for writing a _Generic that switches on two of its operand types, if the choices aren't independent and there's no default clause? In my 2023 article I mentioned the idea of using a function type to stand in for a type tuple, via GNU typeof, along the lines of _Generic((void (*)(__typeof(x), __typeof(y)))NULL, void (*)(int, int) : "got two ints", void (*)(int, char *) : "got an int and a string", void (*)(char *, int) : "got a string and an int") Now that typeof is standard in C23, that idea doesn't depend on GNU extensions any more. And it's certainly an improvement on the horrible system of integer type ids I suggested as a workaround at the time. But do you have any even better ideas? Ideally, a way to combine it with the N3888 identifiers, so as to be able to get both good features at once – the ability to switch on both types, _and_ the ability to refer to both values inside the branch via correctly typed identifiers?

@tiotasram@kolektiva.social @csk@mathstodon.xyz @pieter@mathstodon.xyz generating incrementally as the user explores: yes, indeed, I've had that thought too. As you say, for _my_ ultimate application of generating a puzzle game, or the much more obvious one of just generating a patch of tiles for a pretty picture, there's no need to remember your state and extend it later, but you could perfectly well do that if you wanted to! On generating a tiling from the limiting distribution: since I wrote that, I've realised that phrase is ambiguous in some cases. If not all tile types have the same area, do you take the limiting distribution to be the distribution of _tiles_, or of _area_? Put another way, are we taking the limit as patch size → ∞ of the operation "pick a tile uniformly at random from this finite patch", or "pick a _point_ uniformly at random in the patch and see which tile it falls in?" For hats and Spectres, this doesn't matter, because of course the whole point is that all the tiles are the same. But for handling the 'legacy' aperiodic tilings – Penrose, Ammann-Beenker and others – it does matter!

@csk@mathstodon.xyz @pieter@mathstodon.xyz "no lattice points lie on the boundary of the fractal" – ah, I expect that will be the loophole that the singular patterns sneak through.

@csk@mathstodon.xyz @pieter@mathstodon.xyz I certainly agree with your second paragraph – with bignums and a finite-degree field extension you can do all of this in exact arithmetic. "And I don't think you even have to go very far from the origin to see that" – that's a shame! I was hoping that the hat tiling being based on kites would help there, because you can separately calculate where you are in a kite and where that kite is in the tiling, so the quality of the FP approximation might degrade only per kite and not per pixel. I'd expect it to be harder in a Spectre version of this idea, where there's no discrete underlying grid. What's interesting to _me_, naturally, is how the two systems of identifying a tiling match up to each other. I represent a specific tiling via a sequence of supertile types and the relationship between each and its subtile; this technique represents one via a point in the plane. Translating between the two must be possible, but is probably also a royal pain. And I have to guess it won't be quite possible in some of the (alas, most interesting) edge cases, like the singular patterns. If it's anything like the pentagrid system for Penrose tilings, there won't be any real (x,y) value that _exactly_ represents a specific singular instance of the hat tiling. Instead, there will be an (x,y) value that represents the symmetric parts in common between more than one of them, and a full tiling that breaks the symmetry in a specific way can only be realised as the limiting tiling you obtain by approaching the singular point from a particular direction.

@thephd that looks cool! But I transcribed the initial example from my blog post into it, added identifiers that I'd have expected to fix the compile failure, and got some very strange error messages: https://godbolt.org/z/6o77aGWE9 "'foo' declared as a pointer to a reference of type 'const char &'"? That looks like a weirdly C++ish error message for a compiler in C mode. Unless C++-style references are coming in C2y and I haven't heard? But even if that were true, it's not obvious to me how I accidentally introduced one in this code example.

@thephd@pony.social so it is – my own godbolt link also works now, I guess because the compiler version updated under its feet. (Although that was confusing, because I re-checked my link this morning and it still failed, even though the "i" button for the compiler reported git commit 916de97c3dea18a469628e498a83162fa85e41ee, which is the same one it reports now and looked in your git repo as if it contained the fix. Presumably the compiler info and the actual results didn't update in sync.) Now I've looked more carefully at N3888, I see that existing _Generic is expected to return an lvalue if it can, which I'd never thought to try. I guess that's where the references came in? Your implementation converted the type to a reference internally so that it could be an lvalue if it escaped the _Generic? And somehow, when the type was a pointer, it accidentally became a pointer-to-ref instead of a ref-to-pointer.

@mjd@mathstodon.xyz @robinhouston@mathstodon.xyz I've definitely seen puzzles of that kind with the circles full of beads interlocking, though I couldn't name a brand or manufacturer – never owned one myself. But hexagons sound more unusual. Don't think I've ever seen one based on hexagons at all.

@garthy@social.linux.pizza those settings specify a "cyclic" mode, in which the top of the grid is considered to wrap round to the bottom. So that 2 clue is not just adjacent to the single closed cell shown in your picture, but also to some cells at the bottom of the grid. If you click on the 2 cell as if you were going to clear around it, it will show all the cell's closed neighbours temporarily.

@csk@mathstodon.xyz @tiotasram@kolektiva.social @pieter@mathstodon.xyz I think it only gets to reliable log time in the later articles. In that initial one I think the hat method is still log² in the worst case.

@csk@mathstodon.xyz @pieter@mathstodon.xyz … though thinking about it, that idea of "per kite and not per pixel" is nonsense, because in fact one surely rounds to the nearest point of the integer lattice that samples the fractal, which is neither of those. Posted before thinking.