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

[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: HHHHTHHTTHTTTTH H
[17] flip: 114222
[17] verb: HHTHHHHHTTTHTHH HT
[18] flip: 14742
[18] verb: TTTTHHHTTHHTTHT HHT
[19] flip: 497841
[19] verb: HHHHTTHHTTTHTHH TTTH
[20] flip: 381701
[20] verb: THTHHHTHTTHHTTT TTHTH
[21] flip: 1100729
[21] verb: HTTTTHHTTHTHHHT HHHTTH
[22] flip: 3217500
[22] verb: HHTTTHTTTHHTTTT HTHHHTT
[23] flip: 448828
[23] verb: TTTTHHTHHTHHTTH TTHHHHTT
[24] flip: 9939800
[24] verb: HTTHTHHHHTHTHTH HTHTHHTTT
[25] flip: 15726966
[25] verb: THHHTHHHHHHHHHT THTHHHTHHT
[26] flip: 20009544
[26] verb: THTTHHTTTHTHTHT THTTHTTHTTT
[27] flip: 83576936
[27] verb: HTTHHHHHTHHTHTT HTTTTHHTHTTT
[28] flip: 173898176
[28] verb: HTHTTHTHHHTHTHH HHTTHHHTTTTTT
[29] flip: 141622752
[29] verb: THTTTTHHHTTTTHH HHHHTHHHHTTTTT
[30] flip: 299941248
[30] verb: THTTTHHHHTTTTTH THHHHTHHTTTTTTT
[31] flip: 1781985408
[31] verb: HHTHTHTTTHHTHHT HHHHTTTTHTTTTTT T
[32] flip: 3541639168
[32] verb: HHTHTTHHTTTHHTT HTTHTTTTTTTTTTT TT
[33] flip: 5060871680
[33] verb: HTTHTHHTHHTHTTH HTHHTTTHHTTTTTT TTT
[34] flip: 16940951552
[34] verb: HHHHHHTTTHHHTTT THTTHHTHTTTTTTT TTTT
[35] flip: 31300495360
[35] verb: HHHTHTTHTTHHTHT THHHHTHTHTTTTTT TTTTT
[36] flip: 15590113280
[36] verb: TTHHHTHTTTTHTTH HHHHTTHTTTTTTTT TTTTTT
[37] flip: 95535947776
[37] verb: HTHHTTTHHHHHTTH HTTTHTHHHTTTTTT TTTTTTT
[38] flip: 269381238784
[38] verb: HHHHHTHTHHHTTTT HTHHHHHHTTTTTTT TTTTTTTT
[39] flip: 134102679552
[39] verb: TTHHHHHTTHHHTTH TTHTTHTTHTTTTTT TTTTTTTTT
[40] flip: 586999660544
[40] verb: HTTTHTTTHTHTHTH HHHHTHTTTTTTTTT TTTTTTTTTT
[41] flip: 233909387264
[41] verb: TTTHHTHHTTHHHTH HTTTTHTHHTTTTTT TTTTTTTTTTT
[42] flip: 4395471732736
[42] verb: HHHHHHHHHHTHHTT HHTHTTTHTTTTTTT TTTTTTTTTTTT
[43] flip: 5947706048512
[43] verb: HTHTHHTHTTTHHTT HHHTHHHTHTTTTTT TTTTTTTTTTTTT
[44] flip: 276266221568
[44] verb: TTTTTHTTTTTTTHT HTTHTHHTTTTTTTT TTTTTTTTTTTTTT
[45] flip: 20237481148416
[45] verb: HTTHTTHHTTHHHHH HTTHHHHHHTTTTTT TTTTTTTTTTTTTTT
[46] flip: 7040550305792
[46] verb: TTTHHTTHHTTHHHT HTTTTTHHTTTTTTT TTTTTTTTTTTTTTT T
[47] flip: 14499146891264
[47] verb: TTTHHTHTTHTHHHH HHTHHTTTHTTTTTT TTTTTTTTTTTTTTT TT
[48] flip: 224865965572096
[48] verb: HHTTHHTTHTTTTTH HHTHHTTTTTTTTTT TTTTTTTTTTTTTTT TTT
[49] flip: 160148156841984
[49] verb: THTTHTTTHHTHTTH HHTHHTTHHTTTTTT TTTTTTTTTTTTTTT TTTT
[50] flip: 51396397236224
[50] verb: TTTTHTHHHTHTHHH HHTHTHTHTTTTTTT TTTTTTTTTTTTTTT TTTTT

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.WriteLi ne("[" & x & "] flip: " & f.ToString)
Console.WriteLi ne("[" & 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 ArithmeticExcep tion
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(ByV al 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!

[Larry Lard]

bo************@ 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. 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.NextByte s, which fills a byte array
with random bits. (If you want cryptographical ly strong random bits,
use a Cryptography.Ra ndomNumberGener ator)

--
Larry Lard
Replies to group please

[Andrew Morton]

bo************@ 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.R NGCryptoService Provider.GetByt es

Andrew

[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/?u...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.
<bo************ @gmail.com> escribió en el mensaje news:11******** ************@t3 1g2000cwb.googl egroups.com...
| (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: HHHHTHHTTHTTTTH H
| [17] flip: 114222
| [17] verb: HHTHHHHHTTTHTHH HT
| [18] flip: 14742
| [18] verb: TTTTHHHTTHHTTHT HHT
| [19] flip: 497841
| [19] verb: HHHHTTHHTTTHTHH TTTH
| [20] flip: 381701
| [20] verb: THTHHHTHTTHHTTT TTHTH
| [21] flip: 1100729
| [21] verb: HTTTTHHTTHTHHHT HHHTTH
| [22] flip: 3217500
| [22] verb: HHTTTHTTTHHTTTT HTHHHTT
| [23] flip: 448828
| [23] verb: TTTTHHTHHTHHTTH TTHHHHTT
| [24] flip: 9939800
| [24] verb: HTTHTHHHHTHTHTH HTHTHHTTT
| [25] flip: 15726966
| [25] verb: THHHTHHHHHHHHHT THTHHHTHHT
| [26] flip: 20009544
| [26] verb: THTTHHTTTHTHTHT THTTHTTHTTT
| [27] flip: 83576936
| [27] verb: HTTHHHHHTHHTHTT HTTTTHHTHTTT
| [28] flip: 173898176
| [28] verb: HTHTTHTHHHTHTHH HHTTHHHTTTTTT
| [29] flip: 141622752
| [29] verb: THTTTTHHHTTTTHH HHHHTHHHHTTTTT
| [30] flip: 299941248
| [30] verb: THTTTHHHHTTTTTH THHHHTHHTTTTTTT
| [31] flip: 1781985408
| [31] verb: HHTHTHTTTHHTHHT HHHHTTTTHTTTTTT T
| [32] flip: 3541639168
| [32] verb: HHTHTTHHTTTHHTT HTTHTTTTTTTTTTT TT
| [33] flip: 5060871680
| [33] verb: HTTHTHHTHHTHTTH HTHHTTTHHTTTTTT TTT
| [34] flip: 16940951552
| [34] verb: HHHHHHTTTHHHTTT THTTHHTHTTTTTTT TTTT
| [35] flip: 31300495360
| [35] verb: HHHTHTTHTTHHTHT THHHHTHTHTTTTTT TTTTT
| [36] flip: 15590113280
| [36] verb: TTHHHTHTTTTHTTH HHHHTTHTTTTTTTT TTTTTT
| [37] flip: 95535947776
| [37] verb: HTHHTTTHHHHHTTH HTTTHTHHHTTTTTT TTTTTTT
| [38] flip: 269381238784
| [38] verb: HHHHHTHTHHHTTTT HTHHHHHHTTTTTTT TTTTTTTT
| [39] flip: 134102679552
| [39] verb: TTHHHHHTTHHHTTH TTHTTHTTHTTTTTT TTTTTTTTT
| [40] flip: 586999660544
| [40] verb: HTTTHTTTHTHTHTH HHHHTHTTTTTTTTT TTTTTTTTTT
| [41] flip: 233909387264
| [41] verb: TTTHHTHHTTHHHTH HTTTTHTHHTTTTTT TTTTTTTTTTT
| [42] flip: 4395471732736
| [42] verb: HHHHHHHHHHTHHTT HHTHTTTHTTTTTTT TTTTTTTTTTTT
| [43] flip: 5947706048512
| [43] verb: HTHTHHTHTTTHHTT HHHTHHHTHTTTTTT TTTTTTTTTTTTT
| [44] flip: 276266221568
| [44] verb: TTTTTHTTTTTTTHT HTTHTHHTTTTTTTT TTTTTTTTTTTTTT
| [45] flip: 20237481148416
| [45] verb: HTTHTTHHTTHHHHH HTTHHHHHHTTTTTT TTTTTTTTTTTTTTT
| [46] flip: 7040550305792
| [46] verb: TTTHHTTHHTTHHHT HTTTTTHHTTTTTTT TTTTTTTTTTTTTTT T
| [47] flip: 14499146891264
| [47] verb: TTTHHTHTTHTHHHH HHTHHTTTHTTTTTT TTTTTTTTTTTTTTT TT
| [48] flip: 224865965572096
| [48] verb: HHTTHHTTHTTTTTH HHTHHTTTTTTTTTT TTTTTTTTTTTTTTT TTT
| [49] flip: 160148156841984
| [49] verb: THTTHTTTHHTHTTH HHTHHTTHHTTTTTT TTTTTTTTTTTTTTT TTTT
| [50] flip: 51396397236224
| [50] verb: TTTTHTHHHTHTHHH HHTHTHTHTTTTTTT TTTTTTTTTTTTTTT TTTTT
|
| >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.WriteLi ne("[" & x & "] flip: " & f.ToString)
| Console.WriteLi ne("[" & 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 ArithmeticExcep tion
| 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(ByV al 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!

[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.WriteLi ne(s)
next

and with System.Security .Cryptography.R NGCryptoService Provider.GetByt es
your throws would be really random!

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

Klaus

[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 >(highestValu e)

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!

[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!

[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!

[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_Clic k(ByVal sender As System.Object, ByVal e As System.EventArg s) Handles butMonedas.Clic k

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.

<bo************ @gmail.com> escribió en el mensaje news:11******** **************@ t31g2000cwb.goo glegroups.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!

[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!