Interesting Challenge...

[Andrew Fergus]

Hi Everyone

I'm trying to come up with a (pseudo) random number generator (producing a 2 or 3 digit integer) and am curious about other peoples take on this issue. In particular what formula(s) you use or have tried, how long a run can you get before the formula repeats itself, the distribution of numbers and so forth.

The reason I'm asking is because I'm trying to introduce an apparent degree of randomness into a process without it actually being random. It requires the appearance of randomness but for the purposes of back-tracking etc I need to know the next number in the sequence given n instances of a sequence.

I've looked at lagged Fibonacci sequences and I can't get past about 200-300k records before the process repeats itself. I'd prefer a much higher number, if this is possible, so would appreciate any and all comments on this subject. I could use the product of two of my own sequences together (using different seeds) to come up with 4-5b combinations, but I'd prefer something a little more elegant, if possible.

I've done a bit of research and looked into the Blub Blum Shub technique but a) I'm stuck and b) I'm not sure what to make of the BBS technique. Any thoughts on that technique are also appreciated.

Thanks in advance
Andrew

 

[NateO]

I'm trying to come up with a (pseudo) random number generator (producing a 2 or 3 digit integer) and am curious about other peoples take on this issue. In particular what formula(s) you use or have tried, how long a run can you get before the formula repeats itself, the distribution of numbers and so forth.

Here's what I have used:

http://www.mrexcel.com/board2/viewtopic.php?p=969413#969413

Just change keyArr().

 

[Andrew Fergus]

Hi Nate and thanks for replying.

I had a quick look at your code and it looks like it is employing the Rnd function. I was trying to use my own custom Random function. The lagged Fibonacci sequence is almost doing what I want but I I might try using more digits in each 'lag'* and more 'lags' to see if I can get a longer run.

*A lag being the number of previous numbers in the sequence that I use to calculate the next (pseudo) random number.

But I like the look of your 'keyArr' variable and may use that technique elsewhere.

Thanks again
Andrew

 

[Bartek]

Hi,

Standard Excel Rnd generator has a cycle of 16.7M (2^24), which may be insufficient for some simulations. I sometimes use the following generator:

 Rseed = 16807 * (Rseed Mod 127773) - 2836 * Int(Rseed / 127773)
 If Rseed < 0 Then Rseed = Rseed + 2147483647

Rseed / 2147483647 gives you U(0, 1) distribution. Is has a cycle of 2.1 billion (2^31) and Rseed remains withing the range of long integer variable (you do not get overflow).

 

[erik.van.geit]

Hi,

this might generate some more ideas ...
You asked for 2 or 3 digits, but this one includes also the 1 digits 0 to 9.

I found a short formula which cycles through all # from 0 to 999 without any repeat. Unless I'm missing something ?
Right(41 * n + 1, 3)

Option Explicit

Sub test()
Dim seed As Long

seed = 20
MsgBox pseudo_random(seed), 64, "item #" & seed

End Sub

Function pseudo_random(m As Long)
'Erik Van Geit
'070115
'create # with 1 to 3 digits
'cycle = 1000: each seed between 1 and 1000 generates different #

Dim i As Long
Dim n As Long

n = 2 'or any number

    For i = 1 To m
    n = Right(41 * n + 1, 3)
    Next i
    
pseudo_random = n

End Function

Sub pseudo_random_list()
'proof that the cycle is 1000
Dim i As Long
Dim a As Variant

Const m = 1000
ReDim a(1 To m)

    For i = 1 To m
    a(i) = pseudo_random(i)
    Next i
    
    With Range("A1:A" & m)
    Range("A1:A" & m) = Application.Transpose(a)
    'count appearancies of each item
    Range("B1:B" & m) = "=COUNTIF(R1C1:R" & m & "C1,RC[-1])"
    'what is the maximum ?
    Range("C1") = "=MAX(RC[-1]:R[" & m - 1 & "]C[-1])"
    'well the MAX is 1 !!! which means all numbers got selected
    End With
    
End Sub

kind regards,
Erik

 

[Andrew Fergus]

Hi Bartek

Thanks for that. I will give it a go tonight and see how it goes. How did you decide on the values within the formula? Was it via experimentation or did you come across them somewhere?

Hi Erik

I think something was lost in translation. By 2 or 3 digits I meant numbers in the range 00 to 99 or 000 to 999 so thanks for 'reading between the lines'. An interesting approach - how did you know to use 41?

I noticed that if you use a seed of 1, then the final digit increments by 1 and every hundredth number goes like this : 001, 101, 201, 301 etc.

Thanks, Andrew

 

[erik.van.geit]

Hi, Andrew,

41 was my second try, just mathematical intuition ?
first I used 13 (combined with +1 -1 +7 -7)

in fact the drawback is every 100 you have some pattern, which is somehow related with the 1000-cycle ...

hmm
more experiments: the difference between A1 and A101 is often something like 100, 200, 60, 80 ...

rewrote the code a little to allow more easy experiments

Option Explicit

Sub test()
Dim seed As Long

seed = 20
MsgBox pseudo_random(seed), 64, "item #" & seed

End Sub

Function pseudo_random(m As Long)
'Erik Van Geit
'070115
'create # with 1 to 3 digits
'cycle = 1000: each seed between 1 and 1000 generates different #

Dim i As Long
Dim n As Long

n = 2 'or any number

    For i = 1 To m
    n = Right(331 * n + 1, 3)
    Next i
    
pseudo_random = n

End Function

Sub pseudo_random_list()
Dim i As Long
Dim a As Variant

Const m = 1000
ReDim a(1 To m)

    For i = 1 To m
    a(i) = pseudo_random(i)
    Next i
    
    Range("A1:A" & m) = Application.Transpose(a)
    
    'analysing a little ...
    
    'count appearancies of each item
    Range("B1:B" & m) = "=COUNTIF(R1C1:RC1,RC[-1])"
    'what is the first occurence of "2" ?
    'this will determine the cycle
    Range("C1") = "cycle"
    Range("C2") = "=MATCH(2,C[-1],0)-1"
    
    'difference with 10 rows difference, 25 rows, 50 & 100
    Range("D1") = "R11 - R1"
    Range("D2") = "=R11C1-R1C1"
    Range("E1") = "R26 - R1"
    Range("E2") = "=R26C1-R1C1"
    Range("F1") = "R51 - R1"
    Range("F2") = "=R51C1-R1C1"
    Range("G1") = "R101 - R1"
    Range("G2") = "=R101C1-R1C1"
    
End Sub

good luck :wink:
Erik

 

[Andrew Fergus]

Hi Erik

I haven't checked this but I'm guessing that so long as you used any prime number > 2 in place of the 41 or 331 then there is a good chance your technique may work.

If you extend your test to 4 digits, you will see the pattern repeat itself after every 1000'th item (first digit excluded).

Andrew

 

[Andrew Fergus]

Hi Bartek and thanks for your suggestion

I tried out your suggestion and found the following :

1 ) I used an initial seed value of 1
2) I tested 145m consecutive values without finding duplication (tested at a minimum of 3 consecutive values)
3) I took the last 3 digits at the 1m mark, and tested the next 144m records and only once was there are partial repeat (of 3 consecutive values) at the 86.4m mark - partial in the sense that yes I had 3 consecutive values which were the same from the 1m mark but the 4th value was then different so the cycle did not repeat itself.

So I think this formula, or a variant thereof, will be perfect. I can see why various values were selected but what is the logic behind the value 2836 - out of curiousity, why not something higher or lower?

Cheers
Andrew

 

[erik.van.geit]

If you extend your test to 4 digits, you will see the pattern repeat itself after every 1000'th item (first digit excluded).

of course my suggestion using very basic stuff didn't claim anything more then 2 or 3 digits
but I think your statement is not correct
of course you would need to extend the RIGHT-funtion to 4 digits

best regards,
Erik

EDIT: tested using same formula, replaced 3 by 4 to get 4 digits

    n = Right(331 * n + 1, 4)

cycle is 5000


for quicker testing you need to replace

    For i = 1 To m
    a(i) = pseudo_random(i)
    Next i

by

a(1) = Right(331 * 2 + 1, 4)
    For i = 2 To m
    a(i) = Right(331 * a(i) + 1, 4)
    Next i

and turn of automatic calculation if needed

for future reference (members who would read this later on)
anywy this is some very primitive testingcode
don't use it for large tests