next »

[st33d]

So I've ported my XORShift generator to C#. It has all the methods I like and I know how to seed it reliably. I adapted it from here:

Oh bugger. The site doesn't exist anymore. Well you see, that's part of the trouble I'm having. There's a lot of differing opinions on the implementation. Including bollocks with writing directly to memory and running loops. I can't find a straightforward answer. Honestly the version I had in AS3 was quite simple, fast and worked:

Code:

public function value():Number{
   r ^= r << 21;
   r ^= r >>> 35;
   r ^= r << 4;
   return r * MAX_RATIO;
}

Where r is a uint given an initial seed value and MAX_RATIO is a double: 1.0 / uint.MAX_VALUE.

So I thought I could port this to C#. But C# doesn't have a >>> operator. What does it do? It's an unsigned right shift. "But the uint is unsigned already!" says Microsoft.

So am I fucking this algorithm up by just swapping >> for >>>?

I can post the full class below if you need it, I just wanted to keep the OP brief.

[Dacke]

yes, >>> is equivalent to >> for unsigned integers

What >>> does is to fill up from the left with 0s
http://www.ecma-international.org/ecma-262/5.1/#sec-11.7.3

What >> does in C# for unsigned integers is to fill up from the left with 0s
http://msdn.microsoft.com/en-us/library/aa691377(v=vs.71).aspx

(For signed integers, >> fills up from the left with copies of the initial left-most bit. That way the number stays negative/positive.)

[st33d]

Thanks for clarifying the C# side. I'm not wholly up to speed there.

But what the hell is going on in AS3?

In AS3 it gave reliable random numbers. It just leaves me wondering if there's something weird going on in AS3's syntax that made the guy do that or if it was a typo. Being not that math savvy I don't feel qualified to say whether the results I'm getting in C# are actually random.

If anyone wants a go:

Code:

using UnityEngine;
using System.Collections;
using System;

/* Ported this from AS3.
 * 
 * My chief reason for using it is that I can have all the proper functions for all the jobs
 * without fannying around with functions named Next that mean fuck all during general use.
 * 
 * The algo also possibly has an error in it. In AS3 the author used an unsigned right shift
 * for some reason - which doesn't exist in C# upon the logic that the uint is unsigned anyway.
 * 
 * So I'm buggered if I know if this works or not. I dunno. Seems pretty random to me.
 */

public class XorRandom {

	public static uint r;
	public static uint seed;
	
	public const double MAX_RATIO = 1.0 / uint.MaxValue;
	
	public XorRandom() {
	}

	public static void Init(uint _seed = 0){
		
		//_seed = 1195675104;
		
		if(_seed != 0){
			r = _seed;
		} else {
			r = SeedFromDate();
		}
		seed = r;
	}
	
	/* Get a seed using a Date object */
	public static uint SeedFromDate(){
		uint r = (uint)System.DateTime.UtcNow.Ticks;
		// once in a blue moon we can roll a zero from sourcing the seed from the Date
		if(r == 0) r = (uint)(new System.Random().NextDouble() / MAX_RATIO);
		return r;
	}
	
	/* Returns a number from 0 - 1 */
	public static float GetFloat(float n = 1f){
		r ^= r << 21;
		r ^= r >> 35;
		r ^= r << 4;
		return (float)(r * MAX_RATIO * n);
	}

	public static float GetFloat(float min, float max){
		r ^= r << 21;
		r ^= r >> 35;
		r ^= r << 4;
		return min + (float)(r * MAX_RATIO * (max - min));
	}
	
	public static int GetInt(int n){
		r ^= r << 21;
		r ^= r >> 35;
		r ^= r << 4;
		return (int)(r * MAX_RATIO * n);
	}
	
	public static bool CoinFlip(){
		r ^= r << 21;
		r ^= r >> 35;
		r ^= r << 4;
		return r * MAX_RATIO < 0.5f;
	}
	
	/* Advance the sequence by n steps */
	public static void Step(int n = 1){
		while(n-- > 0){
			r ^= r << 21;
			r ^= r >> 35;
			r ^= r << 4;
		}
	}

	public static Vector3 Displace(Vector3 v, float dist){
		v.x += -dist + GetFloat(dist * 2);
		v.y += -dist + GetFloat(dist * 2);
		return v;
	}

	/* Sophie Houlden's wieghted random algo
	 * 
	 * function for getting a random index for an array, with specified liklihoods for each index
	 * use like:
	 * string[] items = {"rock", "coin", "gem"};
	 * float[] itemFrequency = {10f, 4f, 1f}; - protip, sort this list biggest 1st
	 * string randomItem = items[ GetWeightedRandomIndex(itemFrequency) ];
	*/
	public int GetWeightedRandomIndex(float[] arrayWeights){
		float tWeight = 0f;
		for (int i=0; i<arrayWeights.Length; i++) tWeight += arrayWeights[i];
		float r = GetFloat(tWeight);
		
		tWeight = 0f;
		for (int i=0; i<arrayWeights.Length; i++){
			if (r > tWeight && r <= tWeight + arrayWeights[i]) return i;
			tWeight += arrayWeights[i];
		}
		
		return arrayWeights.Length-1;
	}

}

[Dacke]

I'm not sure how much I can help you, as I don't know C#, AS3 or how the algorithm is expected to work.

The >> shouldn't be a problem. Maybe the problem is the different number representations in the languages? Or some cast to uint that results it some error. I'm really not sure.

The algorithm should work the same way in both languages, so you could run them side by side to find where they start to differ. Give both the same seed and print/trace the values you get during the algorithm, to find where they start to differ.

Another option is to ditch this specific algorithm and just write your own wrapper-class around C#'s existing RNG. That way you get robust randomization from C# but can use your own methods to access it.

[st33d]

Yeah, I'd wrap if I didn't like inlining as much as John Carmack does. I'm definitely going to have to graph this though. I'll post results.

There is the fact that the >>> documentation in AS3 says there is no corresponding <<<, so cast to uint. But "r" is a uint already. So, it's a typo?

Graph - then I get to see the hole in the period this particular algorithm makes. Eben Howard has posted this implementation as well:

https://github.com/SquidPony/SquidLib/blob/experimental/src/squidpony/squidmath/XorRNG.java

Though it says it's untested, so I'd have to graph that as well.

It's looking very much like I have to draw a graph.  

[Layl]

If it's random numbers you're looking for, you might want to look at the Random class.

http://msdn.microsoft.com/en-us/library/system.random%28v=vs.110%29.aspx


Thinking about this a bit more, I was wondering if that algorithm for generating numbers is faster than .NET's implementation. The general rule in .NET is that the standard libraries ALWAYS have implemented the fastest way to do it, with an important caveat to always measure anyways.

So without further delay, here's my measurements:

Code:

Microsoft: 00:00:01.0848913 (1.0848913 seconds)
Custom: 00:00:01.4591376 (1.4591376 seconds)

This was for 100 million(!) times calling the function. Here's my code so you can try it yourself:
https://gist.github.com/LaylConway/8596b376c6abf16399f1

Well there's your answer! Your custom value() function implemented in C# is 50% slower than Random.Next().

But why?

Let's look at the source and figure out!
http://referencesource.microsoft.com/#mscorlib/system/random.cs

From what I can see, rather than computing a new answer every time, it generates a table in the constructor. Then in Next, it uses two values from that array to generate the number. After generating the number it puts the value back into the array to make sure you will get a different result the next time you get those two values.

Why is this faster? I honestly can't tell for sure but I assume it's because you're doing a LOT less calculations. (a few +1s and a subtraction) As a result though, because that table is there it has a much larger memory footprint. (the table is 56 integers!) That memory footprint usually isn't a problem though, since you generally don't have many Random instances.

I would like to close off this post by addressing one complaint noted in the XorRandom java class.

Code:

 * My chief reason for using it is that I can have all the proper functions for all the jobs
 * without fannying around with functions named Next that mean fuck all during general use.

In C#, you can create an extension method!

Code:

public static class RandomExtensions
{
	public static int GetInt(this Random random)
	{
		return random.Next();
	}

	public static bool CoinFlip(this Random random)
	{
		return random.Next(2) == 0 ? false : true;
	}
}

// Then you can use them like:
var rand = new Random();
var test1 = rand.GetInt();
var test2 = rand.CoinFlip();

"But Layl, what about Mono?" you might say. To which I answer "How did you get into my house?"

Unity 3D doesn't use .NET, it uses Mono Embedded. Mono is an open source implementation of the .NET framework, and thus has its own implementation of the Random class. Looking at the source it's VERY different from .NET's implementation.
https://github.com/mono/mono/blob/master/mcs/class/corlib/System/Random.cs

I refactored the test code a bit, added in our new MonoRandom and...

Code:

Microsoft: 00:00:01.0650837 (1.0650837 seconds)
Mono: 00:00:04.2950404 (4.2950404 seconds)
Xor: 00:00:01.6635072 (1.6635072 seconds)

Woah! It's 4 times as slow as Microsoft's implementation!

However keep in mind that this is all micro optimization. The seconds difference is only visible because we're running these functions a 100 million times. Most likely, your random function isn't going to be your bottleneck. Adding your own custom implementation will add a lot of uncertainty and complexity to your code base. That's something you never want.
http://blog.codinghorror.com/micro-optimization-and-meatballs/


Since I was on such a roll with this post, I decided to make another addition! Turns out, these classes perform differently on Mono than they do on .NET! So to be entirely sure, I stuffed these classes into a Unity project. (copying over the .NET reference implementation since I can't just use the Random class there)

Let's see what the result is!

Code:

Microsoft: 00:00:02.6206364 (2.6206364 seconds)
Mono: 00:00:02.6038894 (2.6038894 seconds)
Xor: 00:00:01.3177572 (1.3177572 seconds)

More interesting differences! Turns out that on mono, the Mono implementation and the .NET implementation perform nearly identically. The mono implementation however only uses 4 integers, instead of the entire array the .NET one uses! As well, both implementations are slower than the Xor implementation, which performs slightly faster here.


But what about Unity's own implementation? And is there a difference between using System.Random and our copied MonoRandom class? Let's see again!

Code:

Corlib: 00:00:02.7176550 (2.717655 seconds)
Unity: 00:00:02.0844385 (2.0844385 seconds)
Microsoft: 00:00:02.5794904 (2.5794904 seconds)
Mono: 00:00:02.6090185 (2.6090185 seconds)
Xor: 00:00:01.3437745 (1.3437745 seconds)

Corlib (System.Random) is nearly identical to MonoRandom and MsRandom here. Unity's Random.value property (a wtf by itself, don't use Unity's random class, the API is terrible) takes less than Corlib, Microsoft and Mono, but is still slower than Xor.

[Sik]

Call me clueless but:

Code:

	public static uint r;
	public static uint seed;

What's the size of that integer? Because it seems the algorithm wants a 64-bit integer.

EDIT: also a very good reason to make one's own PRNG is if one needs to get a specific sequence of numbers always (e.g. in competitive puzzle games that look random but both players need to get the exact same values, or for games that have replays by just faking player input, etc.) You never know what the system's implementation is doing.

[Layl]

EDIT: also a very good reason to make one's own PRNG is if one needs to get a specific sequence of numbers always (e.g. in competitive puzzle games that look random but both players need to get the exact same values, or for games that have replays by just faking player input, etc.) You never know what the system's implementation is doing.

If you need both sides to get the same number, you make the server do the calculation. If you need to store a replay, you store the seed.

[Sik]

...you completely missed my point in both examples.

1) Games like Puyo Puyo generate the sequence of pieces randomly, but they need the same set of pieces to be given to both players in order for the match to be fair. Using the system PRNG won't help you here, you need to have your own PRNG and have two different instances of it (one for each player), and both starting from the same seed. This is a need even with local multiplayer.

2) In the case of a replay storing the seed alone won't help you if the underlying algorithm changes (this happens when porting across platforms, but can also happen when upgrading to a newer version of the API). You need to make sure that the PRNG stays the same, and this usually means making your own.

[Dacke]

Call me clueless but:

Code:

	public static uint r;
	public static uint seed;

What's the size of that integer? Because it seems the algorithm wants a 64-bit integer.

That should be the problem, then.
uint is 32 bit
ulong/uint64 is 64 bit

[st33d]

I think there's a weird thing in AS3 where a uint is actually a Number type. AS3 Number is 64bit, but uint is listed as 32bit. Yet it behaves like a Number type in some casting circumstances IRC.

So the guy who wrote this may have been aware of that. It definitely shouldn't work in C# because the middle line is just clearing the whole thing.

Ugh. I really should run some results in AS3 and C# to see what numbers come out.

Been busy making my game run at 60fps today though so, yeah, that was a bit more fun to do: https://vine.co/v/OKhihKL5JPa

[Sik]

If I was you I'd just change the variables to 64-bit and see if the problem gets fixed. It's not a hard thing to test, right?

[Layl]

1) Games like Puyo Puyo generate the sequence of pieces randomly, but they need the same set of pieces to be given to both players in order for the match to be fair. Using the system PRNG won't help you here, you need to have your own PRNG and have two different instances of it (one for each player), and both starting from the same seed. This is a need even with local multiplayer.

Again, shouldn't it be the server's job to decide what happens in situations like that? Why do both clients have to generate the list of pieces?

There's dangerous things that could happen if you decide to give the client the seed to your PRNG! Not only does that mean that in games like starcraft where there's fog of war you need to send EVERYTHING to the client (or it can't know when a next value is requested), it also means in games like team fortress 2 where RNG is used to check if someone gets a critical hit it becomes much easier to estimate when to shoot to get one.

2) In the case of a replay storing the seed alone won't help you if the underlying algorithm changes (this happens when porting across platforms, but can also happen when upgrading to a newer version of the API). You need to make sure that the PRNG stays the same, and this usually means making your own.

This to me just smells of bad design. There's other ways of doing this that don't require being dependent on the specific implementation. What if it turns out there's a bug in your PRNG and now that you fixed it the sequence is different? Now it breaks all replays! A better solution would be to store for every instance where a random number was used what the result was.

[Sik]

OK, seriously, you're literally looking for excuses to imply that doing something yourself is always a bad idea.

Again, shouldn't it be the server's job to decide what happens in situations like that? Why do both clients have to generate the list of pieces?

There's dangerous things that could happen if you decide to give the client the seed to your PRNG! Not only does that mean that in games like starcraft where there's fog of war you need to send EVERYTHING to the client (or it can't know when a next value is requested), it also means in games like team fortress 2 where RNG is used to check if someone gets a critical hit it becomes much easier to estimate when to shoot to get one.

Do you even know what kind of games am I talking about? This is not a matter of keeping two systems in sync, it's part of the game design itself. Also congratulations on missing on the local multiplayer part (i.e. the issue happens even when there aren't two machines to sync), and in fact this can be an issue even in single player (e.g. when going with computer-controlled opponents).

Also seriously, tell me how

can be achieved just using the system-provided PRNG. Note how the same sequence of pieces is given to each player, which can go on forever (there's no theoretical limit), so it's not a matter of just pregenerating a list. Having two instances of the PRNG that work independently of each other would be enough, except the system-provided PRNG doesn't allow that or even give a way to fake it.

You seem to think I'm talking about just having netgames synchronized the lazy way when I'm talking about something more closely tied to the game design itself.

This to me just smells of bad design. There's other ways of doing this that don't require being dependent on the specific implementation. What if it turns out there's a bug in your PRNG and now that you fixed it the sequence is different? Now it breaks all replays! A better solution would be to store for every instance where a random number was used what the result was.

Well, if we go that way, failing to store the entire state of every frame would be bad design, since if the game uses floating point it's also bound to break eventually (the underlying algorithms used in the FPU could change in different processor models, resulting in different rounding errors, which will eventually cascade and result in wildly different results over time). I don't think you want to store that much data, do you? (not to mention it's a lot harder to set the entire state of the game than just faking player input, so you're bound to introduce even more bugs that way as well to take longer to implement it)

And yes, for the record, these issues are why most games don't bother with replays in the first place, they're very easy to break if you aren't careful regardless of what method you choose.

[Layl]

Yes, I am implying that doing something yourself when it's already available is a bad idea. I agree there are exceptions but this isn't one of them. I indeed did not know what kind of game you were talking about, and I should have researched more on that. I'm sorry for making wrong assumptions about the type of game you were talking about.

I however still think that depending on your random number algorithm implementation isn't the way to go, and to answer your question on how it can be achieved I wrote a small class:

Code:

	public class ProceduralRandomList
	{
		private readonly List<int> _list = new List<int>();
		private readonly Random _random = new Random();

		public int GetAtIndex(int index)
		{
			// Generate numbers until it's in the list (might be already in there, in which case it will just skip this)
			while (index >= _list.Count)
			{
				_list.Add(_random.Next());
			}

			// Now that it's in the list, return it
			return _list[index];
		}
	}

With a bit of test code to try it out:

Code:

	static class Program
	{
		public static void PlayerRequests(ProceduralRandomList list, int player, int piece)
		{
			Console.WriteLine("Player {0} requests piece #{1}: {2}", player, piece, list.GetAtIndex(piece));
		}

		static void Main(string[] args)
		{
			var list = new ProceduralRandomList();

			PlayerRequests(list, 1, 0);
			PlayerRequests(list, 1, 1);
			PlayerRequests(list, 2, 0);
			PlayerRequests(list, 1, 2);
			PlayerRequests(list, 2, 1);
			PlayerRequests(list, 1, 3);

			Console.ReadKey();
		}
	}

This way you can even save the member _list to a file and read it back in if you need to replay the numbers. I don't think this would take too much space. It wouldn't by far even take noticeable space compared to the actual input. (depending on how many random numbers you use of course)

[st33d]

It always happens that you ask a question you believe to be in straight forward manner, some smart arse comes along and says,

"Why would you want to do that?"

That, ladies and gentlemen, is not an answer. It's another question.

Anyway.

AS3 is a very strange beast indeed. Here's what happened when I decided to see what the difference between >>> and >> was:

Code:

start value 1195675104 1000111010001001000110111100000
r << 22 1195675104 11101000100100011011110000000
<< 22 4215573984 11111011010001001000110111100000
// and here we test what the difference is
r >> 35 4215573984 -100101110110111001000100
r >>> 35 4215573984 11111011010001001000110111100
// WTF?

I was using uint.toString(2) to get the binary values. Nice that it assumes uint is capable of negative binary numbers.

The fact remains that >>> and >> behave completely differently in AS3 and output completely different results. The algorithm cannot be ported to C# by simply swapping >>> for >>.

I can't simply swap up to 64bit integers because the algorithm in AS3 is clearly doing something really bizarre. I might just go with Eben's version and graph it to check it works properly.

[Layl]

When taking the following code:

Code:

public function value():Number{
   r ^= r << 21;
   r ^= r >>> 35;
   r ^= r << 4;
   return r * MAX_RATIO;
}

And translating it directly into C#, you get:

Code:

public static int Value(){
  r ^= r << 21;
  r ^= r >> 35;
  r ^= r << 4;
  return r * MAX_RATIO;
}

However there's other better ways to solve the issue "How do I generate a random number in C#", which seems to be the problem you're trying to solve.


Thinking over it a bit more, I think the problem is actually in the signedness. ">>>" is an unsigned operator in AS, while "<<" is a signed one. In C# the signedness is inferred by what the type of the value you're bit shifting is.

Taking that into account, the code should be adjusted into this to exactly mirror the original code:

Code:

private static uint r;

public static int Value(){
  r ^= (uint)((int)r << 21);
  r ^= r >> 35;
  r ^= (uint)((int)r << 4);
}

By casting the uint to an int, performing the bitshift, then casting back again, you're ensuring the same signedness is used with the operators as in the original code.

[Dacke]

What would the difference be between a signed << and an unsigned <<? The << operator only fills in with 0 from the right, so sign shouldn't matter, right?

Also, I have no idea what the is going on in that AS3 test.

[Sik]

The fact remains that >>> and >> behave completely differently in AS3 and output completely different results. The algorithm cannot be ported to C# by simply swapping >>> for >>.

Well, I gave my try to it in C (although I inverted the directions so the way bits changed was the opposite because I like to use modulo to make my life easier) and it seemed to work reasonably decent for me:

Code:

static uint64_t prng_seed;

void reset_random(void) {
   prng_seed = 0x5AA5A55A5AA5A55A;
}

uint16_t get_random(uint16_t max) {
   prng_seed ^= prng_seed >> 21;
   prng_seed ^= prng_seed << 35;
   prng_seed ^= prng_seed >> 4;

   return prng_seed % (max + 1);
}

(rewrite code for C# and then to be relevant to your needs)

Do you need exactly the same results as your previous code? (and I mean if there's anything that could break now or in the future if it changes right now) If not, really just consider testing if it's random enough instead of it being exactly the same. Test the values it outputs for randomness and see what happens.

[Layl]

I generated a quick 1000 values and piped them into a file, then put the file into wolfram alpha to get a few graphs out of it. For reference, here's the function I ran:

Code:

private static uint _r = 4529432;
private static uint NextInt()
{
	_r ^= _r << 21;
	_r ^= _r >> 35;
	_r ^= _r << 4;

	return _r;
}

And here are the graphs that came out of wolfram alpha: