← Feed
@simontatham@hachyderm.io
Post #2454876
2026-05-08 14:48 UTC
@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!
Replies (1)
-
@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.
Open ##2454877