something that's been bouncing around in my head for a few days: I wonder if any of the common permuted congruential generators (PCGs) have the property that for any finite sequence of unique integers there is always a set of parameters (seed, multiplier, increment, modulus, shift amount, rotation amount) that produces that sequence.
I know it's not the case for LCGs, but the permutation step changes the details quite a bit.
if PCGs can create any arbitrary unique sequence of integers, presumably finding the parameter set for a given sequence is computationally difficult, because if it wasn't I'm sure someone would have leveraged this for compression.
@gsuberland
I remember someone doing something similar with pi, as it's assumed (though not proven as far as I know) pi contains all possible sequences. It was called pi fs (file system) or something similar.
It was more a joke than anything else since it'd be terribly inefficient.
@koantig yeah, similar idea, except instead of brute force searching for n-bit sequences in pi whose positions could be represented as a p-bit integer (p<n to obtain a compression ratio), you're finding arbitrary parameters to generate the required sequence as a whole.
example: you could take some data, compress it with some existing scheme to reduce the chances of duplicate 64-bit values in the set, expand the values by however many bits it takes to "stuff" them with prefixes to make every value unique, then find PCG parameters to fit that sequence.
decompression is then simple: generate the PCG values, mask off the prefixes, concatenate, and undo the underlying compression.
the pi approach theoretically has a smaller lower bound on the number of required bits to store the index and length, but in practice it is unbounded. the PCG approach has fixed storage size for its parameters, regardless of data.
but the pi approach is required to be brute force with no upper bound on time. whereas the PCG approach, if the maths is sound, has the potential to be solvable with more concrete bounds, even if it is computationally difficult.
@rotopenguin the other side of it is that the time complexity for searching pi grows exponentially with the size of the sequence. short of some earth-shattering discovery, we probably can't accelerate that at all. there aren't any variables we can tweak.
with the PCG approach, though, we've got a lot more freedom to alter how the sequence generation works, and the whole thing is less of a mystery in general.
@rotopenguin if we bounded ourselves to unique sequences of 16-bit values, for example, the naive search space for the most basic variant (variable multiplier, increment, and xorshift amount; constant modulus and rotation amount) would be at most 67 bits. that is assuming the underlying assumption that all sequences are possible to generate from a PCG holds, which is unclear.
Add comment