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

bogusexception · Apr 19, 2006

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

Andrew Morton · Apr 19, 2006

(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

Larry Lard · Apr 19, 2006

(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)

=?iso-8859-1?Q?Jos=E9_Manuel_Ag=FCero?= · Apr 19, 2006

Klaus · Apr 19, 2006

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

bogusexception · Apr 19, 2006

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!

bogusexception · Apr 19, 2006

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 · Apr 19, 2006

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!

=?iso-8859-1?Q?Jos=E9_Manuel_Ag=FCero?= · Apr 20, 2006

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.

<[email protected]> escribió en el mensaje | 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 · Apr 20, 2006

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!

Andrew Morton · Apr 20, 2006

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

=?iso-8859-1?Q?Jos=E9_Manuel_Ag=FCero?= · Apr 20, 2006

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.

<[email protected]> escribió en el mensaje | 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!

Multiple coin flips in a single cell	7	Sep 12, 2005
Combining two macros	2	Jun 7, 2011
Scrabble Value calculation for Welsh words	0	Oct 19, 2021
Excel in Perl VIA OLE -- saving workbook(s)	2	Mar 17, 2006
Excel VBA	1	Mar 14, 2023
VBA - combinations	0	Aug 4, 2015
Workbooks.OpenText method help	3	Sep 30, 2014
Modify working code to expand the output.	5	Mar 13, 2014

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

bogusexception

Andrew Morton

Larry Lard

=?iso-8859-1?Q?Jos=E9_Manuel_Ag=FCero?=

Klaus

bogusexception

bogusexception

bogusexception

=?iso-8859-1?Q?Jos=E9_Manuel_Ag=FCero?=

bogusexception

Andrew Morton

=?iso-8859-1?Q?Jos=E9_Manuel_Ag=FCero?=

Ask a Question

Similar Threads