Post #2454877

2026-05-08 15:04 UTC

@simontatham@hachyderm.io @pieter@mathstodon.xyz Yes, that's clearly the case! The GPU implementation is necessarily a numerical approximation of an idealized algorithm that would produce perfect information in a computational model with real numbers. Finite precision means that some samples close to the border of the fractal will accidentally be mis-classified, giving you incorrect or missing tiles. And I don't think you even have to go very far from the origin to see that (in fact, I'm hiding some of those errors by choosing a starting translation that avoids them). In principle I think you can implement the whole algorithm with exact arithmetic in something like the rational numbers extended by sqrt(3) and sqrt(5). In that case you'd need bignums, you'd definitely be on the CPU and not the GPU, and it would be slow, but the only true limit would be your computer's memory.

Replies (2)

@simontatham@hachyderm.io 2026-05-08 15:46

@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.

Open ##2454878
@csk@mathstodon.xyz 2026-05-08 16:19

@simontatham@hachyderm.io @pieter@mathstodon.xyz Reflecting on this further, I suppose it's more accurate to say that the algorithm emphatically *does* require constant time per pixel, but that it's sometimes wrong. That's just your basic computational trade-off; for some applications of hat tilings (whatever those may be), it's perfectly adequate and perhaps even desirable.

Open ##2454883