Sign in to follow this  
Extrarius

Unity Number Generator "CMWC 4096" and Implementation?

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
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

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this  

  • Forum Statistics

    • Total Topics
      627787
    • Total Posts
      2979031
  • Similar Content

    • By Hacktion Architects
      Hey guys me and my team have made our first game! Would be awesome if you guys could download, play it and let us know what you think!

      3. 2. 1. GO! Fly through the local school grounds with three other drones vying for the fastest time. Racing past the football fields, weaving in between pillars and squeezing through tight corridors, in Drozone speed is everything.
      Race through checkpoints while keeping your eyes out for power ups that give you a big short burst of speed, but be careful not to lose control!
      And if you're having problems completing the course you will want to grab the shield power up to double your health.
      Pick your drone and start racing, will you be able to beat our fastest lap time?
      Trailer here:
      https://www.youtube.com/watch?v=tekETULy2Qk&feature=youtu.be
      Link to download:
      https://gamejolt.com/games/drozone/292176
      A game developed by a group of seven young indie devs, from Brisbane Australia, Drozone is focused on delivering the exhilaration of flying a drone in first person.
      The experience is built up around competition between players and seeing who can get the fastest time. Let us know what you’re fastest time is!
    • By Polycanic Studios

      Everybody's favorite hard hitting reality blood sport is back and is better than ever. Join your host Miss Midnight and enter the Graviators arena for a new and thrilling style of combat.
      Graviators is a 3rd person arena based brawler in which you can play online multiplayer and LAN multiplayer with up to 4 friends or test your skills in our single player mode. Choose your fighter, control your gravity and fight using each characters unique ranged and melee attacks. 

      Download now at: www.graviators.com or watch the Trailer
      Graviators is currently released but will be receiving updates to make improvements and fix any issues so please bear with us! If you want to know more about what we are up to, follow us here for regular devlogs or check out our Facebook or Twitter for updates. 
      If you want to get in contact with us, please feel free to comment here, polycanicstudios@gmail.com or send us a message on Facebook!
    • By INTwindwolf
      COMPANY AND THE PROJECT

      We are an indie game studio consisted of professional and friendly people. Additionally, we are a team of skilled artists and dedicated indie enthusiasts. Our current project is INT, developed on Unity Engine 5 for platforms Windows, Linux, and Mac.

      INT is a 3D Sci-fi RPG with a strong emphasis on story, role playing, and innovative RPG features such as randomized companions. The focus is on the journey through a war-torn world with fast-paced combat against hordes of enemies. The player must accomplish quests like a traditional RPG, complete objectives, and meet lively crew members who will aid in the player's survival. Throughout the game you can side and complete missions through criminal cartels, and the two major combatants, the UCE and ACP, of the Interstellar Civil War.
      Please note that all of our current positions are remote work. You will not be required to travel.
      For more information about us, follow the links listed below.
      INT Official website
      Steam Greenlight
      IndieDB page
      Also follow social media platforms for the latest news regarding our projects.
      Facebook
      Twitter
       
      TALENT NEEDED
      We are looking for an Animator to join the Art team to create and polish animations for the game. You will be collaborating with fellow members of the team, and follow instructions from the Project Lead and the Animation team Lead in crafting smooth, flowing animations.
      As an Animator for this project, your duties would include:
      Create rigs to be used for animations. Skin 3D models to rigs. Contribute to constructive team discussions. Attend regular team meetings.  
      REQUIREMENTS
      To be successful in this position, following requirements apply:
       
      Have working knowledge of 3D animation suites. Understand import/export requirements for Unity Engine integration. Excellent self-management skills. Excellent attention to detail. Excellent communication skills. Preferred requirement:
      Knowledge of the Unity Engine UMA character creation system would be an advantage.  
      REVENUE - SHARE
      This is the perfect opportunity to get into the game development industry. Being an Indie team we do not have the creative restrictions often imposed by publishers or other third parties. We are extremely conscientious of our work and continuously uphold a high level of quality throughout our project.
      We are unable to offer wages or per-item payments at this time. However revenue-sharing from crowd-funding is offered to team members who contribute 15-20 hours per week to company projects, as well as maintain constant communication and adhere to deadlines. Currently the crowd-funding campaign is scheduled for the year 2018. Your understanding is dearly appreciated.
       
      TO APPLY
      Please send your Cover Letter, CV, Portfolio (if applicable), and other relevant documents/information to this email: JohnHR@int-game.net
      Thank you for your time! We look forward to hearing from you!
      John Shen
      HR Lead
      Starboard Games LLC
    • By KARTHI
      Now I am making 2d game in my home. I am so confused with the resolution.
      Please anyone help me to choose the resolution
    • By KARTHI
      Free software
       
      1. Lumberyard (Game engine) open-source and free tool
      Amazon Lumberyard is a free cross-platform triple-A game engine developed by Amazon and based on the architecture of Cry Engine, which was licensed from Crytek in 2015.
       
      2. Sculptris (sculpture tool) open-source and free tool
      Sculptris is a virtual sculpting software program, with a primary focus on the concept of modeling clay. It entered active development in early December 2009, and the most recent release was in 2011.
       
      3. Make human (game model creator) open-source and free tool
      Make human is an open-source 3D computer graphics software middleware designed for the prototyping of photorealistic humanoids. It is developed by a community of programmers, artists, and academics interested in 3D modeling of characters.
       
      4. Ipi soft (motion capture software) not free tool
      iPi Motion Capture is a scalable markerless motion capture software tool that supports 1 or 2 Kinect cameras or 3 to 6 Sony PlayStation Eye cameras to track a human action and convert it into a motion capture file
       
       5. Blender (Complete tool) for modeling, texturing and so on (open-source and free tool)
       Blender is a professional, free and open-source 3D computer graphics software toolset used for creating animated films, visual effects, art, 3D printed models, interactive 3D applications and video games.
                 
      6. Audacity (music editor) open-source and free tool
      Audacity is a free open source digital audio editor and recording computer software application, available for Windows, OS X, Linux and other operating systems.
                 
      7. Awesome bump (bump map editor) open-source and free tool (optional)
      Awesome Bump is a free program written using Qt library designed to generate normal, height, specular or ambient occlusion textures from a single image.
       
      8. Faceware (facial animation) not free tool
      Faceware Technologies is an American company that designs facial animation and motion capture technology. The company was established under Image Metrics and became its own company at the beginning of 2012.
       
      9. GIMP (image editing) open-source and free tool
      GIMP is a free and open-source raster graphics editor used for image retouching and editing, free-form drawing, converting between different image formats, and more specialized tasks. Through this you can also create bump maps
       
      10. Meshlab (mesh repair) open-source and free tool (Optional)
      MeshLab is an advanced 3D mesh processing software system that is oriented to the management and processing of unstructured large meshes and provides a set of tools for editing, cleaning, healing.
       
      11. LibreOffice (create documents) open-source and free tool
      LibreOffice is a free and open source office suite, a project of The Document Foundation. It was forked from OpenOffice.org in 2010, which was an open-sourced version of the earlier StarOffice.
                 
      12. Atom (coding software) open-source and free tool
      Atom is a free and open-source text and source code editor for macOS, Linux, and Microsoft Windows with support for plug-ins written in Node.js, and embedded Git Control, developed by GitHub.
                 
       
      Useful websites
      free image
                 
      Reference images will be found on Pinterest
       
      Free Sounds
       
      1.      Freesound.org
      2.      99Sounds.org
      3.      NoiseForFun.com
      4.      Incompetech.com
      5.      OpenGameArt.org
      6.      RaisedBeaches.com
      7.      Musopen.org
      8.      PlayonLoop.com
      9.      Bensound.com
      10.   SoundJay.com
      11.   Dig.ccmixter.org
      12.   Soundgator.com
      13.   Pacdv.com
      14.   Freesfx.co.uk
      15.   Soundtrack.imphenzia.com
      16.   Bxfr.net
       
      Download the free music tracks from these websites
       
      1. http://incompetech.com/music/
      2. http://dig.ccmixter.org/
      3. http://www.joshwoodward.com
      4. http://www.youtube.com/audiolibrary
       
      I hope this information will help full to you. I am got so stress to collect this data so don't waste it 
      🤗🤗🤗🤗🤗🤗🤗🤗🤗🤗🤗🤗🤗🤗🤗🤔🤔🤔🤔🤔🤔🤔🤔🤔🤔🤔🤔🤔🤔🤔
       
       
  • Popular Now