Generating random numbers
Wayne Robinson
That's fine. But how do I make sure that no two numbers are ever the same???
Any help would be greatly appreciated!
Dave Hawley
I have a fun little Function that you could use: Click the link below for
full easy instructions if are unsure of how to use in the Worksheet.
http://www.ozgrid.com/VBA/RandomNumbers.htm
Function RandLotto(Bottom As Integer, Top As Integer, Amount As Integer)
Dim iNum As String
Dim strNum As String
Dim i As Integer
Application.Volatile
iNum = Int((Top - Bottom + 1) * Rnd + Bottom)
For i = 1 To Amount
strNum = Trim(strNum & " " & iNum)
Do Until InStr(1, strNum, iNum) = 0
iNum = Int((Top - Bottom + 1) * Rnd + Bottom)
Loop
Next i
RandLotto = strNum
End Function
--
Kind Regards
Dave Hawley
www.MicrosoftExcelTraining.com
www.OzGrid.com
FREE EXCEL NEWSLETTER
http://www.ozgrid.com/News/2home.htm
"Wayne Robinson" <wayner...@bigpond.com> wrote in message
news:M9US8.22710$Hj3....@newsfeeds.bigpond.com...
Wayne Robinson
Neal
Neal
"Wayne Robinson" <wayner...@bigpond.com> wrote in message
news:M9US8.22710$Hj3....@newsfeeds.bigpond.com...
Dave Hawley
generator.
--
Kind Regards
Dave Hawley
www.MicrosoftExcelTraining.com
www.OzGrid.com
FREE EXCEL NEWSLETTER
http://www.ozgrid.com/News/2home.htm
"Neal" <nbla...@clear.net.nz> wrote in message
news:eB6aEmnHCHA.2472@tkmsftngp11...
Neal
Cheers, Neal
"Dave Hawley" <Dav...@OzGrid.com> wrote in message
news:5nVS8.4$tW6....@vicpull1.telstra.net...
Dave Hawley
random. Once we know in the sequence where the first number comes from, it
becomes possible to predict them (if you could be bothered). Basically a
computer must do as it is instructed and so cannot be truly random.
--
Kind Regards
Dave Hawley
www.MicrosoftExcelTraining.com
www.OzGrid.com
FREE EXCEL NEWSLETTER
http://www.ozgrid.com/News/2home.htm
"Neal" <nbla...@clear.net.nz> wrote in message
news:OMYjOopHCHA.2512@tkmsftngp08...
Chip Pearson
generators", and do not produce truly random sequences of numbers. They produce
sequences that are "random enough" for the vast majority of applications.
However, the sequences are predictable and reproducable, given knowledge of
the algorithm and the "starting number" called the "seed".
For example, you can get Excel to repeat a sequence of random numbers with code
like the following:
Dim N As Long
Rnd -1
Randomize 1
For N = 1 To 100
Cells(N, 1).Value = Rnd
Next N
Rnd -1
Randomize 1
For N = 1 To 100
Cells(N, 2).Value = Rnd
Next N
This generally doesn't matter, but does have implications in high end encryption
system, like those used by governments. The National Security Agency, for
example, uses fluctations in the cosmic background radiation (produced by quatum
effects) to get their truely random numbers. Quantum effects are truly random
(in the theoretical sense), and are what the experts like to use.
--
Cordially,
Chip Pearson
Microsoft MVP - Excel
Pearson Software Consulting, LLC
www.cpearson.com ch...@cpearson.com
"Neal" <nbla...@clear.net.nz> wrote in message
news:OMYjOopHCHA.2512@tkmsftngp08...
Vasant Nanavati
I agree with you as far as computers are concerned. But real life
abounds with random number generators; for example, a roulette wheel, a
throw of a die, the "cents" part of a large company's bank balance at
the end of each business day. Not being a mathematician, I'll even go
out on a limb and say that any group of consecutive digits in the
decimal approximation of Pi would be random or close to it, even though
I don't imagine this is mathematically provable.
--
Regards,
Vasant.
**No direct emails please--keep discussion in newsgroup.**
"Dave Hawley" <Dav...@OzGrid.com> wrote in message
news:5nVS8.4$tW6....@vicpull1.telstra.net...
Dave Hawley
Yes I should have stated the word "computer" right from the start. The use
of the term "Random number generator" was supposed to imply that.
Re; throw of a die
Ohhhh, I know all about that :o(
Is it really random when I loose every single time? It seems like I
consistently loose when I have a big dollar amount riding and win when I
have a pittance, this can't be random :o)
RE "cents" part of a large company's bank balance at the end of each
business day.
Unless your WorldCom, then you just cook the books to suit :o)
--
Kind Regards
Dave Hawley
www.MicrosoftExcelTraining.com
www.OzGrid.com
FREE EXCEL NEWSLETTER
http://www.ozgrid.com/News/2home.htm
"Vasant Nanavati" <vas...@aol.com> wrote in message
news:#yxW8WxHCHA.2572@tkmsftngp11...
Vasant Nanavati
>>Is it really random when I loose every single time? It seems like I
consistently loose when I have a big dollar amount riding and win when I
have a pittance, this can't be random<<
Been there, done that,, with same results as yours!
>>Unless your WorldCom, then you just cook the books to suit <<
I don't think they know what "cents" are...too busy misplacing billions
of dollars.
--
Regards,
Vasant.
**No direct emails please--keep discussion in newsgroup.**
"Dave Hawley" <Dav...@OzGrid.com> wrote in message
news:ox9T8.5$O%6.3...@vicpull1.telstra.net...
Sandy Mann
I am not trying to be a smart-ass here - I just trying to learn good
programming techniques through these NG's - and I know that your function is
just a bit of fun but it seems, to me at least, to have a fatal flaw when
the number of random numbers approaches the total of numbers available.
For example with numbers 1 to 20, when you ask for 16 random numbers, (i.e.
*Amount*)' Excel seem to freeze. I assume that the reason is that it ends
up going through an endless loop. I think what is happening is that when 12
is selected then when either 1 or 2 is selected, the InStr function will
find then in the number 12 ans so will reject them. (i.e. Running the
function numerous times I noticed that if 12 is selected early then neither
1 nor 2 will be but if 1 and 2 are selected then 12 can still appear in the
list.) It must be that the odds are that the numbers 16 through 20 have
already been selected and so when 1, 2, 6, 7, 8 or 9 are selected, the InStr
function will find that number and so will continue the loop without end
because it still requires another number. At least when I added a counting
variable to see how many times the loop had executed I got a message box at
20,000,000 (I didn't have the patients to wait any longer.)
Of course I could be wrong about the above but I would value your comments
to further my knowledge of Excel & VBA
Kind Regards
Sandy
"Dave Hawley" <Dav...@OzGrid.com> wrote in message
news:imUS8.40$0O6....@vicpull1.telstra.net...
J.E. McGimpsey
number of single digits in the range Bottom to Top and Top-Bottom is
>=10. Of course, it's unusual for any lotto to have more than 9 picks,
so this would happen rarely in Lotto picking. However the routine below
generalizes this a bit and returns up to Bottom-Top + 1 (i.e., all)
numbers:
Public Function Rands(Bottom As Integer, Top As Integer, _
Amount As Integer) As String
Dim iArr As Variant
Dim i As Integer
Dim r As Integer
Dim temp As Integer
Application.Volatile
ReDim iArr(Bottom To Top)
For i = Bottom To Top
iArr(i) = i
Next i
For i = Top To Bottom + 1 Step -1
r = Int(Rnd() * (i - Bottom + 1)) + Bottom
temp = iArr(r)
iArr(r) = iArr(i)
iArr(i) = temp
Next i
For i = Bottom To Bottom + Amount - 1
Rands = Rands & " " & iArr(i)
Next i
Rands = Trim(Rands)
End Function
In article <uwNIHS7HCHA.2012@tkmsftngp13>, Sandy Mann
Dana DeLouis
one needs different techniques based on different situations.
If one needed to pick 999 out of 1,000 numbers, then doing a search on
previous numbers would take a long time. A loop would take a long time as
it tried to pick a number that was not already used. Loading the 1,000
numbers, and shuffling would probably be the best way. On the other hand,
if you had to pick 100 numbers out of 1,000,000, then building a large
array, and then sorting that array, would not be the best idea either.
I like to use the following general technique. It handles the problem of a
large pool to choose from. (not building a large array to shuffle). It is
also pretty fast for "Lotto" size problems.
Although it has a programming loop :>( ,most of the "hard" looping is
done by Excel as it checks previous entries.
As a side note...I don't believe a collection can be used as a 1 dimensional
array when finished. (example: Join / Split). That is why the last
"for-loop." I just hate that last loop! <vbg> ..and I have tried
everything!
I removed some code, and removed error checking...
(16 numbers between 1 & 20)
Debug.Print PickNumbers(16, 1, 20)
8,13,15,4,2,5,20,14,19,6,16,12,3,18,10,1
Function PickNumbers(N As Long, Low As Long, High As Long) As String
'// By: Dana DeLouis
Dim grp As New Collection
Dim v As Variant
Dim j As Long
Dim s As String
On Error Resume Next
Do While grp.Count < N
s = CStr(Int(Rnd * (High - Low + 1)) + Low)
grp.Add s, s
Loop
'// Basically done. Do what you want here...
ReDim v(1 To grp.Count)
For j = 1 To grp.Count: v(j) = grp(j): Next
PickNumbers = Join(v, ",")
End Function
--
Dana DeLouis
Windows XP & Office XP
= = = = = = = = = = = = = = = = =
"J.E. McGimpsey" <jemcg...@mvps.org> wrote in message
news:300620021308012025%jemcg...@mvps.org...
Dave Hawley
I am glad you bought this up as I wrote the code about a year ago and it was
for a user wanting non-repeating random numbers between 1 and 10. I hade
forgotten about this :o)
I will revisit this and see if I can loosen it up somewhat, starting with
Jims suggestion.
--
Kind Regards
Dave Hawley
www.MicrosoftExcelTraining.com \ www.OzGrid.com
Get 8 Add-ins in one! For less than the price of 1
http://www.ozgrid.com/Services/AddinExamples.htm
FREE EXCEL NEWSLETTER
http://www.ozgrid.com/News/2home.htm
"Sandy Mann" <sand...@tiscali.co.uk> wrote in message
news:uwNIHS7HCHA.2012@tkmsftngp13...
Dave Hawley
You are right, the original Function was written to work on numbers between
1 and 10 and I hade forgotten that. I have updated this code on my site with
a thank you to you for modifying it:
http://www.ozgrid.com/VBA/RandomNumbers.htm
--
Kind Regards
Dave Hawley
www.MicrosoftExcelTraining.com \ www.OzGrid.com
Get 8 Add-ins in one! For less than the price of 1
http://www.ozgrid.com/Services/AddinExamples.htm
FREE EXCEL NEWSLETTER
http://www.ozgrid.com/News/2home.htm
"J.E. McGimpsey" <jemcg...@mvps.org> wrote in message
news:300620021308012025%jemcg...@mvps.org...
J.E. McGimpsey
My few tests showed a 99.8% improvement using your code over mine for
the 100/1000000 scenario (after changing Ints to Longs), ~50%
improvement for smaller lotto-type samples (e.g., 7/49), to a 400%
degradation with larger proportion samples (e.g., 42/49).
In article <uNl7mdHICHA.1728@tkmsftngp10>, Dana DeLouis
Myrna Larson
mows
I don't know if it is of interest, but we can get a rought idea of how
efficient your code is. Stripping it down we get something like
for i = 1 to k
do
{Choose a number}
Repeat Until {Choice not been out before}
next i
The cost of the main loop must be at least k. The probability of a repeat
is (i - 1) / N, where N is the total number of unique choices. i - 1
because there will not be a repeat the first time around. The probability
that the length of the inner loop is x, is the probability that there were
(x - 1) repeats and 1 unique. Therefore ....
p(x) = a^(x - 1)) * (1 - a)
where a = (i - 1) / N
So, the expected length is
E{x}=Sum[x p(x), {x, 1, Infinity}] = N / (N - (i - 1)
Introducing H(n) for Harmonic numbers.
e.g. H(4) = 1 / 1 + 1 / 2 + 1 / 3 + 1 / 4
The total cost for the outer loop is the sum of E{x} through 1 to k
= N * Sum[E{x},{x,1,k}] = N * Sum [1 / (N - (i - 1)),{i,1,k}]
= N * (H(N) - H(N - k))
(Here, N = High-Low+1 and k = n in your code)
For your example PickNumbers(16, 1, 20) we would expect to need about 30
loops to get the 16 numbers. It may be quicker here to do something like
PickNumbers(4, 1, 20), which takes only 4.3 loops and select those not
chosen. With this in mind, you will only ever need to do a maximun of
PickNumbers(X/2, 1, X),. which needs about X Log 2 loops.
If you tried to something like PickNumbers(100, 1, 100), then
expect to wait over 500 loops. For the U.K lottery PickNumbers(6, 1, 49)
will on average need 6.33 loops.
In excel speak, if C3 = High, C2 = low and C1 = n then
=(C3-C2+1) * (Harmonic(C3-C2+1)-Harmonic((C3-C2+1)-C1))
returns the expected number of loops; ie the value the counter in this
snippet from you code
> Do While grp.Count < n
> counter = counter + 1
> s = CStr(Int(Rnd * (High - Low + 1)) + Low)
> grp.Add s, s
> Loop
Function Harmonic(n)
Dim B(7)
B(0) = 0.577215664901533 'Euler's Gamma
B(1) = -1 / 12
B(2) = 1 / 120
B(3) = -1 / 252
B(4) = 1 / 240
B(5) = -1 / 132
B(6) = 691 / 32760 '"adjusted " Bernoulli numbers
B(7) = -1 / 12
If n > 10 Then
k = 8 'adjust number of cycles
If n > 1000 Then k = 4
If n > 6000000 Then k = 1
z = n * n
For i = 1 To k
h = h / z + B(k - i)
Next
Har = h + Log(n) + 1 / 2 / n
Else
For i = 1 To n
h = h + 1 / i 'add up reciprocals for small n
Next
Har = h
End If
Harmonic = Har
End Function
To get the feel, Here a few Harmonic Numbers
n H(n)
0 0
1 1
10 2.9290
100 5.1874
1000 7.4855
10000 9.7876
100000 12.09
1000000 14.3927
mows
ExcelXP/WinXP
Eero
mows wrote in message ...
The following array-formula does the same job:
=IF(A1<65537,SUM(1/ROW(INDIRECT("1:"&A1))),LN(A1)+0.577215664901533)
Dana DeLouis
a good problem from a "program timing" point of view for a while. The
problem of picking 42 out of 49 size problems I find is very interesting.
Although there are a few pretty looking solutions, the timing involved in
every effort is actually slower then the bruit force method of building
every number, and sorting. I think J.E.'s method is actually faster for
these size problems. I have been trying to come up with a formula to
measure expected attempts like those that you have posted for a long time
without success. So, thanks!!
I lost you on your formula though. I had to follow along using Mathematica.
With "a" set like you mentioned.your formula
Simplify[Sum[x*a^(x - 1)*(1 - a), {x, 1, Infinity}]]
Did reduce to the following.
n/(1 - i + n)
With Expectation "e" set.
e[i_, n_] := Plus @@ Table[n/(n - x + 1), {x, i}]
I tried the 3 solutions that you mentioned. I get the same answers.
e[4, 20] -> 4.340213278293773
e[16, 20] -> 30.288126476206973
e[100, 100] -> 518.737751763962
I really lost you on the Harmonic Table though. I will have to study it
some more. I cannot figure out what you are doing for large numbers. I
tested
your data quickly, and the numbers agree.
Table[{10^n, Plus @@ Sum[1./z, {z, 10^n}]}, {n, 6}]
{10., 2.9289682539682538},
{100., 5.187377517639621},
{1000., 7.485470860550343},
{10000., 9.787606036044345},
{100000., 12.090146129863282},
{1.*^6, 14.392726722864781}
I honestly cannot figure out how you, and now Euro, came up with your
equation. I do remember something Jay Petrulis wrote about a year ago.
Therefore, I took a guess and combined what you wrote with some other stuff.
For small sizes, this agrees with you numbers.
Function HowManyTrys(Pick As Long, N As Long) As Double
Dim SoFar As Double
Dim j As Long
For j = N - Pick + 1 To N
SoFar = SoFar + 1 / WorksheetFunction.HypGeomDist(1, 1, j, N)
Next
HowManyTrys = SoFar
End Function
Sub TestIt()
Debug.Print HowManyTrys(4, 20)
Debug.Print HowManyTrys(16, 20)
Debug.Print HowManyTrys(100, 100)
'//and of course...
Debug.Print HowManyTrys(42, 49)
End Sub
Anwers I got were.
4.34021327829377
30.288126476207
518.737751763962
92.4310615781418
Anyway, thanks again.
--
Dana DeLouis
Windows XP & Office XP
= = = = = = = = = = = = = = = = =
"mows" <mo...@mopar.freeserve.co.uk> wrote in message
news:exCGY9RICHA.2132@tkmsftngp10...
Dana DeLouis
eliminating the last loop.
> For i = Bottom To Bottom + Amount - 1
> Rands = Rands & " " & iArr(i)
> Next i
> Rands = Trim(Rands)
by using something like this...
ReDim Preserve iArr(Bottom To Bottom + Amount - 1)
Rands = Join(iArr, Space(1))
However, this is actually slower. The timing of the ReDim statement is
slower than I initially thought. :>0
There are so many interesting timing questions. Another one would be the
Filter function, instead of ReDim. The number of loops is less, since you
only want to mark 43-49 as being deleted.(for the 42 / 49 problem.).
Unfortunately, this too is slower. :>(
For i = Bottom + Amount To Top
iArr(i) = Chr(255)
Next
iArr = Filter(iArr, Chr(255), False)
Rands = Join(iArr, Space(1))
--
Dana
<snip>
J.E. McGimpsey
have a native Join (I wrote one myself for compatibility, but it's
understandably slower than the built-in function and the loop). Wonder
why ReDim Preserve is slower - I'd think it would just be a matter of
changing a pointer or two.
In article <eYR5WSWICHA.1124@tkmsftngp10>, Dana DeLouis
mows
The Harmonic function was written in the days of the 80286 for QBasic. I did
not have the option to add up any numbers in a large loop, hence the long
winded code that will only do a few loops. Eero's code is more
appropriate for Excel. It is based upon the fact that H(n) = Log(n) + Eulers
constant + O(1/n). The first 2^16 numbers are simply added up, above that
it uses Log(n) + Euler's constant, which is certainly near enough for what
we are doing here. Harmonic() goes a bit further, H(n) = Log(n) + Eulers
constant + 1/(2n) - 1/(12n^2) + 1/(120n^4) & etc. The constants being the
Bernoulli numbers. Have a peek here
http://www.mathpages.com/home/kmath284.htm
http://mathworld.wolfram.com/HarmonicNumber.html
although being a Mathematica person, I am sure you will know this last site
well.
> I lost you on your formula though. I had to follow along using
>Mathematica.With "a" set like you mentioned.your formula
>
> Simplify[Sum[x*a^(x - 1)*(1 - a), {x, 1, Infinity}]]
>
> Did reduce to the following.
> n/(1 - i + n)
Here
Sum[x*a^(x - 1)*(1- a), {x, 1, Infinity}]
taking a outside the sum
=Sum[x*a^x*(1- a), {x, 1, Infinity}] * (1/a)
now take (1- a) outside the sum
=Sum[x*a^x, {x, 1, Infinity}] * (1/a)*(1-a)
=(1-a)*(1/a) * a/(a-1)^2 = 1/(1-a)
and so E{x}= n/(1- i + n)
The total cost is now
= Sum[E{x},{x,1,k}] = Sum [N / (N - i + 1),{i,1,k}]
= N* Sum [1 / (N - i + 1),{i,1,k}]
= N* Sum [1 / j, {j, N - k + 1, N}]
and here we see how Harmonic numbers creap in.
> With Expectation "e" set.
> e[i_, n_] := Plus @@ Table[n/(n - x + 1), {x, i}]
I notice that Mathematica comes up with
n (-PolyGamma[0, k - n] + PolyGamma[0, -n])
for n* Sum [1 / (n - i + 1), {i, 1, k}], which then does not like integers!
Mathematica4 has HarmonicNumber, so you could do
e[k_, n_] := n *(HarmonicNumber[n] - HarmonicNumber[n - k])
N[e[4, 20], 17] ---> 4.3402132782937736
e[k_, n_] := n* Sum [1 / (n - i + 1), {i, 1, k}]
also seems fine.
>The problem of picking 42 out of 49 size problems I find is very
>interesting.
Or not picking 7 / 49
> Function HowManyTrys(Pick As Long, N As Long) As Double
> Dim SoFar As Double
> Dim j As Long
> For j = N - Pick + 1 To N
> SoFar = SoFar + 1 / WorksheetFunction.HypGeomDist(1, 1, j, N)
> Next
> HowManyTrys = SoFar
> End Function
Spot on -- but perhaps a bit complex as for integer x and y
=HYPGEOMDIST(1,1,x,y) = x / y
From the formula above, N* Sum [1 / j, {j, N - k + 1, N}]
we can simply do ---
Function HowManyTrys2(Pick As Long, N As Long) As Double
Dim SoFar As Double
Dim j As Long
For j = N - Pick + 1 To N
SoFar = SoFar + 1 / j
Next
HowManyTrys2 = N * SoFar
End Function
Using the Harmonic function we could also do ---
Function HowManyTrys3(Pick As Long, N As Long) As Double
HowManyTrys3 = N * (Harmonic(N) - Harmonic(N - Pick))
End Function
mows
Dana DeLouis
For small size problems, I am able to understand the problem slight better
with the HypGeomDist( ) function.
Realizing that 3 of the 4 variables for HypGeomDist are constants, I think
the VBA function could be reduced even further.
Here's my new attempt:
Function HowManyTrys(Pick As Long, N As Long) As Variant
Dim SoFar As Variant
Dim j As Long
For j = N - Pick + 1 To N
SoFar = SoFar + 1 / (j / N)
Next
HowManyTrys = SoFar
End Function
...and I get the same answers...
4.34021327829377
30.288126476207
518.737751763962
92.4310615781418
As a fun side note only, we can pretend we're using MM, and get more digits
with the following...
Function HowManyTrys(Pick As Long, N As Long) As Variant
Dim SoFar As Variant
Dim One As Variant
One = CDec(1)
Dim j As Long
For j = N - Pick + 1 To N
SoFar = SoFar + One * N / j
Next
HowManyTrys = SoFar
End Function
I get the same numbers out to about 28 digits (Checked w/ Mathematica)
4.3402132782937736498108015135
30.288126476206971563008714712
518.73775176396202608051176755
92.43106157814182782046311784
I didn't realize earlier, but should have, that HarmonicNumber was built in
to MM.
Timing[Table[{10^j, HarmonicNumber[10.^j]}, {j, 10}]]
{0.*Second,
10, 2.9289682539682538,
100, 5.1873775176396215,
1000, 7.485470860550345,
10000, 9.787606036044384,
100000, 12.09014612986343,
1000000, 14.392726722865724},
10000000, 16.695311365859855,
100000000, 18.997896413853898,
1000000000, 21.300481502347946,
10000000000, 23.603066594891988
--
Dana
= = = = = = = = = = = = = = = = =
"mows" <mo...@mopar.freeserve.co.uk> wrote in message
news:e8dB3dcICHA.2664@tkmsftngp10...
> Dana,
>
> The Harmonic function was written in the days of the 80286 for QBasic. I
did
> not have the option to add up any numbers in a large loop, hence the long
> winded code that will only do a few loops. Eero's code is more
> appropriate for Excel. It is based upon the fact that H(n) = Log(n) +
Eulers
> constant + O(1/n). The first 2^16 numbers are simply added up, above that
> it uses Log(n) + Euler's constant, which is certainly near enough for what
> we are doing here. Harmonic() goes a bit further, H(n) = Log(n) + Eulers
> constant + 1/(2n) - 1/(12n^2) + 1/(120n^4) & etc. The constants being the
> Bernoulli numbers. Have a peek here
> http://www.mathpages.com/home/kmath284.htm
> http://mathworld.wolfram.com/HarmonicNumber.html
> although being a Mathematica person, I am sure you will know this last
site
> well.
<snip>
Tushar Mehta
'generates' too many random numbers. Second, is the output
concatenation loop.
To optimize the code for 'minimal' generation,
replace the main For loop with
For i = Top To Top - Amount + 1 Step -1
and the output loop with
For i = Top To Top - Amount + 1 Step -1
Also, it is not clear why the output is provided as a string. It would
seem that an array would be more useful to the caller. In fact, for
larger sample sizes (100,000 out of 1,000,000), both Dana's code and
your code take so long in the output phase that I have never let either
run to completion! :(
In the limited tests that I did, for practical problems the version
below is faster by magnitudes than any other version. With min=1, max=
1,000,000, the code took 0.3 seconds to generate 1, 1,000, or 10,000
numbers, 0.55 seconds for 100,000 numbers and 2.6 seconds for 1,000,000
numbers.
By comparison, generating 10,000 numbers took 6 seconds with Dana's
code, 8 seconds with your code optimized to stop after 'amount' numbers,
and 12 seconds with the unoptimized code.
The only time that Dana's code will be faster than the code below is
when one wants few random numbers from a very large population.
Generating 1 number from 1,000,000 takes 0 seconds with Dana's code and
0.3 seconds with the code below).
Public Function TMOptRands(Bottom As Long, Top As Long, _
Amount As Long) As Variant
Dim i As Long, r As Long, temp As Long
Application.Volatile
ReDim iArr(Bottom To Top) As Long
For i = Bottom To Top: iArr(i) = i: Next i
For i = 1 To Amount
r = Int(Rnd() * (Top - Bottom + 1 - (i - 1))) _
+ (Bottom + (i - 1))
temp = iArr(r): iArr(r) = iArr(Bottom + i - 1): _
iArr(Bottom + i - 1) = temp
Next i
ReDim Preserve iArr(Bottom To Bottom + Amount - 1)
TMOptRands = iArr
End Function
--
Regards,
Tushar Mehta
www.tushar-mehta.com
Microsoft MVP -- Excel
--
In <300620022129035704%jemcg...@mvps.org>, J.E. McGimpsey
<jemcg...@mvps.org> wrote
J.E. McGimpsey
In article <MPG.178ba7a1b...@msnews.microsoft.com>, Tushar
Mehta <ng_p...@bigfoot.com> wrote:
> There are two reasons your method is slower, J.E. First, it
> 'generates' too many random numbers. Second, is the output
> concatenation loop.
>
> To optimize the code for 'minimal' generation,
>
> replace the main For loop with
> For i = Top To Top - Amount + 1 Step -1
>
> and the output loop with
> For i = Top To Top - Amount + 1 Step -1
I had rejected this approach for some reason that escapes me now.
Thanks to you, it is glaringly obvious that it is preferred. <slap to
forehead!>
> Also, it is not clear why the output is provided as a string. It
> would seem that an array would be more useful to the caller.
I thought it was the OP's specification, but looking back I see it was
introduced by D. Hawley. Curious, though OP never said how he wanted
results returned.
> In fact, for larger sample sizes (100,000 out of 1,000,000), both
> Dana's code and your code take so long in the output phase that I
> have never let either run to completion! :(
I did 100 out of 1,000,000. Since I randomized the whole array, I don't
expect it would take much longer to do 100,000 (that is, if there
weren't a 32K limit on string size). I did brew a pot of coffee and
read a section of the paper, however.
Your function is now firmly ensconced in my library.
mows
> Realizing that 3 of the 4 variables for HypGeomDist are constants, I think
> the VBA function could be reduced even further.
> Here's my new attempt:
>
> Function HowManyTrys(Pick As Long, N As Long) As Variant
> Dim SoFar As Variant
> Dim j As Long
> For j = N - Pick + 1 To N
> SoFar = SoFar + 1 / (j / N)
> Next
> HowManyTrys = SoFar
> End Function
This is effectively equivalent to HowManyTrys2()
Function HowManyTrys2(Pick As Long, N As Long) As Double
Dim SoFar As Double
Dim j As Long
For j = N - Pick + 1 To N
SoFar = SoFar + 1 / j
Next
HowManyTrys2 = N * SoFar
End Function
the difference being that you are dividing / multiplying by N on every loop,
whereas HowManyTrys2() does a single multiplication at the end.
We can go even further and work out the standard deviation.
PickNumbers(100,1,100) --- 519 loops, s.d. 125.822
PickNumbers(400,1,1000) ---510 loops, s.d. 12.5
PickNumbers(42,1,49) --- 92.43 loops, s.d. 13.3689
From before we have
E{x}=Sum[x p(x), {x, 1, Infinity}] = N / (N - i + 1)
E{x^2}=Sum[x^2 p(x), {x, 1, Infinity}] = N (N + i - 1) / (N - i + 1)^2
Var{x} = E{x^2} - (E{x})^2 = N (i - 1) / (N - i + 1)^2
Summing Var{x} 1 through k we have ---
Standard deviation = Sqrt[N Sum[(i - 1) / (N - i + 1)^2, {i, 1, k}]]
In MM
sd[k_, n_] := Sqrt[n*Sum[(i - 1) / (n - i + 1)^2, {i, 1, k}]]
mows
ExcelXP/WinXP
Tushar Mehta
save the random values. This time, I switched to the lower portion
simply so that I could use REDIM to truncate the array and then assign
it to the function.
The time it took to concatenate the output in your code was a surprise
as was the time it took to access all the elements of the collection (in
Dana's code). I wonder how XL/VBA implements a collection. A linked
list, perhaps?
--
Regards,
Tushar Mehta
www.tushar-mehta.com
Microsoft MVP -- Excel
--
In <020720021245349034%jemcg...@mvps.org>, J.E. McGimpsey
<jemcg...@mvps.org> wrote