Mr RB's RNG and RNGs in general

[misterT]

I'm currently testing efficient random number generators with 8bit avr microcontrollers. This is one, not very efficient, rng I tested:

uint64_t
random64(void)
{
	v ^= (v>>21);
	v ^= (v<<35);
	v ^= (v>>4);
	return v + 2685821657736338717LL;
}

It took roughly 1400 cycles to execute on an 8bit avr. I have no intention to try write that in assembly, but I would be interested to hear some estimates of how efficient that could be if written in asm? All numbers and variables are uint 64.
My solution is, instead of wasting my time with asm, to use an AES crypto engine to generate 128bit random numbers.. it does the job in background in 375 cycles.

And a point about the efficiency of C and assembly. The truth is that C is only as efficient as the assembly code generated by the compiler. So far all compilers are better assemblers than I am..

 

[Mr RB]

C is so much easier to use for math stuff.

Like for a tacho;
rpm = (60000000 / period_us);

is one easy line in C even though rpm and period_us are 16bit variables and all the math is done in 32bit. That takes a few seconds to type in C but is a rather nasty piece fo code to make in asm.


MisterT-

uint64_t
random64(void)
{
v ^= (v>>21);
v ^= (v<<35);
v ^= (v>>4);
return v + 2685821657736338717LL;
}

Where did you get that RNG code from? It looks poor, what is the point of adding a large prime number right at the end but not blending it in to the algorithm? You may as well just add "5" to the end result.

There is a RNG here that generates very good entropy from a simple algorithm although it is not particularly time efficient; The Black Random number generator

 

[misterT]

C is so much easier to use for math stuff.

Like for a tacho;
rpm = (60000000 / period_us);

is one easy line in C even though rpm and period_us are 16bit variables and all the math is done in 32bit. That takes a few seconds to type in C but is a rather nasty piece fo code to make in asm.


MisterT-

Where did you get that RNG code from? It looks poor, what is the point of adding a large prime number right at the end but not blending it in to the algorithm? You may as well just add "5" to the end result.

There is a RNG here that generates very good entropy from a simple algorithm although it is not particularly time efficient; The Black Random number generator

The RNG I posted (the code is missing the initialization) is from the book "Numerical Recipes - The Art of Scientific Computing, 3rd edition". In the book it says: "It has a period of “only” 1.8e19, so it should not
be used by an application that makes more than  10^12 calls. With that restriction, we think that it will do just fine for 99.99% of all user applications".

I don't know the point of adding the large prime number, but the idea behind "xorsift" random number generator is developed by Marsaglia https://www.jstatsoft.org/v08/i14/paper

 

[misterT]

There is a RNG here that generates very good entropy from a simple algorithm although it is not particularly time efficient; The Black Random number generator

How do you (Mr RB) define "very good entropy"? Have you tested your Black RNG with some test algorithms like Diehard or the tests recommended by NIST? Also, you claim that the Black RNG generates pure random numbers that cannot be predicted.. How it is impossible to predict something that your algorithm just generated? And how is "unbreakable encryption" useful to anybody? Every encryption algorithm must have a method to decrypt the data, so by definition unbreakable encryption is impossible (or useless).

Sorry for the off-topic.

 

[LTX71CM]

How do you (Mr RB) define "very good entropy"? Have you tested your Black RNG with some test algorithms like Diehard or the tests recommended by NIST? Also, you claim that the Black RNG generates pure random numbers that cannot be predicted.. How it is impossible to predict something that your algorithm just generated? And how is "unbreakable encryption" useful to anybody? Every encryption algorithm must have a method to decrypt the data, so by definition unbreakable encryption is impossible (or useless).

Sorry for the off-topic.

Computers don't do "random", I don't think Mr RB suggested the Black RNG was pure random, just that it had better entropy.

Breaking encryption and reversing (decrypting) it are two different things. With random or good pseudo-random seeds, encryption with no predictable patterns can hopefully be obtained, this makes it very difficult to break/crack (Provided you're using a decent algorithm). Breaking encryption suggests you've found a weakness, a shortcut to the end zone, you side-stepped knowing the cipher key. If you know the key you're not breaking the encryption, you're decrypting it.

 

[be80be]

misterT said the same thing. And

Computers don't do "random",

no but people do LOL

 

[misterT]

I don't think Mr RB suggested the Black RNG was pure random, just that it had better entropy.

Yes he did. In the website he says: "My algorithm for generating pure entropic (random) data" and "After enough passes the data is completely random and cannot be predicted."

 

[LTX71CM]

Yes he did. In the website he says: "My algorithm for generating pure entropic (random) data" and "After enough passes the data is completely random and cannot be predicted."

Mr RB didn't say that, Mr Black did.

There is a RNG here that generates very good entropy from a simple algorithm although it is not particularly time efficient; The Black Random number generator

I'd say either Mr Black isn't well informed or that he knows something others don't. Perhaps he just mis-spoke/mis-typed.

 

[Mr RB]

3V0-

Optimizing compilers can compact code in ways that no rational human would. Optimized code can be smaller then hand coded assembly.

There's no way in hell any compiler can optimise a small fast task to the level that a good human assembler coder can. Compilers can optimise large complex code to be better than what an assembler programmer can do easily. Those are 2 very different concepts.

MisterT-

The RNG I posted (the code is missing the initialization) is from the book "Numerical Recipes - The Art of Scientific Computing, 3rd edition". In the book it says: "It has a period of “only” 1.8e19, so it should not
be used by an application that makes more than 10^12 calls. With that restriction, we think that it will do just fine for 99.99% of all user applications".

Check your code again, you are only adding the prime number;
return v + 2685821657736338717LL;
which is an essentially useless step; adding ANY number after the algorithm itself.
but if you blended the prime number into the algorithm;
return v += 2685821657736338717LL;
it would start to be usable as a RNG. I'm guessing either your code or the book had a typo.

LTX71CM-

Computers don't do "random", I don't think Mr RB suggested the Black RNG was pure random, just that it had better entropy.

"Pure" random is in the eye of the beholder. Any process that produces a new number that cannot be predicted by knowing all the numbers before it meets my definition of random. There's no reason that that goal cannot be produced algorithmically. My process uses an algorithm, a 1Mbit cache and values held within the RNG engine. The algorithm may be known but what the algorithm does with the cache has random factors determined by the cache and by the engine. The result is *sufficiently* random that the next number in the sequence can't be predicted by the observer.

MisterT-

How it is impossible to predict something that your algorithm just generated?

To predict the next number generated you would need to know the entire contents of the 1Mbit cache, and the postion in the cache, and the state of the RNG engine. It is not possible for the observer to know those things based on previously generated numbers, so to predict means you must solve for every possible solution of cache content and cache index and engine values, and that brings you back to equal odds, ie your chance of guessing.

It doesn't take long to code my RNG engine up in C, feel free to play with it and run the data through your tests. Or use it in your commercial product, I don't care. It won't do the really fast megabits/sec RN generation you asked for in your other thread but it is sufficiently random with enough passes, if you need high quality RNG generated solely by algorithm without resorting to hardware tricks.

 

[misterT]

"Pure" random is in the eye of the beholder. Any process that produces a new number that cannot be predicted by knowing all the numbers before it meets my definition of random.

Imagine that I'm a random number generator. I will shuffle numbers between 0 to 99 and give them out to you in the order I decide. There is no way you can predict the next number for sure. After giving you all of my 100 random numbers I will choose a new set of numbers - from 100 to 199. I will shuffle them and give them to you in a random order. There is no way you can predict the next number for sure.. etc.

Does that satisfy your need for a good RNG? It does exactly what you are looking for. It produces a new number which you cannot predict (by knowing all the numbers before it). And the period is infinite! Am I a perfect random number generator?

The result is *sufficiently* random that the next number in the sequence can't be predicted by the observer.

Imagine I have a service that gives me information about the world coordinates. I give them a coordinate and they tell me if it hits land or water on the earth. Now, I want to know the percentage of dry land relative to the surface of the earth.

So, my strategy is to send uniform random coordinates to the service I have available. I count the number of "land" coordinates and compare that number to the number of coordinates I have generated.

If the RNG I have used is good enough to produce millions and millions of uniformly distributed coordinates around the globe, I should have a very good answer after millions and millions of random coordinates sent. I really don't want the random numbers clustering around atlantic.. or missing the river Kwai. The millions and millions and millions of points really have to be uniformly distributed around the globe.

Can you say that your Black RNG is *sufficiently* random to give me a good results in a situation like that? Can you say that your RNG is nothing like RANDU: RANDU - Wikipedia, the free encyclopedia

MisterT- To predict the next number generated you would need to know the entire contents of the 1Mbit cache, and the postion in the cache, and the state of the RNG engine. It is not possible for the observer to know those things based on previously generated numbers, so to predict means you must solve for every possible solution of cache content and cache index and engine values, and that brings you back to equal odds, ie your chance of guessing.

Some RNGs have trouble recovering after generating a small number. I'm not saying that this is the case with Black RNG, but it is a flaw with some RNGs. If some poor RNG produces a small number, I can predict that couple of next numbers will also be small. Are you sure that Black RNG does not have this kind of flaws?

It doesn't take long to code my RNG engine up in C, feel free to play with it and run the data through your tests. Or use it in your commercial product, I don't care. It won't do the really fast megabits/sec RN generation you asked for in your other thread but it is sufficiently random with enough passes, if you need high quality RNG generated solely by algorithm without resorting to hardware tricks.

I have a challenge for you. Imagine that You are a Random Number Generator. Write down 100 numbers purely out of your imagination. Then choose one, or more, of your favourite random number generators and generate 9 more sets of 100 random numbers. Anyone can take this challenge! I am confident enough to beat this challenge most of the time (not always, there is always a chance of failure).

There is no way I can predict the numbers you choose. But, I'll bet you that I can recognize from all the 10 sets of 100 random numbers the one set that is generated by your imagination and the ones that are generated by computer.

The reason I'm giving you (Mr RB) a hard time with this is that there is a need for a really good random number generators. I want to know if Black RNG is really as good as the hype you are putting out.

 

[Mr RB]

MisterT-

After giving you all of my 100 random numbers I will choose a new set of numbers - from 100 to 199. I will shuffle them and give them to you in a random order. There is no way you can predict the next number for sure.. etc.
Does that satisfy your need for a good RNG?

No. Shuffling a set list of numbers is nowhere near random. You get exactly 1 of each number per 100 samples, giving you enormous leverage to predict the next number by knowing the previous numbers, like counting cards.

MisterT-

If the RNG I have used is good enough to produce millions and millions of uniformly distributed coordinates around the globe, I should have a very good answer after millions and millions of random coordinates sent. I really don't want the random numbers clustering around atlantic.. or missing the river Kwai. The millions and millions and millions of points really have to be uniformly distributed around the globe.

Can you say that your Black RNG is *sufficiently* random to give me a good results in a situation like that?

Yes. That is exactly what I designed it for.

MisterT-

Some RNGs have trouble recovering after generating a small number. I'm not saying that this is the case with Black RNG, but it is a flaw with some RNGs. If some poor RNG produces a small number, I can predict that couple of next numbers will also be small. Are you sure that Black RNG does not have this kind of flaws?

Yes. One of the engine tasks is to toggle bits. So any bits extracted from the engine during the RNG process have an equal chance of being 1 or 0 as one bit in the cache is always toggled for every engine cycle. To generate a random number bits are extracted over time as the algorithm progresses and must have equal probability.

MisterT-

The reason I'm giving you (Mr RB) a hard time with this is that there is a need for a really good random number generators. I want to know if Black RNG is really as good as the hype you are putting out.

I'm not offended. The fun and enthusiasm in my hobby web page (ie the "hype") is not relevant. Whether or not you like my hobby project writing style please take the time to examine the RNG, how it toggles bits, and how it transposes bits in both position AND time. The process that is performed on the cache at any instant varies dependent on the data in the cache and the state of the engine, so the entire process is sufficiently chaotic to defeat any mathematical prediction of what data it might produce next. Coupled with an equal probability of making a 1 or 0 bit, this makes it ideal for algorithmic generation of "pure" random data.

I apologise to everyone as this has got a little off-topic from the C vs ASM debate.

 

[misterT]

No. Shuffling a set list of numbers is nowhere near random. You get exactly 1 of each number per 100 samples, giving you enormous leverage to predict the next number by knowing the previous numbers, like counting cards.

But my method met your definiton of random. You said: "Any process that produces a new number that cannot be predicted by knowing all the numbers before it meets my definition of random."
Also, my proposed algorithm does not have any repeating pattern.. How long is the pattern of Black RNG? I think you were unfair to quote only a small part of my proposed RNG.

Did you even read my proposed algorithm? It produces all numbers exactly once.. so you wont get 1 of each number per 100 samples. You will get 1 of each number only once.. ever!

anyway.. are you taking my challenge? I repeat it:

Imagine that You are a Random Number Generator. Write down 100 numbers purely out of your imagination. Then choose one, or more, of your favourite random number generators and generate 9 more sets of 100 random numbers. Anyone can take this challenge! I am confident enough to beat this challenge most of the time (not always, there is always a chance of failure). There is no way I can predict the numbers you choose. But, I'll bet you that I can recognize from all the 10 sets of 100 random numbers the one set that is generated by your imagination and the ones that are generated by computer.

Anyone can take this challenge.. just post a file containing the random numbers and I will tell which one of the sets was generated by computer and which one is a result of human imagination.

 

[birdman0_o]

Your not making any sense, you didn't even propose a range. Also, stop leeching off this thread. Also your idea of taking from different sets [0,99], [100,199] isn't random. A random number has an equal chance of getting picked from a set as any other number in this set at any given instance, you are giving every other set a 0% chance.

 

[misterT]

Also your idea of taking from different sets [0,99], [100,199] isn't random. A random number has an equal chance of getting picked from a set as any other number in this set at any given instance, you are giving every other set a 0% chance.

That is exactly what I'm trying to say to Mr RB (if you can't predict it, doesn't mean it's random). I hope you are not the only one that gets my point. And about the range.. you can choose the range. My proposed (very poor and sarcastic) RNG has a range of infinity. If you are concerned about the range of my challenge.. that is up to the challenger. If you can write it into a file, I can handle it.

I know I am leeching a thread that repeats itself every two months in this forum.. sorry about that.

 

[3v0]

Shuffling a deck of cards can tend in the direction of a random shuffle (ordering) but not random numbers.

The human mind is a very bad random number generator. We favor numbers and sequences.

I favor the idea that any random number generator that starts with a seed or seeds and uses an algorithm can only look random. If we can put in the same seed info and get the same set of numbers that is not random. Even if we generate the seed info from a algorithm. With the seed info and the number of steps you can predict the next number with the algorithm.

We call them pseudo random number generators.

There are tests.
NIST.gov -
Batteries of Statistical Tests for Random Number Generators

 

[Mr RB]

Birdman-

Also, stop leeching off this thread.

That was my fault, sorry. It started when I pointed out a glaring error in MisterT's RNG and suggested a good alternative, and I think he mistook my genuine efforts to help him as some type of competition or "challenge". Threads like this do put people in an arguing mood.

3V0-

With the seed info and the number of steps you can predict the next number with the algorithm.

With any purely algorithmic process it must start from a seed and generate numbers from that point onward. But that's not the point, the point of a RNG is to spit out numbers, and if the quality of the generated numbers is high enough that they are as good as the numbers generated by a "pure" random source then the RNG is as good as it gets. After that, it's trivial to shake up the RNG with some occasional real world input. The real challenge is to get the RNG spitting out numbers of sufficient chaos. Hence my definition "The next number cannot be predicted from knowing all the numbers that came before it". I'll refine that further for MisterT; "The next number has an equal probability of being any number" - which I thought was obvious from the fact that it can't be predicted.

 

[3v0]

While not an expert in random number theory I know enough to see that most of this thread is more speculation then science.

We have access to tests used to quantify the random/non randomness of number sets. Either Mr T or yourself can run these tests and be done with it.

 

[nsaspook]

A random number generator based on a program cannot be a true "random" number generator. They can be very good but because it's an algorithm and not infinite there is always a seed or key and adding seeds from any input later will not make it better cryptographically. True random generators are based on physical methods like quantum mechanics which can generate one-time pads that are unbreakable using computation (but can be broken with a shot to the kneecap). You can design good RNGs in software with care.

https://tools.ietf.org/html/rfc4086

 

[misterT]

I'll refine that further for MisterT; "The next number has an equal probability of being any number" - which I thought was obvious from the fact that it can't be predicted.

If the next number cannot be predicted, it does not necessarily mean that all numbers (in the range) have equal probability of being the next number. Your logic is far from obvious or even rational. In roulette, every number has equal probability, but when throwing two dice the number seven is the most likely sum to turn up. Also, gaussian distribution RNGs are very important class of random number generators.. many of them are based on a good uniform random number generators.

 

[Mr RB]

3V0-

While not an expert in random number theory I know enough to see that most of this thread is more speculation then science.

We have access to tests used to quantify the random/non randomness of number sets. Either Mr T or yourself can run these tests and be done with it.

I just did, and wrote up the results for you; Black RNG - now with test results and source code


nsaspook-

They can be very good but because it's an algorithm and not infinite ...

Who says an algorithm cannot be infinite? Such closed minded thinking...