News for hackers. Stuff that matters.

A comment on Every UUID Dot Com. Parent comment

Re:Every UUID Dot Com by thaumasiotes on Friday December 06, 2024 @08:06PM (#42346312)
> If we didn’t care about generating valid UUID v4s, we could just generate 2^128 numbers, scramble them, convert the resulting bits into a hex string, and intersperse some dashes.

You can do that anyway. You'd only need the twiddling if you wanted to limit the amount of numbers you generate to 2^122. Since you're willing to generate 128 bits:

    // get encrypted value
    uint128 bits = encipher(seed);
    // clear zero bits
    bits &= 0xFFFFFFFF FFFF 4FFF BFFFFFFFFFFF; // instead of 4 and B, you can use 0 and 3
    // set one bits
    bits |= 0x00000000 0000 4000 800000000000; // these have to be 4 and 8
But since you're generating more numbers than you need, you're going to end up with 64 copies of each UUID in your final stream.
[ Parent | on HN ]
Re:Every UUID Dot Com by eieio on Friday December 06, 2024 @10:42PM (#42347072)
I considered this, but I'd just be so unsatisfied if I finished scrolling through all 2^128 rows and realized I'd seen some duplicates!
[ Parent | on HN ]
Re:Every UUID Dot Com by thaumasiotes on Saturday December 07, 2024 @12:53AM (#42347595)
I liked the approach movpasd suggested: https://news.ycombinator.com/item?id=42346076

With a linear algebra library, you can guarantee that you've found the next, or the previous, match in sequence. I don't know what the state of the art is for fast linear algebra in javascript, though.

(The matrix approach also has the advantage that, when your full-text search problem has 2^115 solutions, you can compute the one you want, the next one after some index, without having to compute them all.)

[ Parent | on HN ]
Re:Every UUID Dot Com by eieio on Saturday December 07, 2024 @11:12AM (#42350660)
I need to learn more linear to be able to appreciate this! Gonna do some reading.

very fun to have received so many pointers here, hopefully I'll be able to do a follow up blog once I've finally let people find all the good UUIDs

[ Parent | on HN ]