0
$\begingroup$

So I am wondering about how to generate a subset $8^{10} \subset 8^{32}$ IDs. That is, there is a space of $8^{32}$ possible IDs, but I only want to generate $8^{10}$ of them right now. This shouldn't be too relevant, but just the numbers and scales are relevant: $8^{32}$ and $8^{10}$.

This can be encoded in an alphabet such as 12345678.

The problem is, you can't randomly generate $8^{10}$ ids that are 32 characters long using the 8 symbols 12345678 in a reasonable amount of time. So I'm trying to look to math for inspiration on how to simulate randomness and make this perform much faster.

What I've tried so far is basically the following. Given the total size of the number of IDs ($t = 8^{32}$), I want a subset ($w = 8^{10}$). I can do this by taking every nth item, which is obtained by $n = floor(t \div w)$. However, this results in sub-par data. It gives me stuff like this:

88888641528324675111111111111111
88888641517646645111111111111111
88888641487168615311111111111111
88888641476512565511111111111111
88888641465834535711111111111111
88888641455356485711111111111111
88888641444678456111111111111111
88888641434222426311111111111111
88888641423544376511111111111111
88888641412866346511111111111111
88888641382388316711111111111111
88888641371732267111111111111111
88888641361254237311111111111111
88888641348576187311111111111111
88888641338118157511111111111111
88888641327442127711111111111111
88888641316763878111111111111111

This doesn't appear random because all those "0's" from calculating $n$, which become the 1's above....

What would appear more random is something like this:

88888641528324675415283246754152
88888641517646645415176466454151
88888641487168615414871686154148
88888641476512565414765125654147
88888641465834535414658345354146
88888641455356485414553564854145
88888641444678456414446784564144
88888641434222426414342224264143
88888641423544376414235443764142
88888641412866346414128663464141
88888641382388316413823883164138
88888641371732267413717322674137
88888641361254237413612542374136
88888641348576187413485761874134
88888641338118157413381181574133
88888641327442127413274421274132
88888641316763878413167638784131

The reason for the 8's padding the beginning is because I'm generating them from the ending numbers of $8^{10}$ on down to the beginning, so it starts in the trillions or whatever. The numbers I generated above in the second example aren't ideal because I just copy/pasted the first few randomly-appearing numbers for each row, but the gist of it is that this sort of thing looks a lot more random.

What I'm wondering though is if there are any mathematical techniques to select out numbers from a large set (in this case $8^{10}$ out of $8^{32}$) such that it appears more random, and yet it is also guaranteed to provide unique and consistent results sort of like hashing. Perhaps it is some sort of noisy curve that is governed by some equation, where you can provide it $t = 8^{32}$ for the total amount, and $w = 8^{10}$ for the desired amount, and you can use it to, instead of having an $n$ which is static, maybe an $i$ which is plugged into a function and gives you back a specific number which, when taken as part of the final set of obtained numbers, appears random.

Wondering how to do something like this, some sort of theory or equation system that might help in solving this problem.

Also BTW, the characters 12345678 are just characters, they could also be $abcdefgh$ or any other set of 8 characters (or 10 characters if we had a system of 10 instead, etc.).

By "appears more random" anything that is better than the above will do, or where it is obvious that there is some sort of pattern to a layman. Basically trying to remove the thought that "hey there is a pattern here" for the non-math person. That would make it "look" random.

To modify the question a bit, it doesn't need to be random necessarily, it just needs not to appear like it is (a) incremental or (b) has a simple pattern like we selected all numbers with 10 ones at the end. It could instead be something like it selects some multiple of the current number to scramble the lower part of the number, or I don't know, stuff like that.

$\endgroup$
  • 1
    $\begingroup$ Would a linear congruential generator over a specified range you want do the trick? Seeding it in the same way would generate the same sequence of numbers. $\endgroup$ – Moo May 7 at 12:45
  • $\begingroup$ it really depends on what exactly you mean by "appears more random", but as a first approximation start with some sort of linear codes $\endgroup$ – user10354138 May 7 at 12:48
  • $\begingroup$ @Moo I am not familiar with those, taking a look, thank you. $\endgroup$ – Lokasa Mawati May 7 at 12:48
  • 1
    $\begingroup$ @LokasaMawati: Start with en.wikipedia.org/wiki/Linear_congruential_generator and an easy LCG with a very small period to see what is going on. $\endgroup$ – Moo May 7 at 12:54
  • 1
    $\begingroup$ As for the second set of numbers, an LCG just keeps going and going. You can just use the last generated number as a seed for the next set. $\endgroup$ – David K May 7 at 14:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.