I think it showed me that Kolmogorov complexity of pi’s digits is really low (this was before I even understood what Kolmogorov complexity was). Looking at it now, however, it’s not all all surprising, given that pi’s definition is already very low complexity.
Unless I misunderstand something that could be used as an RNG with properties I’ve been looking for for ages! Sadly, I don’t understand half the math involved. Example code would be nice...
(I’m pretty interested in roguelikes and procedural content generation in games, and have played around with various algorithms for infinite consistent worlds etc. - if your name’s anything to go by, I expect you might be interested in that stuff too)
Something that can act like a lookup table of random binary data of infinite size and dimensionality, which is as fast as possible but have very low demands on the quality of the randomness.
This should if I got things right be both faster and more random than XORing a load of bitstrings repeating with different prime numbers length.
I don’t think it’s fast. The any-base one that NancyLebovitz linked to claims to be O((n log n)^3). The original hex one, I don’t know exactly but from the description on wikipedia it’s definitely worse than O(n) (I’d guess significantly worse).
Oooh, interesting. While not exactly right some could probably be re-purposed as an RNG yes… Especially cryptographic hash functions seem interesting, but they are probably far to slow. Something that looks like a cryptographic hash function to someone who really sucks at cryptography is probably what I’m looking for. Also there are probably some things to gain from collisions being a non-issue and the output needed being extremely short.
I don’t actually know exactly what I need this for, it’s just somehting I for some reason tend to stumble upon repeatedly when I think about compsci things and has thus concluded would be generally useful. Procedural generation, either for games, art, or math experiments, probably constitutes most of it thou.
>>> import random
>>> def random_lookup(key):
random.seed(("Whatever", key))
return random.randint(0, 999)
>>> random_lookup(11)
885
>>> random_lookup((42, 115, 802))
481
>>> random_lookup((31, 42, 717))
805
>>> random_lookup("strings are good keys too")
564
>>> random_lookup(11)
885
>>> random_lookup("strings are good keys too")
564
… internally, he’s just using the hash of your input as a random seed, but then you can get random floats, etc.
I used something like that to get boundless fields of random temperatures, elevation and humidity, resulting in a tile-based world with mountains, oceans, swamps, forests etc. that you could scroll as far as you wanted to in any direction, and always get the same thing for a given position.
Ok, that’s pretty fast for python. Should be fast enough for anything with speed requirements that makes python a viable language in the first place. Unless I did the math wrong somewhere.
4000 per second is probably way to slow for any application I might use, and I don’t think I have quite the kind of wizardry needed to employ the graphics card for anything.
Not awfully—I haven’t counted but for a screenful of terrain tiles there can’t be more than a thousand calls, which could be a bit slow if you’re recalculating everything every frame, but is fast enough as soon as you cache your results, so that you only need to calculate new, undiscovered terrain.
If performance is really a problem, it’s always possible to rewrite the slow bits in C, using simpler algorithms than the Python hash function.
Once I found out that you can compute any digit of pi without computing any other digit (albeit in hexadecimal), my life just wasn’t the same anymore.
It surprised me tremendously, but I don’t think it’s affected me otherwise. If you were being literal, what changed for you?
It isn’t limited to hexidecimal.
I like the way the author formatted their summation formulas in ascii.
I think it showed me that Kolmogorov complexity of pi’s digits is really low (this was before I even understood what Kolmogorov complexity was). Looking at it now, however, it’s not all all surprising, given that pi’s definition is already very low complexity.
!!!
Unless I misunderstand something that could be used as an RNG with properties I’ve been looking for for ages! Sadly, I don’t understand half the math involved. Example code would be nice...
Is there something wrong with the Mersenne Twister?
Yes, lots of things, although I don’t know a quick or non-technical way of summing up what.
Looking at my response to Emile below will probably help.
Is there something wrong with AES in counter mode?
what is that?
Encrypting successive integers with AES gives you a pretty fast and very high quality PRNG.
apperently I’m geting to tired to cognite any compsci rigth now, it might work thou.
I’m curious, what properties are you looking for?
(I’m pretty interested in roguelikes and procedural content generation in games, and have played around with various algorithms for infinite consistent worlds etc. - if your name’s anything to go by, I expect you might be interested in that stuff too)
Something that can act like a lookup table of random binary data of infinite size and dimensionality, which is as fast as possible but have very low demands on the quality of the randomness.
This should if I got things right be both faster and more random than XORing a load of bitstrings repeating with different prime numbers length.
I don’t think it’s fast. The any-base one that NancyLebovitz linked to claims to be O((n log n)^3). The original hex one, I don’t know exactly but from the description on wikipedia it’s definitely worse than O(n) (I’d guess significantly worse).
oh, yea then it’s probably useless.
That sounds like a hash function, or are you looking for something else? (something faster?)
What applications do you have in mind? Procedural generation in games, or something else?
reads up on hash functions
Oooh, interesting. While not exactly right some could probably be re-purposed as an RNG yes… Especially cryptographic hash functions seem interesting, but they are probably far to slow. Something that looks like a cryptographic hash function to someone who really sucks at cryptography is probably what I’m looking for. Also there are probably some things to gain from collisions being a non-issue and the output needed being extremely short.
I don’t actually know exactly what I need this for, it’s just somehting I for some reason tend to stumble upon repeatedly when I think about compsci things and has thus concluded would be generally useful. Procedural generation, either for games, art, or math experiments, probably constitutes most of it thou.
In Python, you can do things like
… internally, he’s just using the hash of your input as a random seed, but then you can get random floats, etc.
I used something like that to get boundless fields of random temperatures, elevation and humidity, resulting in a tile-based world with mountains, oceans, swamps, forests etc. that you could scroll as far as you wanted to in any direction, and always get the same thing for a given position.
Nice trick, thanks, but isn’t it awfully slow?
How fast do you need it to be? My laptop can do SHA1 about 2^20 times with no noticeable delay.
Ok, that’s pretty fast for python. Should be fast enough for anything with speed requirements that makes python a viable language in the first place. Unless I did the math wrong somewhere.
Thanks.
Sorry, that’s not actually Python. I was minting a 20-bit Hashcash stamp.
Edit: In Python, I get 2^15 hashes in similar time.
Edit2: and if for some reason you need insane speed, I believe graphics cards can be made to perform hashing.
Edit3: with the specific code listed in the 4-parent, rather than using hashlib.sha1(), about 2^12. The point is that computers are fast.
4000 per second is probably way to slow for any application I might use, and I don’t think I have quite the kind of wizardry needed to employ the graphics card for anything.
I don’t think Pavitra was talking about seconds, but in “no noticeable delay”—on my laptop, in python, I get about 2^22 hashes per second.
Oh. Well then I don’t know but it’ll be worth trying if I ever need to do somehting like this in python.
Not awfully—I haven’t counted but for a screenful of terrain tiles there can’t be more than a thousand calls, which could be a bit slow if you’re recalculating everything every frame, but is fast enough as soon as you cache your results, so that you only need to calculate new, undiscovered terrain.
If performance is really a problem, it’s always possible to rewrite the slow bits in C, using simpler algorithms than the Python hash function.