Sign in to follow this  
Extrarius

Unity Number Generator "CMWC 4096" and Implementation?

Recommended Posts

Extrarius    1412
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
Extrarius    1412
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
popsoftheyear    2194
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
Bregma    9202
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
alvaro    21246
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
Extrarius    1412
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
alvaro    21246
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
Raghar    96
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
Rockoon1    104
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
alvaro    21246
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
Rockoon1    104
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
Rockoon1    104
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  

  • Similar Content

    • By ilovegames
      You - the chief doctor of the hospital. Working late into the evening, did not notice the majority of hospital workers went home ... But where you disappeared the night shift is also not known. Hastily taking important documents, go home, but something went wrong as usual ... Can you get out of the hospital alive?
      Download https://falcoware.com/AtTheHospital.php



    • By Gator Man
      Game Concept Doc: https://docs.google.com/document/d/1B5eS_eGMke3gk5xPyMLekZY1T7uE2q1pO4vFdALIOC8/edit

      We are looking for every position. From Game designer, to marketer, to programmer, to 3D modeler. Any further questions can be discussed through discord
      DISCORD: Gator#5635
    • By ilovegames
      Wind Of Fear is a game where we have to kill different kinds of waves of monsters packing weapons. The main goal is to survive the waves and pump up your own weapons. There is a store where you will buy new weapons, scattered crystals that restore your life are also on the map!

      Controls:
      WASD - Walking
      Shift - Running
      Mouse1 - Attack
      Space - Jump
      ScrolDown - weapon change
      T - Deceleration of time
      G - Bleed your weapon
      Esc - Exit, pause
      Download http://falcoware.com/WindOfFear.php
       



    • By ilovegames
      Continuation of the first part of the game, Invention. While you were on the island exploring the underground laboratory, the infection was busy spreading throughout the world. In this episode, you have to go through a city populated by monsters in search of salvation aided by weapons that you will find during your travels. The gloomy atmosphere, music and atmosphere and a crowd of walking meat will keep you on your toes!
      Download http://falcoware.com/Invention2.php



    • By Jacob Laurits Besenbacher Kjeldsen
       
      Intro - "The challenges of dynamic system design"
      Custom Quest evolved during development, from a minor quest system used for our own needs in our own game production Quest Accepted, to something entirely more dynamic and customizable, now finally released, these are our thoughts on quest design and developing standalone subsystems. 
      Splitting what is a major production for a small indie team, into smaller installments such as a quest system was a good idea we thought, this way we can get some releases out there and fuel the development of our game. But building a system that works for yourself is one thing, building a unity plugin that will let other developers create quests, missions, and objectives, you would never have thought of is something else entirely.
      The first thing we had to realize was that when building a quest system, the task is not to design great quests, the task is to enable the users to create great quests.
      That still meant we had to find out what good quest design is and what a quest really is.
      Our task was to create a system where the user is free to create creative engaging and rewarding mission experiences for their players.
      What is a quest? - "Cut to the core"
      First off, we need to know what a quest really is.
      A quest is the pursuit, search, expedition, task or assignment a person(s) does in order to find, gain or obtain something.
      In games, quests and missions function in many different ways depending on the genre.
      A single game can contain a multitude of different types of quests put together in just as many ways. In an MMO, for instance, quests are vehicles for the story and the player's progression. In many cases they are formulaic and simple, some can even be repeated, there are hundreds of them and everyone can do them. In other games quests are for single player campaigns only, here they shape each level giving the player a sense of purpose.
      Quests can span the whole game or just be a minor optional task on the way, there are so many design philosophies and creative quest designs that we had to narrow it down and really cut to the core of what is needed for good quest design.
      What all quests have in common is the task, the criteria for successful completion of the quest, and the reward, the goal of the quest, what the player gets out of doing what we ask of him.
      Quests cover an incredible variety of tasks so it was important for us to base our decisions on thorough research. In our research, we found that there are three layers to quest design.
      The type, the pattern and the superstructure.
      Quest types exist within quest patterns and quest patterns exist within the quest superstructure.
      We found that there are 8 basic types of quests these are the various tasks/criteria the player must do in order to complete the specific quest.
      There are 12 quest patterns. These are ways designers can use their quests, connect multiple quests set them up in engaging ways or teach players how to interact with and get the most out of the game world creating variety and engaging the player.
      Enveloping the patterns is the quest superstructure, the overall structure of quests in the game, we found that there are two main ways of structuring your quests.
      Historically quest have a quest giver, an NPC or object that informs the player about the quest, what they need to do, the story behind it and perhaps even what their reward will be should they complete the quest.
      Quest types - "Do this, do that"
      The core task each quest consists of, the criteria for completing part of or all of a single quest. These are the actions we want Custom Quest to be able to handle.
      Kill
      Probably the most basic quest type, the task is to kill something in the game, for example; kill 10 goblins. Gather
      Again very simple, the task is to gather x things in the game world, collecting berries or the like. Escort
      The player must escort or follow a person or object from point A to B while keeping it safe. FedX
      The player is the delivery boy, they must deliver an item to a person or point. Defend
      The player has to defend a location from oncoming enemies, often for a set number of waves or time. Profit
      The player must have a certain amount of resources to complete the quest, contrary to gather quests these resources are resources the player would otherwise be able to use himself. Activate
      The player's task is to activate/interact with one or more objects in the game world or talk to a number of NPC’s. In some cases, this must be done in a certain order for a puzzle effect. Search
      Search an area, discover an area of the game world. This is useful for introducing areas of the map to the player and giving them a sense of accomplishment right off the bat, showing them a new quest hub or the like. Quest Patterns - "An engaging experience"
      Tasks are one thing, and in many games, that might be plenty but we wanted custom quest to let the users create chains of quests, specialize them and set them up in ways that draw the player into the experience, there are many ways to go about this.
       
      Arrowhead
      The most basic quest pattern, the quest chain starts out broad and easy, the player has to kill some low-level cronies. The next quest is narrower, the player must kill fewer but tougher enemies, lets say the boss' bodyguards. The last quest is the boss fight, the player has killed the gang and can now kill the boss. This quest pattern is very straightforward and works well, giving rewards either at every stage or only when the boss is dead.  
      Side stub 
      A side stub is an optional part of the overlapping quest. Lets say quest A leads to quest C but there is an option to complete a side objective B, which makes completing C easier or it changes the reward, for example. The player must escape prison, the side stub is “free the other prisoners” in this example escaping with all the prisoners is voluntary but it might make it easier to overpower the guards or the prisoners might reward the player when he gets them out. The side stub differs from a generic side quest in that it is tied to the main quest directly.  
      Continuous side-quests
      These are side-quests that evolve throughout the game, one unlocks the next, but they are also affected by external requirements such as story progress. This pattern is often found with party members in RPG games, where the player must befriend the party member to unlock their story quests.  
       
      Deadline
      As the name implies these quests are time sensitive. The task can be of any type, the important thing is that the quest fails if time runs out. This could also be used for a quest with a side quest where the side quest is timed for extra rewards but the main objective is not.  
       
      Deja-vu quests
      This kind of quest pattern gives the player a quest they have done or seen before. In some cases, this “new” quest will have a twist or something that sets it apart. It can also be the same sort of quest that exists in different areas of the game world, perhaps there is more than one goblin camp? or perhaps the player has to pick berries daily.  
       
      Delayed impact
      Delayed consequences of a previous decision. Often used in games where the story is important and the players’ choices matter. These quests are tied together without the player knowing. Let's say the player is set the optional task of giving a beggar some gold to feed himself. The player gives the beggar a few gold and is on his way. The next time he meets the beggar the beggar has become rich and rewards the player for his kindness with ten times what he gave.  
      One of many
      The player is presented with a number of quests, they have to choose which one to complete, they can only choose one. The others will not be available.  
       
      Hidden quests
      Hidden tasks that aren’t obviously quests at first glance or are hidden away for only the most intrepid players to find. This could be an item the player picks up with an inscription in it if the player then finds the person the inscription is about he can get a reward for delivering it. A good quest pattern for puzzles, these kinds of quests can really make the game world come alive and feel a lot more engaging, allowing the player to uncover secrets, Easter eggs and discover all of the world created for them   
      Moral dilemma
      Punish the bread thief who stole to feed his family? often used in games that have a good/ evil alignment level for the players, these kinds of quests make the player make a choice about what kind of character they want to play, they get to choose if their character is good or evil.  
       
      Side quests
      Optional quests, these quests are often found in level based games where the overall quest must be completed to get to the next level, the player can optionally do some extra tasks to get more points. The important part is that these are optional but they give the player a reward for, getting everything they can out of the game.  
       
      Tournament
      Tournament style quests, a series of quests that get harder as the player progresses. An example could be a gladiatorial arena if the player defeats five enemies one after the other he gets rewarded as the champion of the arena, but if for example, he fails at the third, the whole tournament is failed and he has to start all over from quest 1.  
       
      Vehicle missions
      Despite the name these quests are not confined to being about cars, these are simply quests where the players control scheme changes to complete the quest(s). An example could be; changing from running around in the game world to driving a tank to destroy a fort.  
      Quest superstructure - "The whole package"
      With quest superstructures, we are venturing into general game design. The superstructure is how the player is allowed to complete quests in the game world. It's basically a question of whether the game is “open world” or a linear experience.
       
      The diamond structure 
      The open world model, think games like The Elder Scrolls V: Skyrim, the player is introduced to the game through a quest, but after that, they can go wherever and do whatever quests they want. There are tons of quests of the above types and patterns, the player is free to pick and choose which to do, giving the player the illusion of freedom within the game world (the diamond). However, the game still ends by completing a quest that is locked and always a requirement to complete the game. This can, of course, be varied by different choices the player has made throughout the game or even have multiple endings. Quests can be concentrated into quest hubs, i.e. towns with lots to do or the like, but they don't have to be completed in a linear fashion  
       
       
      Linear hub structure
      This structure consists of a number of required “bridge” quests that need to be completed in order to unlock the next area or “hub”, each hub can have any number of quests, this could be a town full of people in trouble, each with their own quests and quest chains to complete, when they are all done, the player moves on to the next hub through another bridge quest. Limiting the quest size of the hubs will make the quest structure feel more linear and thereby the game linear, and creating larger more open hubs can make the player feel freer.  
       
      Outcome - "So many options!"
      The development of custom quest has been the quest to allow game developers to create quests and missions that use these types. However, no matter how well we have researched, some one will come up with a new and creative way of doing quests.
       
      The solution for us was to make the system more customizable. Letting users convert their quest prefabs to quest scripts that automatically inherits the core functionality, so the user can freely add their own additional functionality on top of the existing core
      Asset development as fuel - "A learning experience"
      Developing this way, splitting the production into sub systems that can function on their own and even be used by others is not something that should be taken lightly, but if you can build something lasting, something others can find value in using, then the final product will be all the better for it. Custom Quest started as a project we thought could be completed in a couple of months, it ended up taking 7.
      In part this is because we realised that if we were going to release the system, we might as well do it right, that meant creating a system that was customizable and robust, a system that can be added to the users game and not the other way around, a system we could be proud of.
      The experience of developing for other developers is quite different to developing a game. One that has made us much stronger as programmers and as a company, it forced us to think in new ways, in order to create a dynamic and customizable solution. Custom quest has evolved from an asset we could use in Quest Accepted, into a tool others can use to create a unique game experience. All in all, the experience has been a good one and Random Dragon is stronger for it, I would, however, recommend thinking about your plugin and extra time before you start developing.
       
       
      Sources:
      www.pcgamesn.com -"We know you aren't stupid" - a quest design master class from CD Projekt RED
      http://www.pcgamesn.com/the-witcher-3-wild-hunt/the-witcher-quest-design-cd-projekt-masterclass
      http://www.gamasutra.com/ - Game Design Essentials: 20 RPGs - http://www.gamasutra.com/view/feature/4066/game_design_essentials_20_rpgs.php?print=1
      Extra credits - Quest Design I - Why Many MMOs Rely on Repetitive Grind Quests https://www.youtube.com/watch?v=otAkP5VjIv8&t=219s
      Extra credits - Quest Design II - How to Create Interesting MMO and RPG Quests https://www.youtube.com/watch?v=ur6GQp5mCYs
      Center for Games and Playable Media - Situating Quests: Design Patterns for Quest and Level Design in Role-Playing Games - http://sokath.com/main/files/1/smith-icids11.pdf
      Center for Games and Playable Media - RPG Design patterns https://rpgpatterns.soe.ucsc.edu/doku.php?id=patterns:questindex
       
      Special thanks to Allan Schnoor, Kenneth Lodahl and Kristian Wulff for feedback, constructive criticism and background materials.
  • Popular Now