• Advertisement
Sign in to follow this  

Unity Number Generator "CMWC 4096" and Implementation?

This topic is 3375 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

In another thread (C++ true random numbers), somebody mentioned that the generator CMWC 4096 by George Marsaglia was better in several ways (speed, period, simplicity, output quality) than the more commonly used Mersenne Twister. These details spurred me into investigating this generator, and I need some assistance doing so. A google quickly produced (not-so-great) C source code created by the creator of the CMWC algorithm (below). You can see a paper by the same person (taken from wikipedia) titled Random number generators. An explanation of the algorithm is also available on wikipedia: Complementary-multiply-with-carry RNGs. I think I understand the premise of the algorithm after reading the paper and several other comments by the author, but there are a couple of things in the code that don't seem to match the explanations. (1) To me, it looks like the carry is being added twice (once to 't' and again when the lower bits are extracted to 'x'). I would believe this is simply a basic mistake because it doesn't match my understanding of the math, but every reproduction of the algorithm seems to contain the apparent double addition of 'c'. (2) I also do not understand the purpose of the "if" statement and it's body - I don't see anything corresponding to it in his very simple explanation of the algorithm in the paper I linked above. I imagine that if (1) is not a mistake that this is related to it (testing for overflow), but I'm not aware of the reason for (1) so this also remains a mystery to me.
static unsigned long Q[4096], c=123;
unsigned long CMWC(void)
{
	unsigned long long t, a=18782LL;
	static unsignd long i=4095;
	unsigned long x, m=0xFFFFFFFE;

	i = (i + 1) & 4095;
	t = a * Q[i] + c;
	c = (t >> 32);
	x = t + c;
	if(x < c)
	{
		++x;
		++c;
	}
	return (Q[i] = m - x);
}



Share this post


Link to post
Share on other sites
Advertisement
I realized something before I posted the above, but I apparently forgot while making the post. With respect to (1), the carry isn't added twice, but rather both Carry_n-1 and Carry_n are added. I still don't have any idea why, but it is an important distinction that two different carry values are added.

Share this post


Link to post
Share on other sites
This does not answer your question, but one of the first google results presents an implementation given by the author, and he includes a

if ((x+1)==0) { c++; x=0; }

between the if (x < c) and the return.

I just figured it might be relevant since it includes the carry variable as well.

I don't understand why he does that though... doesn't that knock out the only chance that the function will return 0xffffffff?

-Scott

Share this post


Link to post
Share on other sites
I agree. That code does not calculate the same function as documented on the wikipedia page. His cn is calculated as (a * Q[i] + cn-1) mod b div b, and his x is calculated as (a * Q[i] + cn-1) mod b + cn mod b then biased by 1 if x < cn (where b == 2^(2^sizeof unsigned long) and sizeof unsigned long == 4).

I can't for the life of me come up with any kind of reasonable algebraic transformation from the wikipedia equation and the implementation. Perhaps there are some cool manipulative tricks I've missed (such as Schrage's algorithm, only different).

I would also argue that a 16 kilobyte state vector per RNG is pretty expensive compared with the MT (or even other lag generators).

Share this post


Link to post
Share on other sites
I'll give it a try:
static unsigned long Q[4096], c=123; // Q holds the state
unsigned long CMWC(void)
{
unsigned long long t, a=18782LL;
static unsignd long i=4095;
unsigned long x, m=0xFFFFFFFE;

i = (i + 1) & 4095; // Advance through the state array, circularly
t = a * Q[i] + c; // Notice that the result is computed as a 64-bit integer.
// This is the core of a traditional LGC,
c = (t >> 32); // except we keep changing the constant we add.
x = t + c; // add the lower 32 bits with the higher 32 bits to avoid poor quality bits at the extremes.
if(x < c) // About 50% of the time (?? I don't know why this helps).
{
++x;
++c;
}
return (Q[i] = m - x); // I don't know why this is better than simply `(Q[i] = x)'.
}


Share this post


Link to post
Share on other sites
Quote:
Original post by Bregma
[...]I would also argue that a 16 kilobyte state vector per RNG is pretty expensive compared with the MT (or even other lag generators).
In some applications, such a large state is required. For example, consider a card game where each player can have a deck up to size S and there can be N players per game, you need to be able to generate a number from 0 to S!^N which grows very fast. If the game allowed up to 1000 cards per deck and 6 players per game, the state size required is 1000! ~= 2^8520 for one deck and (2^8520)^6 = 2^51120 for the initial game state, which is beyond MT's capability.

This kind of situation could easily happen in a customizable card game that doesn't have a maximum deck size in the rules, such as Magic the Gathering. In fact, to allow some tournament formats, you'd actually need two levels of RNGs (probably one 'seed generator' per tournament and then one 'game generator' per game) since a single one does possible provide the required state size.
Quote:
I'll give it a try:
[...]if(x < c) // About 50% of the time (?? I don't know why this helps).[...]
It's not 50% of the time: Since C is added to the value that determines X, X can only be lower than C if the value has overflowed. Overflow can only happen rather rarely since the range of C (0..18782 due to the ++C) is rather low and the range of the low 32 bits of T (0..2^32-1) is rather high. 99.99956272% of the time ((2^32-18782)/(2^32-1)), the lower bits of T will be small enough that no value of C will cause overflow.

[Edited by - Extrarius on October 22, 2008 11:22:48 AM]

Share this post


Link to post
Share on other sites
Quote:
Original post by Extrarius
Quote:
I'll give it a try:
[...]if(x < c) // About 50% of the time (?? I don't know why this helps).[...]
It's not 50% of the time: Since C is added to the value that determines X, X can only be lower than C if the value has overflowed. Overflow can only happen rather rarely since the range of C (0..18782 due to the ++C) is rather low and the range of the low 32 bits of T (0..2^32-1) is rather high. 99.99956272% of the time ((2^32-18782)/(2^32-1)), the lower bits of T will be small enough that no value of C will cause overflow.


Of course you are right. When I first read the algorithm, I thought that Q[i] was a 64-bit integer.

Anyway, it's not clear to me what that `if(x < c)' part does, and the same goes for the subtracting-from-0xfffffffe part.

Share this post


Link to post
Share on other sites
Quote:
Original post by alvaro
and the same goes for the subtracting-from-0xfffffffe part.

The same as subtracting 4 bit number.

14 - 0 = 14
14 - 1 = 13
14 - 15 = -1 mod 0xF = 15

Basically inverting the number, and shifting it by a little.

Share this post


Link to post
Share on other sites
Complement Multiply With Carry

I am not capable of translating the theory to an algorithm either, but I want to point out that the calculation of Mod (2^n-1) needs to use some tricks.

For example, if modulus = 2^n - 1 then there is an efficiency trick:

result = x Mod modulus

is equivilent to

result = (x And modulus) + (x >> n)
If (result >= modulus) Then result -= modulus

(^^ thats a bitwise And)

The later is generally much more efficient (assuming good branch prediction)

Now, note that he is using the constant 0xfffffffe, which is not his modulus (which is 0xffffffff) but in fact 1 less than his modulus .. this could explain what might be considered a spurious increment

note that (x And modulus) in his code is implicit with a conversion from 64-bit to 32-bit

Share this post


Link to post
Share on other sites
Quote:
Original post by Raghar
Quote:
Original post by alvaro
and the same goes for the subtracting-from-0xfffffffe part.

The same as subtracting 4 bit number.

14 - 0 = 14
14 - 1 = 13
14 - 15 = -1 mod 0xF = 15

Basically inverting the number, and shifting it by a little.


When I say I don't know what the code does I mean that I don't see how it's going to significantly affect the quality of the pseudo-random numbers generated.

Share this post


Link to post
Share on other sites
After doing a little work I feel that I should point out that the x mod 2^n-1 trick only works when x is less than 2^(2n)-1

This problem was frustrating to uncover (ouch!)

In the case of calculating (x * y) mod (2^n-1) where 2n is greater than or equal to the sum of the binary lengths of both terms, there shouldn't be a problem.

Share this post


Link to post
Share on other sites
Quote:
Original post by alvaro
When I say I don't know what the code does I mean that I don't see how it's going to significantly affect the quality of the pseudo-random numbers generated.


It is the Complement Multiply With Carry, stress the Complement.

He wishes to keep (for his x's)

b - ((ax + c) mod b)

which is different from a Multiply With Carry, where you keep

((ax + c) mod b)

In his code, 'm' is actualy 'b - 1'

so 'by default' he is 1 too low with his (m - x), which I suspect explains completely the 'extra' increment.

The reason to use the complement is, according to his pdf there, to get the maximal length period out of the number of bits being stored in the state (the period is actualy a small bit shy, because b isnt 2^32 but instead 2^32-1)

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
  • Advertisement
  • Popular Now

  • Advertisement
  • Similar Content

    • By Chamferbox
      Chamferbox, a mini game asset store has just opened with some nice game assets, 
      Here you can find a free greek statue asset 

      Also check their dragon, zombie dragon and scorpion monster out:



      They're running the Grand Opening Sale, it's 30% off for all items, but for gamedev member, you can use this coupon code:
      GRANDOPEN
      to get 50% off prices What are you waiting for, go to
      http://chamferbox.com
      and get those models now!

      View full story
    • By Dafu
      FES Retro Game Framework is now available on the Unity Asset Store for your kind consideration!
      FES was born when I set out to start a retro pixel game project. I was looking around for an engine to try next. I tried a number of things, from GameMaker, to Fantasy Consoles, to MonoGame and Godot and then ended up back at Unity. Unity is just unbeatable in it's cross-platform support, and ease of deployment, but it sure as heck gets in the way of proper retro pixel games!
      So I poured over the Unity pipeline and found the lowest levels I could tie into and bring up a new retro game engine inside of Unity, but with a completely different source-code-only, classic game-loop retro blitting and bleeping API. Months of polishing and tweaking later I ended up with FES.
      Some FES features:
      Pixel perfect rendering RGB and Indexed color mode, with palette swapping support Primitive shape rendering, lines, rectangles, ellipses, pixels Multi-layered tilemaps with TMX file support Offscreen rendering Text rendering, with text alignment, overflow settings, and custom pixel font support Clipping Sound and Music APIs Simplified Input handling Wide pixel support (think Atari 2600) Post processing and transition effects, such as scanlines, screen wipes, screen shake, fade, pixelate and more Deploy to all Unity supported platforms I've put in lots of hours into a very detail documentation, you can flip through it here to get an better glimpse at the features and general overview: http://www.pixeltrollgames.com/fes/docs/index.html
      FES is carefully designed and well optimized (see live stress test demo below). Internally it uses batching, it chunks tilemaps, is careful about memory allocations, and tries to be smart about any heavy operations.
      Please have a quick look at the screenshots and live demos below and let me know what you think! I'd love to hear some opinions, feedback and questions!
      I hope I've tickled your retro feels!



      More images at: https://imgur.com/a/LFMAc
      Live demo feature reel: https://simmer.io/@Dafu/fes
      Live blitting stress test: https://simmer.io/@Dafu/fes-drawstress
      Unity Asset Store: https://www.assetstore.unity3d.com/#!/content/102064

      View full story
    • By DevdogUnity

      Ho ho ho
      Tis the season of Christmas surprises, and we have a awesome one for you! 🎅  
      Sponsored by all your favorite Unity Asset Store developers, Nordic Game Jam, Pocket Gamer Connects, and co-hosted by Game Analytics, we (Joris and I – Devdog) are launching the second edition of our yearly Christmas Giveaway Calendar for all Unity game developers!
      You can already now sign up right here.
       
      So what’s this all about?
      For the past weeks, we’ve been collecting sponsored gifts related to Unity (asset vouchers, product keys, conference tickets etc.), and throughout each day of December leading up to Christmas Day on the 25th, we will be sending out these sponsored gifts as early gamedev Christmas presents via e-mail to hundreds of lucky winners.
      The total prize pool is at $35,000, with over 1200 presents donated by the awesome sponsors!
       
      Merry Christmas from Devdog, Game Analytics, and every single one of the sponsors.

      View full story
    • By sveta_itseez3D
      itSeez3D, a leading developer of mobile 3d scanning software, announced today a new SDK for its automatic 3D avatar generation technology, Avatar SDK for Unity. The Avatar SDK for Unity is a robust plug-n-play toolset which enables developers and creatives to integrate realistic user-generated 3D avatars into their Unity-based applications. SDK users can allow players to create their own avatars in the application or integrate the SDK into their own production processes for character design and animation.
      “Virtual avatars have recently become increasingly popular, especially in sports games and social VR apps. With the advance of VR and AR, the demand to get humans into the digital world is only increasing”, said Victor Erukhimov, itSeez3D CEO. “Our new Avatar SDK for Unity makes it super-easy to bring the avatar technology into any Unity-based game or VR/AR experience. With the Avatar SDK for Unity now every developer can bring face scanning technology into their games and allow players to create their own personalized in-game avatars, making the gameplay much more exciting and immersive.”
      Key features of the Avatar SDK for Unity:
      Automatic generation of a color 3D face model from a single selfie photo in 5-10 seconds (!). Works best with selfies, but can be used with any portrait photo.
      Shape and texture of the head model are unique for each person, synthesized with a deep learning algorithm crafted by computer vision experts
      Head models support runtime blendshape facial animations (45 different expressions)
      Generated 3D heads include eyes, mouth, and teeth
      Algorithms synthesize 3D meshes in mid-poly resolution, ~12k vertices, and ~24k triangles
      Six predefined hairstyles with hair-recoloring feature (many more available on request)
      Avatar generation API can be used in design-time and in run-time, which means you can allow users to create their own avatars in your game
      Cloud version is cross-platform, and offline version currently works on PCs with 64-bit Windows (support for more platforms is coming soon)
      Well-documented samples showcasing the functionality.
       
      Availability
      The Avatar SDK for Unity is offered in two modes - “Cloud” and “Offline”. The “Cloud” version is available at http://avatarsdk.com/ and the “Offline” version is available by request at support@itseez3d.com.
      ###
      About itSeez3D
      At itSeez3D, we are working on the computer vision technology that turns mobile devices into powerful 3D scanners. itSeez3D has developed the world's first mobile 3D scanning application that allows to create high-resolution photorealistic 3D models of people's' faces, bodies and objects. The application is available for iOS and Windows OS mobile devices powered with 3D cameras. In 2016 the company introduced Avatar SDK that creates a realistic 3D model of a face from a single selfie photo. To learn more about itSeez3D scanning software and 3D avatar creation technology, please visit www.itseez3d.com and www.avatarsdk.com.

      View full story
    • By khawk
      Unity has posted the Unity Austin 2017 playlist on YouTube. From their tweet:
      View the full playlist at https://www.youtube.com/playlist?list=PLX2vGYjWbI0TI_C4qouDw7MSSTFhKJ6uS or below:
      .

      View full story
  • Advertisement