Rnd() vs. Long ...no joy with LSB!

microsoft.public.dotnet.languages.vb

19 Apr 2006 1:27 PM

bogusexception

(or.. "I'm getting too much Tails and not enough Heads")

I'm running into a very strange problem with random numbers and long
numbers. To demonstrate the problem, I've created a simple test.
Consider that a series of coins are to be "flipped" all at once. The
result of the combined flip are a series of bits (0 = tails or
1=heads). These bits form a number, and that number can be represented
by a type long.

OK. Not so bad so far. To determine the long, all I need to know is how
many coins will be flipped:

r = 2 ^ c

r is the long number that represents the highest value of a flip (all
flips are 1, or heads). So a value of "0" means that all coin flips
were tails. You get it. Now to get the actual flip (a mix of 0s and
1s), you just:

f = CLng(Rnd() * r)

Where f is now a long from 0 to r. Now all that you need to do is go
through each bit of the long f to determine the results of each coin
that was flipped ("0101100101001..."). We've even written a nice method
that displays the results of each flip as "H" or "T" to make it easy to
visualize.

This all works wonderfully for a while, output looking like:

[1] flip: 1
[1] verb: H
[2] flip: 2
[2] verb: HT
[3] flip: 5
[3] verb: HTH
[4] flip: 5
[4] verb: THTH
[5] flip: 10
[5] verb: THTHT

Remember that "H" = 1 and "T" = 0. So in the case where 3 coins were
flipped, the result is 5 (4 + 1). This example increases the # of coins
flipped by 1 each time, so the results are easy to see and validate.

"So whats the problem?" you say? Well, things start to go bad around
coin #22. Check out what the results look like when the coin range is
from 1 to 50:

[1] flip: 1
[1] verb: H
[2] flip: 2
[2] verb: HT
[3] flip: 5
[3] verb: HTH
[4] flip: 5
[4] verb: THTH
[5] flip: 10
[5] verb: THTHT
[6] flip: 50
[6] verb: HHTTHT
[7] flip: 2
[7] verb: TTTTTHT
[8] flip: 195
[8] verb: HHTTTTHH
[9] flip: 417
[9] verb: HHTHTTTTH
[10] flip: 726
[10] verb: HTHHTHTHHT
[11] flip: 93
[11] verb: TTTTHTHHHTH
[12] flip: 1696
[12] verb: THHTHTHTTTTT
[13] flip: 7067
[13] verb: HHTHHHTTHHTHH
[14] flip: 12951
[14] verb: HHTTHTHTTHTHHH
[15] flip: 12240
[15] verb: THTHHHHHHTHTTTT
[16] flip: 63043
[16] verb: HHHHTHHTTHTTTTHH
[17] flip: 114222
[17] verb: HHTHHHHHTTTHTHHHT
[18] flip: 14742
[18] verb: TTTTHHHTTHHTTHTHHT
[19] flip: 497841
[19] verb: HHHHTTHHTTTHTHHTTTH
[20] flip: 381701
[20] verb: THTHHHTHTTHHTTTTTHTH
[21] flip: 1100729
[21] verb: HTTTTHHTTHTHHHTHHHTTH
[22] flip: 3217500
[22] verb: HHTTTHTTTHHTTTTHTHHHTT
[23] flip: 448828
[23] verb: TTTTHHTHHTHHTTHTTHHHHTT
[24] flip: 9939800
[24] verb: HTTHTHHHHTHTHTHHTHTHHTTT
[25] flip: 15726966
[25] verb: THHHTHHHHHHHHHTTHTHHHTHHT
[26] flip: 20009544
[26] verb: THTTHHTTTHTHTHTTHTTHTTHTTT
[27] flip: 83576936
[27] verb: HTTHHHHHTHHTHTTHTTTTHHTHTTT
[28] flip: 173898176
[28] verb: HTHTTHTHHHTHTHHHHTTHHHTTTTTT
[29] flip: 141622752
[29] verb: THTTTTHHHTTTTHHHHHHTHHHHTTTTT
[30] flip: 299941248
[30] verb: THTTTHHHHTTTTTHTHHHHTHHTTTTTTT
[31] flip: 1781985408
[31] verb: HHTHTHTTTHHTHHTHHHHTTTTHTTTTTTT
[32] flip: 3541639168
[32] verb: HHTHTTHHTTTHHTTHTTHTTTTTTTTTTTTT
[33] flip: 5060871680
[33] verb: HTTHTHHTHHTHTTHHTHHTTTHHTTTTTTTTT
[34] flip: 16940951552
[34] verb: HHHHHHTTTHHHTTTTHTTHHTHTTTTTTTTTTT
[35] flip: 31300495360
[35] verb: HHHTHTTHTTHHTHTTHHHHTHTHTTTTTTTTTTT
[36] flip: 15590113280
[36] verb: TTHHHTHTTTTHTTHHHHHTTHTTTTTTTTTTTTTT
[37] flip: 95535947776
[37] verb: HTHHTTTHHHHHTTHHTTTHTHHHTTTTTTTTTTTTT
[38] flip: 269381238784
[38] verb: HHHHHTHTHHHTTTTHTHHHHHHTTTTTTTTTTTTTTT
[39] flip: 134102679552
[39] verb: TTHHHHHTTHHHTTHTTHTTHTTHTTTTTTTTTTTTTTT
[40] flip: 586999660544
[40] verb: HTTTHTTTHTHTHTHHHHHTHTTTTTTTTTTTTTTTTTTT
[41] flip: 233909387264
[41] verb: TTTHHTHHTTHHHTHHTTTTHTHHTTTTTTTTTTTTTTTTT
[42] flip: 4395471732736
[42] verb: HHHHHHHHHHTHHTTHHTHTTTHTTTTTTTTTTTTTTTTTTT
[43] flip: 5947706048512
[43] verb: HTHTHHTHTTTHHTTHHHTHHHTHTTTTTTTTTTTTTTTTTTT
[44] flip: 276266221568
[44] verb: TTTTTHTTTTTTTHTHTTHTHHTTTTTTTTTTTTTTTTTTTTTT
[45] flip: 20237481148416
[45] verb: HTTHTTHHTTHHHHHHTTHHHHHHTTTTTTTTTTTTTTTTTTTTT
[46] flip: 7040550305792
[46] verb: TTTHHTTHHTTHHHTHTTTTTHHTTTTTTTTTTTTTTTTTTTTTTT
[47] flip: 14499146891264
[47] verb: TTTHHTHTTHTHHHHHHTHHTTTHTTTTTTTTTTTTTTTTTTTTTTT
[48] flip: 224865965572096
[48] verb: HHTTHHTTHTTTTTHHHTHHTTTTTTTTTTTTTTTTTTTTTTTTTTTT
[49] flip: 160148156841984
[49] verb: THTTHTTTHHTHTTHHHTHHTTHHTTTTTTTTTTTTTTTTTTTTTTTTT
[50] flip: 51396397236224
[50] verb: TTTTHTHHHTHTHHHHHTHTHTHTTTTTTTTTTTTTTTTTTTTTTTTTTT

>From coin #22 on, you do not get odd numbers anymore, and what is

worse, the LSBs are all 0s ("T"ails).

Here is the program used in this test:

Module Module1
   Sub Main()
       Dim c As New TestClass
       Dim x, f As Long
       Dim s As String
       For x = 1 To 50
           f = c.flip(x)
           s = c.flip2string(x, f)
           Console.WriteLine("[" & x & "] flip: " & f.ToString)
           Console.WriteLine("[" & x & "] verb: " & s.ToString)
       Next
   End Sub
End Module

And here is the class it calls:

Public Class TestClass
   Public Function flip(ByVal c As Integer) As Long
       Dim r, f As Long
       Try
           r = 2 ^ c
       Catch ex As ArithmeticException
           MsgBox("error: " & ex.ToString & vbCrLf & "coins: " &
c.ToString & " r: " & r.ToString)
       End Try
       f = CLng(Rnd() * r)
       If f = r Then ' result is counted as "0" due to LSB/MSB
rounding in Rnd()
           f = 0
       End If
       Return f
   End Function
   Public ReadOnly Property flip2string(ByVal c As Integer, ByVal f As
Long) As String
       Get
           Dim s As String
           Dim x As Integer
           For x = 1 To c
               If getLSB(f) = 1 Then
                   s = "H" & s
               Else
                   s = "T" & s
               End If
               f >>= 1 ' bitwise shift right
           Next
           Return s
       End Get
   End Property
   Private ReadOnly Property getLSB(ByVal i As Long) As Integer
       Get
           If i And 1 Then ' LSB is set (1) or "H"
               Return 1
           Else ' LSB is not set (0) or "T"
               Return 0
           End If
       End Get
   End Property
End Class

Any ideas?

TIA!

19 Apr 2006 1:56 PM

Andrew Morton

bogusexcept***@gmail.com wrote:

> (or.. "I'm getting too much Tails and not enough Heads")
>
> I'm running into a very strange problem with random numbers and long
> numbers.
>
> f = CLng(Rnd() * r)

Try System.Security.Cryptography.RNGCryptoServiceProvider.GetBytes

Andrew

19 Apr 2006 1:57 PM

Larry Lard

bogusexcept***@gmail.com wrote:
Show quoteHide quote

> (or.. "I'm getting too much Tails and not enough Heads")
>
> I'm running into a very strange problem with random numbers and long
> numbers. To demonstrate the problem, I've created a simple test.
> Consider that a series of coins are to be "flipped" all at once. The
> result of the combined flip are a series of bits (0 = tails or
> 1=heads). These bits form a number, and that number can be represented
> by a type long.
>
> OK. Not so bad so far. To determine the long, all I need to know is how
> many coins will be flipped:
>
> r = 2 ^ c
>
> r is the long number that represents the highest value of a flip (all
> flips are 1, or heads). So a value of "0" means that all coin flips
> were tails. You get it. Now to get the actual flip (a mix of 0s and
> 1s), you just:
>
> f = CLng(Rnd() * r)
>
> Where f is now a long from 0 to r.

Rnd() is a Single. Single has about 23 bits of precision. This is not a
good way to try and get 64 random bits.

To get n random bits:

Make a function that gives you a random bit, and call it n times.

Alternatively, you could use Random.NextBytes, which fills a byte array
with random bits. (If you want cryptographically strong random bits,
use a Cryptography.RandomNumberGenerator)

--
Larry Lard
Replies to group please

19 Apr 2006 10:34 PM

bogusexception

Larry,

After your post, I found this on 15seconds:

"Rnd() Internals

The Rnd() uses the following formula:

x1 = (x0 * a + c) MOD (2^24)

where a = 1140671485 and c = 12820163

The default value for x0 is 327680 (&h50000). This is why you get
repeatable sequences when you do not use the Randomize statement prior
to the first Rnd() function invocation.

Please notice the 2^24 division. This results in a 'period' for the
PRNG, where a sequence of values from the Rnd() function will repeat
after 16.77M invocations. In talks with my local crypto expert, we both
agreed that this is a serious flaw in the PRNG. Since I was only using
the first 30 items of each sequence, I wasn't too concerned about this.

To get the 0 <= Rnd() < 1 values, the x1 value is divided by 2^24
before it is returned to your Visual Basic program code. It is then up
to the VB programmer to transform the returned values into a scale and
range that is appropriate for the application."

I still need to create a fixed length long whose value is 2^numCoins,
then pick a random # from 0 to that #.

Thanks!

19 Apr 2006 2:11 PM

José_Manuel_Agüero

Hello bogusexception,

The Rnd() function returns a Single, that is, a precision of 23 digits. You may want to generate a number using the Random class (http://msdn.microsoft.com/library/?url=/library/en-us/cpref/html/frlrfSystemRandomClassTopic.asp?frame=true)

To generate a Long, you may use:
dim b(7) as byte, l as long
'dim r as new random 'elsewhere
r.nextbytes(b)
l=bitconverter.toint64(b,0)

Anyway, you may adapt your program to work on an array of bytes instead of a long or, even better, generate the random bytes and convert them to an array of boolean, so that checking tail/head is trivial.

Regards.

Show quoteHide quote

19 Apr 2006 6:58 PM

Klaus

Looks pretty complicated for such an easy task!

Two for-loops should also work, something like

for i as integer = 1 to 50 ' Number of coins
Dim s As String
for j as integer = 1 to i
    if (Rnd() * 2) >= 1 then
      s &= "H"
    else
      s &= "T"
    endif
next
Console.WriteLine(s)
next

and with System.Security.Cryptography.RNGCryptoServiceProvider.GetBytes
your throws would be really random!

I didn't try it out so I just hope it works,

Klaus

19 Apr 2006 10:32 PM

bogusexception

Klaus,

You are right. If all I wanted to do was output H and T, your program
would be great. But the HTHHTHT was just to show what was happenning
with Rnd(). The real purpose of the program is to flip n coins all at
the same time, then gather their state(H or T).

So the task is to specify a number of coins, and create a long number
that is from 0 to 2^coins. The steps were:

highestValue = 2^coins ' if all bits(coins) were 1 (Heads)
randomLong = <randomFunction>(highestValue)

So the problem isn't simply to create a random long, but to create a
random long that has a fixed number of bits. The number may have 1 bit
(2 choices), or hundreds of bits.

Of course, there are far slower, easier ways to do this. The key here
is to build the fastest simultaneous coin flipper (theres an acronym in
there somewhere!). I thought that the fastest way to to do it was to
flip all coins in a single line of code. Unfortunately, Rnd() is just
for single types.

Thanks!

19 Apr 2006 10:36 PM

bogusexception

Jose,

I tried the code you submitted, but I can't figure out where/how I
would set/limit the highest value (# of bits).

Works great, though!

Thanks!

19 Apr 2006 11:17 PM

José_Manuel_Agüero

Hello,

I still don't understand very well what you're attempting to do, but this is what I meant:

Private Sub butMonedas_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles butMonedas.Click

    Dim r As New Random

    Dim coins As Integer = 27 'Put here the number of coins (or true/false values) that you want.

    Dim by() As Byte

    Dim ba As BitArray

    Dim s As String = ""

    ReDim by((coins - 1) \ 8) 'Each byte holds 8 coins.

    r.NextBytes(by)

    ba = New BitArray(by)

    For n As Integer = 0 To coins - 1

        If ba(n) Then

            s &= "H"

        Else

            s &= "T"

        End If

    Next

    Debug.WriteLine(s)

End Sub

Regards.

Show quoteHide quote

<bogusexcept***@gmail.com> escribió en el mensaje news:1145486179.740727.292250@t31g2000cwb.googlegroups.com...
| Jose,
|
| I tried the code you submitted, but I can't figure out where/how I
| would set/limit the highest value (# of bits).
|
| Works great, though!
|
| Thanks!

20 Apr 2006 2:31 PM

bogusexception

Jose,

I'm glad you wrote. The problem is really quite simple, and I think I
only need to change what you've done slightly to achieve what is
needed.

If a bit corresponds to a single coin, then there is an inherent limit
to the amount of coins that can be simultaneously flipped on a system,
based on the limitations of the math types. Double and Long = 64 bits
(8 bytes).

But what if you need to flip 100 or more coins at the same time? What
about 200? The fastest way (I thought) to flip that many coins is to
determine the largest number that the bits would represent if they were
all 1: "2 ^ coins" and then pick a random number from 0 to that number.

The problem is that even on modern systems you can't get close to 200
bits for a single number.

So the problem needs to be broken down somehow into (I'm assuming)
multiples of "Long" numbers, and picking a random number for each
section. Then, you put the pieces back together.

So if I can find a method that allows a number to represent 200+ bits
(coins), then it should be possible to flip the coins in "sections" of
"Long" numbers.

In your example, you create a string of "H" and "T", but I need a way
to store that "flip" in an array so it can be re-created.

Make sense?

TIA!

20 Apr 2006 4:10 PM

Andrew Morton

bogusexcept***@gmail.com wrote:

> I'm glad you wrote. The problem is really quite simple, and I think I
> only need to change what you've done slightly to achieve what is
> needed.

I think you're trying to over-analyze the situation.

> If a bit corresponds to a single coin, then there is an inherent limit
> to the amount of coins that can be simultaneously flipped on a system,
> based on the limitations of the math types. Double and Long = 64 bits
> (8 bytes).

No - there is no simultaneous generation of all the bits in the random
number. There is all sorts of shuffling of bits in separate bytes going on
to generate the random number. Forget about simultaneous.

> But what if you need to flip 100 or more coins at the same time? What
> about 200? The fastest way (I thought) to flip that many coins is to
> determine the largest number that the bits would represent if they
> were all 1: "2 ^ coins" and then pick a random number from 0 to that
> number.
>
> The problem is that even on modern systems you can't get close to 200
> bits for a single number.

That's why you want to use an array, as in José's example.

Andrew

20 Apr 2006 8:11 PM

José_Manuel_Agüero

Well, reading Andrew's comments I've understood better your problem:
You want to store the bits in a numeric type. As the largest numeric type is Decimal (stores 96 bits), you could use it... But it's not practical.
In my example I've stored the bits in an array of bytes and then, created an array of bits (BitArray).
As I'm an afficionate and not good with conceptual explanations, I'll reproduce your test class, so you'll see how you can use more bits than you'll probably ever need:

Module Module1

    Sub Main()

        Dim c As New TestClass

        Dim x As Integer

        For x = 1 To 50

            c.flip(x)

            Console.WriteLine("[{0}] flip length: {1}", x, c.bits.Count)

            Console.WriteLine("[{0}] verb: {1}", x, c.flip2string)

        Next

        x = 500

        c.flip(x)

        Console.WriteLine("[{0}] flip length: {1}", x, c.bits.Count)

        Console.WriteLine("[{0}] verb: {1}", x, c.flip2string)

        Console.ReadLine()

        'You have the bits in c.bits and you can store it for later use...

    End Sub

End Module

Public Class TestClass

    Private r As New Random

    Private ba As New BitArray(0)

    Public Sub flip(ByVal count As Integer)

        If count < 1 Then Throw New ArgumentOutOfRangeException("count", count, "The number of bits must be grater than zero.")

        Dim by() As Byte

        ReDim by((count - 1) \ 8) 'Each byte holds 8 coins (bits).

        r.NextBytes(by) 'Fill the bytes with random values.

        ba = New BitArray(by) 'Create the array of bits.

        ba.Length = count 'Adjust the size of the array of bits (it could have up to 7 bits in excess).

    End Sub

    Public ReadOnly Property flip2string() As String

        Get

            Dim s As New System.Text.StringBuilder(ba.Count)

            For n As Integer = 0 To ba.Count - 1

                If ba(n) Then

                    s.Append("H"c)

                Else

                    s.Append("T"c)

                End If

            Next

            Return s.ToString

        End Get

    End Property

    Public ReadOnly Property bits() As BitArray

        Get

            Return CType(ba.Clone, BitArray) 'Return a copy of the BitArray.

        End Get

    End Property

End Class

You won't see the bits interpreted as a number, but you can have any number of bits...

Regards.

Show quoteHide quote

<bogusexcept***@gmail.com> escribió en el mensaje news:1145543508.385932.47530@i39g2000cwa.googlegroups.com...
| Jose,
|
| I'm glad you wrote. The problem is really quite simple, and I think I
| only need to change what you've done slightly to achieve what is
| needed.
|
| If a bit corresponds to a single coin, then there is an inherent limit
| to the amount of coins that can be simultaneously flipped on a system,
| based on the limitations of the math types. Double and Long = 64 bits
| (8 bytes).
|
| But what if you need to flip 100 or more coins at the same time? What
| about 200? The fastest way (I thought) to flip that many coins is to
| determine the largest number that the bits would represent if they were
| all 1: "2 ^ coins" and then pick a random number from 0 to that number.
|
|
| The problem is that even on modern systems you can't get close to 200
| bits for a single number.
|
| So the problem needs to be broken down somehow into (I'm assuming)
| multiples of "Long" numbers, and picking a random number for each
| section. Then, you put the pieces back together.
|
| So if I can find a method that allows a number to represent 200+ bits
| (coins), then it should be possible to flip the coins in "sections" of
| "Long" numbers.
|
| In your example, you create a string of "H" and "T", but I need a way
| to store that "flip" in an array so it can be re-created.
|
| Make sense?
|
| TIA!