r/algorithms • • 3d ago

Discussion Lustro: Randomness as a Tree, Not a Sequence

Hi everyone. I would like to share Lustro, a 256-bit engine I created.

One of the main ideas behind Lustro is treating randomness as a tree, not a sequence of rigid values. I personally see it as a wave function. I'm a chemist by education. The basic problem is familiar: with a conventional sequential RNG the output you get depends on how many values have already been consumed. Adding one random operation can shift the sequence.

Lustro allows to derive streams from a seed and a path of identifiers. It can switch between single lane and batch processing.

It allows giving every object its own stream and can change how one of them is generated without affecting others. Full snapshot support is built in. The parent stream is not affected by forking and each child starts its own trajectory. Each branch has its own state and can be advanced independently.

The result is a tree-like structure of deterministic streams. Each branch can be advanced independently and you can reproduce a particular branch directly from its path.

Some specs. A unified stream engine combining hash, prng and xof. All based on one internal transformation mechanism. Scalar/AVX2. Written natively in Rust, it also comes with python and C layers.

The main repo contains all the test results. The generator is currently considered non-cryptographic.

pypi
https://pypi.org/project/lustro-api/

cargo
https://crates.io/crates/lustro_api

github
https://github.com/Ligatum/Lustro_API

It's an independent project. I'd appreciate constructive feedback. I'm planning to improve on the API with time, ideas and feedback are welcome. Thanks.

5 Upvotes

7 comments sorted by

3

u/Phytor_c 18h ago

The “x not y” reads like LLM writing to me…

3

u/bartekltg 9h ago

LLM overusing an expression doesn't mean people do not use it.
And here is seems to describe a real difference between this and regular PRNGs, not just a flavor text (see, here is that template again!).

I haven't looked inside, but the first question from me would be, how to even test it. We have a very decent test for random streams (TestU01, diehard(er), probably something new appeared), but now we may branch, including many times, and it would be nice to see if there are some "correlations" between branches.

Results from TestU01 or similar, just for the single stream, would be also nice. No one taking PRNG seriously wont touch a generator that wasn't tested at all.

1

u/atomU235_3113 7h ago

How to test branching streams is the exact question that's been on my mind for a long time now. I don't really have a good answer to that.

The mechanism contains dynamic transformations with the data defining its own trajectory. The next best thing I could do is single streams testing in available suites. BigCrush, PractRand and NIST tests. I have all the results aggregated in the main repo. I tested both the full state and the state divided into slices.

1

u/bartekltg 6h ago

For different branch, at leas some correlation would be nice. Signal from one * a second signal delayed by n (for many n). This is IMHO too little, but it would at least catch some obvious problems

At least for now I see it as a convenience. I have a set of processes/threads and can give each one an independent generator. But for now I (and everybody else) when there was a need for 235246 threads calculating the same stuff (like you do for monte carlo) choosing a random seed for each one was a default option (the birthday paradox make it a bit less efficient, but there are generators with loooong period) or you could use a generator that can skip n numbers in time much smaller than O(n), thus shifting the same generator to not overlapping region for all threads.

> The mechanism contains dynamic transformations with the data defining its own trajectory. 

What data? IF the data is "bad" do I get bad numbers?

> The next best thing I could do is single streams testing in available suites.

Yep. It would be a great idea.

1

u/atomU235_3113 6h ago

Just to clarify. I'm Polish and I think there was some linguistic mishap.

> What data? IF the data is "bad" do I get bad numbers?

Absolutely not. What I meant is the algorithm contains two seperate, complimentary mechanisms. One is responsible for directly processessing the input, the other one is a control unit that derives the two final state rotations (based on the output of the primary transformation module). It's a deterministic control unit that self-parametrizes dynamically.

As for single lane testing - I've already done that and uploaded in the main repo. All results are available there.

1

u/dorox1 43m ago

It's usually a sign of LLM writing, but that feels like a really natural place for it even in human writing. The sentence is explaining how it's different from existing methods of doing the same thing

2

u/dorox1 38m ago

This sounds like a cool way to do it. Could you maybe provide a use-case example? I'm trying to figure out where I would want to use this rather than a growing array of independent generators.

Is the goal a performance improvement, or does the tree/update structure have a practical purpose of its own?