Link to home
Start Free TrialLog in
Avatar of krakatoa
krakatoaFlag for United Kingdom of Great Britain and Northern Ireland

asked on

Generating a random series.

I have my own idea of the 'best' answer to this, so this question is to arrive at others' views on the correctness or otherwise of my assumption. Here it is :

How to best construct a random sequence of 1s and 0s ?
So to end up with a string (or array or whatever) of, say, 53 0s and 1s, what would be the route / tool to obtaining that in a random fashion ?

In Java of course. But a conceptual answer will be enough, if you prefer. Thanks.
Avatar of Dr. Klahn
Dr. Klahn

Use the system's built-in random number generator, e.g., in linux /dev/random or /dev/urandom.

Be sure you don't pull "too fast."  "Too fast" is dependent on the random number hardware present in the system.
As Dr. Klahn mentioned, use /dev/random or /dev/urandom.

Tip: If you require massive quantities of random data, you can quickly... consume all entropy, where code blocks accessing the random devices... while entropy regenerates...

To avoid the "exhausted entropy blocking problem" install the rng-tools package.

This runs the rngd daemon in background to constantly generate entropy, so no random device code blocks ever occur.
BigInteger bRand = new BigInteger(53, new Random());

Open in new window

is one way. Another
UUID uid = UUID.randomUUID();

Open in new window

Interestingly only the second one uses /dev/random or /dev/urandom
Avatar of krakatoa

ASKER

Thanks y'alls.

What "worries" me most about using the RNG, is that it comes up with values between 0 and 1. When I think about that for any length of time, two things occur to me : although the RNG will eventually produce 0s and 1s, most of its determinations will lie in the fractional parts between 0 and 1, which is a range completely unhelpful to my cause. This could not only be considered as a potential skew vulnerability, (perhaps exposing it to some form of attack), but it is immensely wasteful computationally. I'm only interested in 0s and 1s, and if 0s and 1s are all you need to end up with, there's no point using a routine that makes swarf in the process.

My aim is to have a string of 53 0s and 1s, which can be considered as unique to the tune of one in 9 thousand trillion - because 2 to the power 53 is over 9 quadrillion possible combinations. And I need a string which will be used for its uniqueness, and unlikelihood of being replicated. So a one in 9 quadrillion chance of duplication seems good enough for this I believe.

I did some digging on other forums also, and saw similar suggestions pointing to RNGs as a solution. But what I've actually gone and done is this :

public static void main(String[] args){
        
        IntStream stream;
    
        for(int r=0;r<firstSet.length;r++){

            stream = random.ints(0,2).limit(1);
        
            final int t = r;   
            stream.forEach(integer -> firstSet[t] = integer);
            
            /** DEBUG
                if(firstSet[t] == 1){count1++;}
                else{count0++;}
            */
            
        }
               
    }

Open in new window


. . . wherein firstSet is  "static Integer[] firstSet = new Integer[53];"
. . .  random is a "new Random();"
. . . and count1 and count0 are simple integer counters.

I'd be really interested in hearing all your thoughts on this. Thanks.

although the RNG will eventually produce 0s and 1s, most of its determinations will lie in the fractional parts between 0 and 1,
That, afaik, is impossible. We're talking about 'switches' (gates) on a chip. It's literally binary.
The UUID class is designed for your use case.
CEHJ - I can't tell over this forum without sounding rude, whether you had time to look at my last post from the perspective I outlined in the narrative part. Because the generation of superfluous values by an RNG is a complete waste imho for my case. It might be ok for folk seeking randomness over a greater range, but not for my use case.

And . . . the lit for BigInteger says :

public BigInteger(int numBits,          Random rnd)

Open in new window

Constructs a randomly generated BigInteger, uniformly distributed over the range 0 to (2numBits - 1), inclusive. The uniformity of the distribution assumes that a fair source of random bits is provided in rnd. Note that this constructor always constructs a non-negative BigInteger.

So you can end up with a 0, or at the top end (if your exponent of 2 were say 4, giving 16), a 15. Thus a 1 somewhere would also emerge.
So you can end up with a 0, or at the top end (if your exponent of 2 were say 4, giving 16), a 15. Thus a 1 somewhere would also emerge.
I think i know what you're getting at here, but you can think of it more perhaps as a bit set. What you need is 53 random bits and that is what a random number is - a set of on or off bits. You can iterate over the bits for the full spectrum. To use the smaller examples as you did, if you wanted 4 random bits instead of 53 and you got the digit 4 returned from generation, you wouldn't have binary 100 but binary 0100. You can extrapolate that thinking to your 53 bits
The thing is, I want to send each individual ‘bit’ to the remote peer. To get that from a BigInteger, is there a way other than taking its .toString() and iterating that? Because the remote peer will be judging each value as it arrives.

(And that’s ignoring the production overhead of BigInt being randomized, even if that overhead is only a philosophical nicety).
I don't think there's really much problem,  and incidentally if you're doing socket IO, there are methods to just produce a random byte[]. Harder, but purer work could be done by something like

int bit = Math.random() > 0.5? 1 : 0;

Open in new window


in a loop, but in a sense, all these methods are doing that in essence, just more efficiently.
Two peers have an identical 53 character string of 1s and 0s embedded in the code. Each end checks what the other is sending, following the same sequence. So no socket-time bit creation is useful. And a BigInteger might be comprised of 1s and 0s, but not until its .toString() is taken can they be examined individually. afaiaa.

The attraction of using the IntStream and throttling it to a space of 0 and 1, and a limit of a single return token from each stream call, is that it's 100% focussed on a binary space. None of the other methods can say the same about themselves above the waterline. What goes on in the stream and lambda itself is a matter for the developers, but my perspective is that I get an API guarantee that this method has to deliver.
Well you could call https://docs.oracle.com/javase/10/docs/api/java/math/BigInteger.html#testBit(int) but you might as well go for the approach you mentioned (as in my last code too) if you're not over-concerned with efficiency

Having said that, i haven't done the maths but with the BigInteger code i posted, i think the probability of several leading zeros is higher there than if you simply composed a string of random(2)
Of course I was wrong to say that taking the toString() of BigInteger would render a string of 1s and 0s - it just produces the number. So that wouldn't be what I am looking for in any case.

The int bit = Math.random() > 0.5? 1 : 0;  is better, but suffers from overproduction, as can be seen when the process is broken down :

            double bit = Math.random();
            System.out.println(bit);
            bit = bit > 0.5? 1 : 0;
            System.out.println(bit);
ASKER CERTIFIED SOLUTION
Avatar of CEHJ
CEHJ
Flag of United Kingdom of Great Britain and Northern Ireland image

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
Well of course toString invoked with 2 as the base parameter actually would produce just that.
That's why I didn't use it.

My own library for this does produce them.
Would be interesting to see your code at some point. And, why you created it. ;)

:)
I'll try to dig it out. It basically provides the entire bit pattern in the datatype in question instead of just giving the number in its binary form
ok.
(Course, you’re always welcome to add ‘my’ IntStream solution into your portfolio. ;)
Kind - but i wouldn't use something that new-fangled (less support) ;)
<<... i wouldn’t use something that new-fangled>>

Well you could always open a question on it and I’ll walk you through it.
Ah no - you misunderstand i think. When i say "new-fangled", my concern is that this code uses (when it doesn't really need to) features that are only present >= 1.8. That, to me, is an unnecessary restriction to runnability.
I'm not denying the past, just trying to embrace the future; which for some people, of course, is already here, or on the way.