random number generator

Replies to This Discussion

Permalink Reply by Luis Fraguada on July 1, 2009 at 2:32am

Hello Tobias,
Digging a bit, I found this http://msdn.microsoft.com/en-us/library/system.random.aspx. I am assuming that the Random Number component is based on the .net random class... again its an assumption, but this page says:

Pseudo-random numbers are chosen with equal probability from a finite set of numbers. The chosen numbers are not completely random because a definite mathematical algorithm is used to select them, but they are sufficiently random for practical purposes. The current implementation of the Random class is based on Donald E. Knuth's subtractive random number generator algorithm. For more information, see D. E. Knuth. "The Art of Computer Programming, volume 2: Seminumerical Algorithms". Addison-Wesley, Reading, MA, second edition, 1981.

I hope that helps!
Luis

• ▶ Reply

Permalink Reply by Tobias Schwinn on July 1, 2009 at 10:16pm

Thank you Luis. I guess we don't usually think much about how random numbers are generated. But I think it is an interesting subject in its own right. The pattern that I created in the above definition using the default random class doesn't look similar to the two patterns in Daniels work (which has been done using processing) that are titled Knuth No1 and Knuth No2. I could contact Daniel for more specifics about the code and setup that he used. But that still wouldn't answer the question which algorithm is at work in Rhino/Grasshopper. BTW, I found a vb.net implementation of the Mersenne Twister on the web. Maybe, I'll throw that into Grasshopper and see what happens.

Best,

Tobias

• ▶ Reply

Permalink Reply by Luis Fraguada on July 2, 2009 at 2:28am

Hello Tobias,

I see now the very interesting page in Daniel's research on pseudo-random numbers. To be honest, I have seen such diagonal patterns in vb.net's random number generator. But I wonder how many random numbers he was generating at the same time, and if there was an independent generator for each coordinate. The diagonal pattern would imply at least two coordinates are equal no? x = y would start to scratch in points along that axis. But if a random number was created for each coordinate

randomNumberX = (rndMax - (rndMin + 1)) * (randomClass.NextDouble() + rndMin)
randomNumberY = (rndMax - (rndMin + 1)) * (randomClass.NextDouble() + rndMin)
randomNumberZ = (rndMax - (rndMin + 1)) * (randomClass.NextDouble() + rndMin)
Dim pt As New On3dPoint(x + RandomNumberX, y + RandomNumberY, z + RandomNumberZ)

Then maybe the pseudo-randomness is obscured by a few factors.

• ▶ Reply

Permalink Reply by Tobias Schwinn on July 5, 2009 at 11:55am

Hello Luis,

Correct me if I'm wrong but the code example that you're showing doesn't look right. If you were trying to create random integers then you would use

Int((intHigh - intLow + 1) * Rnd + intLow)

For real numbers you would use

(dblHigh - dblLow) * Rnd + dblLow

The "+ 1" is only there because the Int() function always rounds down.

According to the "Random Walk" website, the way the random numbers are generated is as follows: In the sequence of random numbers 3 consecutive numbers form the x, y & z coordinates of the points in the cube.

In the above example definition I implemented this rule in Grasshopper. Interestingly, if you implement the same rule in Rhinoscript using the same seed value you get a different result from the one done in Grasshopper (have a look at the screenshot).

' Reset the random-number generator and provide a seed value for subsequent calls To Rnd
Rnd (-1)
Randomize 2

For i = 0 To max
arrDbl(i) = Rnd
Next

For j = 0 To max Step 3
Call Rhino.AddPoint(Array(arrDbl(j), arrDbl(j + 1), arrDbl(j + 2)))
Next

So, it looks like vbscript is using a different random number generator algorithm than vb.net. Within vbscript and Grasshopper the sequence of random numbers is always the same (as it should be) however they are different from eachother.

Let me know if this makes sense.

Attachments:

• Vollbildaufzeichnung 05.07.2009 132759.jpg, 223 KB
• randomNumbers.rvb, 1 KB

• ▶ Reply

Permalink Reply by Luis Fraguada on July 6, 2009 at 1:51am

http://www.rlmueller.net/CrackRnd.htm
I did not do a very thorough search, but the page above seems to claim that vbscript uses a 24-bit Linear Congruential Generator. I did not come up with a source on the microsoft website... Would be nice to know why they chose to use different generator (if that is indeed the case).

• ▶ Reply

Permalink Reply by Tobias Schwinn on July 20, 2009 at 9:50pm

Thank you Luis, following your clue I did a little bit of reading about Linear Congruential Generators (LGCs). Ok, it's already a while back now that we talked about this. Anyway, if you have a look at wikipedia's entry on LGCs (http://en.wikipedia.org/wiki/Linear_congruential_generator#Advantag...) there is this little animated gif that illustrates the parallel hyperplanes produced by LGCs. This is caused by the fact that each successive number is mathematically related to the previous number. Long story short rhinoscript (which as we know, is based on vbscript) produces exactly those hyperplanes. The screenshot is taken from a file containing 100,000 pseudo-random points in a unit cube. Please find the code used to generate those points attached below.
Having said this, I wasn't able to spot those hyperplanes in random numbers that were generated in Grasshopper using the exact same approach. This might be another clue that the Random Number Generator (RNG) in Grasshopper is using a different algorithm. It is worth noting that generating the same amount of numbers/points in Grasshopper takes significantly, that is to say at least 2 to 3 times, longer.
I'm thinking that there are implications of all this that are maybe worth mentioning/discussing. What this basically means is that those numbers that are not lying on one of those hyperplanes are never going to be produced by the LCG. More specifically, if one thinks about genetic algorithms certain random mutations are not going to happen. This would mean that certain options are not going to be produced and therefore the solution space is limited by the RNG. (Ok, all this sounds slightly abstract unless someone proves that using alternatives to LCGs actually produces better results in GAs). But there might be other implications in addition to the one that you shouldn't use rhinoscript to encrypt your passwords...

Vollbildaufzeichnung 20.07.2009 231919.jpg

Attachments:

• randomNumbers_v2.rvb, 1 KB
• randomNumbers_v2.ghx, 103 KB

• ▶ Reply

Permalink Reply by Tobias Schwinn on July 26, 2009 at 8:30pm

Of course there is a simple way of testing if GH is using the default vb.net random class. Simply by creating a vb component one can show that Grasshopper's random number component is creating the exact same string of pseudo random numbers. Therefore the quote that you provided above applies to GH as well:

The current implementation of the Random class is based on Donald E. Knuth's subtractive random number generator algorithm. For more information, see D. E. Knuth. "The Art of Computer Programming, volume 2: Seminumerical Algorithms ". Addison-Wesley, Reading, MA, second edition, 1981.

Attachments:

• Screenshot 26.07.2009 215920.jpg, 251 KB
• randomNumbers_vb.ghx, 45 KB

• ▶ Reply