Random Geekery - Random number using threads - Truly random?

[FaithlessThinker]

Inspired by nophun... And the pun in the title was unintended

So this is a Java application (console-based) that I created which utilizes concurrently running^ threads to create a 10-digit random number (without repetition of digits).

I know there are various methods to easily get random numbers in Java such as Math.random() but as nophun says, "Why not?"

Here goes the code:

Show More Hide

{TEXT}

Example outputs (each output occured on a fresh new run):

Show More Hide

{TEXT}

Now my question to you all is:

• Standard methods such as Math.random produces a pseudo-random* number.
• My method above utilizes threads to create a random number.
• Is this pseudo-random or truly random?
• Discuss.

^ They do not actually run concurrently but are scheduled by the operating system or the Java VM (I'm not sure which does the scheduling), with the exception that multi-core systems can run some of the threads concurrently.

* Pseudo-random means they look random to the human eye but is actually a predictable result. That's because if the random number generator is fed with the same seed over and over again, it will generate the same number over and over again.

 

[Master_Ghost_Knight]

Re: Random Geekery - Random number using threads - Truly ran

If you are using multi-threading and the criteria of enhancement depends on which thread gets the CPU first then it is parially truly random because the the thread that is going to get the CPU first depends on what other process other than your program is doing and when you have initiated the execution of your program, partially beause in effect the threads launched first have a better chance of getting the processor first before everyone else. A more often then not you can get into ressonation condition as the cicles of interrumptions and atributions mach the processing lenghts of the threads giving very often repetitive results.
But this is a really ineficient way to process things, not only because you have an unecessry destribution of bolean array that can be turned into one short int (and thus saving memory), but primarilly because having threads crank things up in a racing condition takes allot of time, pseudo-random numbers even tough they are not truly random they appear random enough and in contrast can be calculated extremely fast.

Another problem of multi-threading is that different threads may try to do the same operation simultaneously while the CPU in switched between them, causing from time to time a conflictuous result and you will not get what you were expecting (there are methods to prevent this).

Ps. How are you defining your bollean variables? because those seam a bit strange.

 

[FaithlessThinker]

Re: Random Geekery - Random number using threads - Truly ran

If you are using multi-threading and the criteria of enhancement depends on which thread gets the CPU first...

Yes, my program runs 10 threads simultaneously and the random number generator highly depends on which thread gets the CPU next. You said it's partially truly random. Why partially? Is it because of the way the thread scheduler behaves?

But this is a really ineficient way to process things, not only because you have an unecessry destribution of bolean array that can be turned into one short int (and thus saving memory), but primarilly because having threads crank things up in a racing condition takes allot of time, pseudo-random numbers even tough they are not truly random they appear random enough and in contrast can be calculated extremely fast.

I know I'm just doing this for fun. It's just pure geekery and not intended to serve any purpose such as complementing or replacing pseudo-random numbers.

Ps. How are you defining your bollean variables? because those seam a bit strange.

What's strange about them? If you're talking about declaring them as static, yea maybe I could have not done that. EDIT: I can't do that because they cannot be referenced by methods in the class if they are non-static.

Yea and I was thinking of using an int instead of depending on boolean arrays. I'm going to refine my program now.

 

[Master_Ghost_Knight]

Re: Random Geekery - Random number using threads - Truly ran

Yes, my program runs 10 threads simultaneously and the random number generator highly depends on which thread gets the CPU next. You said it's partially truly random. Why partially? Is it because of the way the thread scheduler behaves?

I have explained that. It is because the first threads in are more likely to get the CPU first and thus skewing the results.

What's strange about them? If you're talking about declaring them as static, yea maybe I could have not done that. EDIT: I can't do that because they cannot be referenced by methods in the class if they are non-static.

It didn't worryed me that they were static, it worryed me that they were defined has "boolean" instead of "bool" as I would expect in C or C++, you are using C++ right? I just asked this because I have recently been handling a work where the method "boolean" is a reconstructed from a enum instead of using the default libraries for that.

 

[borrofburi]

Re: Random Geekery - Random number using threads - Truly ran

Aside from the inefficiency (random.org's methods of atmospheric noise sampling are probably more efficient), there are a few troubles.

These are deterministic, everything that runs on a computer is deterministic (indeed a valid question is: does true random exist?). Will you ever get this exact same operating state? Extremely unlikely. Are you likely to get the same thread scheduling? Probably not. Is it effectively random? Maybe.

In many cases pseudo random is a feature, not a bug. You can get effectively random by using the current time as the seed.

 

[FaithlessThinker]

Re: Random Geekery - Random number using threads - Truly ran

It is because the first threads in are more likely to get the CPU first and thus skewing the results.

Yea I noticed that and that's why I'm programmatically discarding the first result and taking only the second. That way it seems more random:

        if (digits[digit] == false) {
            //this is to ignore the first time the digits occur
            //that's because the first time the threads are started in order
            //0 to 9 and hence the random number generated is not truly random
            //and that's because the order of thread starting has partial
            //control over the order of the digits. example: 0213645879
            digits[digit] = true;
        }

it worryed me that they were defined has "boolean" instead of "bool" as I would expect in C or C++, you are using C++ right?

Lol no!

So this is a Java application ...

@burrofburi: So I guess any kind of random algorithm purely based on programming on a deterministic computer will always be pseudo-random. The only way to generate a truly random number is to introduce a non-deterministic element in the algorithm (such as atmospheric noise sampling). Is that right?

I'm learning new things =)

 

[Master_Ghost_Knight]

Re: Random Geekery - Random number using threads - Truly ran

I could swear this looks like class programing in c++. I didn't suspected it was Java because you have predefined all your variables (except for i), I used to programa thing or 2 on Java but not excedingly proficient in it, my boat is C and C++.

 

[borrofburi]

Re: Random Geekery - Random number using threads - Truly ran

@burrofburi: So I guess any kind of random algorithm purely based on programming on a deterministic computer will always be pseudo-random. The only way to generate a truly random number is to introduce a non-deterministic element in the algorithm (such as atmospheric noise sampling). Is that right?

Yes... and no. Your algorithm is non-deterministic in the sense that "given a string of input, output, and the algorithm, you can't determine what's coming next", though it's deterministic in the sense that it's run purely on a finite-state automata machine and as a result if you know the state of the machine you can predict what's coming.

In CS, especially those computational complexity people, *especially* those quantum computing theorists, there's a lot of work done on "non-deterministic algorithms" but they're meant to run on quantum computers (so in a sense, they do depend on an outside non-deterministic element).

One problem with pseudo random number generators is that given a long enough string of the generated numbers** you can figure out what's coming next, but since your method depends more on the state of the machine and generally things that are not controllable by the program running it, it is unlikely this is possible with thread scheduling since it is so highly dependent on the state of the machine.

However I'm not convinced it's completely "random" in the sense of "are certain numbers more likely than others?". Pseudo-random number generators are random in that sense. In some sense you could say that pseudo-random numbers are more "deterministic" than yours (you have to know less about the state of the machine). But while your method depends on the unpredictable-from-our-perspective state of the machine, that doesn't necessarily make it random.

After all, we're wondering if pi is truly random or just pseudo random (or at least were, a few years ago, though I doubt that's been solved because it seems to me it'd require a major advance in mathematics). Indeed, I've even heard criticism of random.org's atmospheric noise method because there *could* be an underlying pattern to atmospheric noise that we just don't know or have yet to detect. You have the same problem, only with less chaos involved (i.e., maybe I can predict that numbers larger than 5xxxxx are 2/3 more likely than the numbers below it).

Essentially, the question I want the answer to is: how much entropy is in the number? Off the top of my head I'm not sure of the best way to perform such an experiment.



**With most pseudo random number generators this is usually around 2^32-1 numbers... It'd take a bit of time before you'd start getting a repeating string. With enough number theory knowledge, though, it might be possible to reduce that (by taking a series of size n and trying to reverse engineer the algorithm and the (relatively prime(?)) numbers involved, but this sounds unlikely).

 

[borrofburi]

Re: Random Geekery - Random number using threads - Truly ran

I could swear this looks like class programing in c++. I didn't suspected it was Java because you have predefined all your variables (except for i), I used to programa thing or 2 on Java but not excedingly proficient in it, my boat is C and C++.

Java is... inspired by C++. Essentially C++ is an awful, hacked together language evolved (not designed) on top of C++. Java fixes that: java was designed to be object oriented from scratch. As such object-oriented programming is all it does, none of this C scripting that runs underneath C++, none of these "why is it done that way?" "oh because C++ compilers have to be able to compile C code and C already took that syntax, so C++ had to have a weird syntax" type of crap. But that's why java looks a lot like C++: it was designed as a C++ that was, well, designed instead of hacked together.

It's not all great. By design you can't have multiple inheritance; in most situations this keeps bad programs from writing bad programs, but in some rare situations it keeps some very good programmers from writing better programs. Also by design java does garbage collection for you, which can be difficult in environments where the device running it aren't as powerful (e.g., cell phones).