# Continuous weighted random distribution, biased toward one end

I am currently contributing to a particle system for our game and developing some emitter shapes.

My uniform random distribution along a line or along a rectangular area works fine - no problem.

But now I would like to have something like a 1 dimensional gradient in this distribution. This would mean for example lower values are more common than higher values.

I don't know what would be appropriate mathematical terms for this problem, so my search skills are rather useless with this one. I need something that is computationally simple, as the particle system needs to be efficient.

Take a look at this picture: It shows the process of mapping a (random) value to a curve. Suppose you generate a uniformly-distributed random value X, ranging from 0 to 1. By mapping this value to a curve - or, in other words, using f(X) instead of X - you can skew your distribution in whatever way you like.

In this picture, first curve makes higher values more likely; second makes lower values more likely; and the third one makes values cluster in the middle. The exact formula of the curve is not really important, and can be chosen as you like.

For example, first curve looks a bit like square root, and second - like square. Third one is a bit like cube, only translated. If you consider square root to be too slow, first curve also looks like f(X)=1-(1-X)^2 - an inversion of square. Or a hyperbole: f(X)=2X/(1+X).

As a fourth curve shows, you can simply use a precomputed lookup table. Is looks ugly as a curve, but will probably be good enough for a particle system.

This general technique is very simple and powerful. Whatever distribution you need, just imagine a curve mapping, and you'll devise a formula in no time. Or, if your engine has an editor, just make a visual editor for the curve!

• thank you very much for your very thorough and understandable explanation. all of the other posts were very helpful too, but i really could understand your post the easiest and fastest. it sticked out bc it really hit the spot for my way of understanding things. and the aspects you are explaining are exactly what i was looking for (or wandering about)! it will enable me to use this in a lot of cases in future. so thx again!!! btw, i played around with some of your curves of them and it works like charm. – didito May 24 '11 at 12:11
• FYI: These are called quantile functions: en.wikipedia.org/wiki/Quantile_function – Neil G May 24 '11 at 19:27

A longer explanation:

If you have a desired probability distribution such as the gradient @didito asked for, you can describe is as a function. Let's say you want a triangular distribution, where the probability at 0 is 0.0, and you want to pick a random number from 0 to 1. We might write it as y = x.

The next step is to calculate the integral of this function. In this case, it's $$\\int x=\frac{1}{x^2}\$$. Evaluated from 0 to 1, that's ½. That makes sense — it's a triangle with base 1 and height 1, so its area is ½.

You then pick a random point uniformly from 0 to the area (½ in our example). Let's call this z. (We're picking uniformly from the cumulative distribution.)

The next step is to go backwards, to find what value of x (we'll call it x̂) corresponds to an area of z. We're looking for $$\\int x=\frac{1}{x^2}\$$, evaluated from 0 to x̂, being equal to z. When you solve for $$\\frac{1}{x̂^2}=z\$$, you get $$\x̂ = \sqrt{2z}\$$.

In this example, you pick z from 0 to ½ and then the desired random number is $$\\sqrt{2z}\$$. Simplified, you can write it as $$\\sqrt{rand(0, 1)}\$$ — exactly what eBusiness recommended.

• thx for your valueable input. i always like to hear how skilled people solve problems. but i still need to wrap my head around it to be honest... – didito May 24 '11 at 9:47
• this is awesome. I always made sqrt(random()) my entire life but I came to it empirically. Trying to tie a random number to a curve, and it did work. Now that I'm a little more Math skilled, knowing why it works is very valuable! – Gustavo Maciel Sep 22 '15 at 19:22

You'd probably get a close approximation to what you want by utilizing an exponential system.

Make the x based on something like 1-(rnd^value) (Assuming rnd is between 0 and 1) and you'll get a few different behaviors of left to right skewing based on what you use. A higher value will get you a more skewed distribution

You can use an online graphing tool to get some rough ideas on the behaviors different equations will give you before placing them in, or you can just fiddle with the equations directly in your particle system, depending what style is more to your tastes.

EDIT

For something like a particle system where CPU time per particle is very important, using Math.Pow (or language equivalent) directly can lead to a decrease in performance. If more performance is desired, and value isn't being changed in run-time, consider switching to an equivalent function such as x*x instead of x^2.

(Fractional exponents could be more of an issue, but someone with a stronger math background than I could probably come up with a good way to create an approximation function)

• Instead of using a graphing program, you can just plot the Beta distribution as this is a special case. For a given value, this is Beta(value, 1). – Neil G May 24 '11 at 3:48
• thx. i tried plotting some graphs and i think it could get me where i want. – didito May 24 '11 at 9:36
• @Neil G thanks for the tip with "beta distribution" - this sounds interesting and useful ... i'll do some research on that topic – didito May 24 '11 at 9:37

The term you are looking for is Weighted Random Numbers, most of the algorithms I have seen use trig functions, but I think I figured out a way that will be efficient:

Create a table/array/List(whatever) that holds a multiplier value for the random function. Fill it out by hand or programatically...

randMulti= {.1,.1,.1,.1,.1,.1,.2,.2,.3,.3,.9,1,1,1,}


...then Multiply random by a randomly chosen randMultiand finally by the max Value of the distribution...

weightedRandom = math.random()*randMulti[Math.random(randMulti.length)]*maxValue


I do believe that this will be much faster than using sqrt, or other more computationally complex functions, and will allow for more custom grouping patterns.

• If you can sacrifice the memory, a table of 100 pre-computed values would be faster (and slightly more accurate). I doubt the user would be able to distinguish between the full and pre-computed versions. – Daniel Blezek May 23 '11 at 18:43
• @Daniel it would be faster, but with 100 random values, it is pretty easy to see repeating patterns. – AttackingHobo May 23 '11 at 18:44
• Just because there appears to be a repeating pattern doesn't mean it isn't random. The essence of randomness is its unpredictability, which literally means that as much as one can't predict that there won't be a pattern, one also can't predict that there could be one (at least for a short time). You'll have to do some testing, but if you do find patterns with multiple tests using different seeds, then your algorithm for generating pseudo-random numbers may need to be reviewed. – Randolf Richardson May 24 '11 at 3:16
• @AttackingHobo thx for that trick. i like the use of LUTs. and the formula is quite easy to understand. i did not think of it this way before. not seeing the wood for the trees ... :) also i think repeating patterns should be avoided but probably would not be recognized in this case anyway. still, precomputing all values would hurt the visual experience. anyway, thx for reminding me that this is a factor to consider on the topic of randomness ... – didito May 24 '11 at 9:44
• also thanks for bringing up the term Weighted "Random Numbers"! – didito May 24 '11 at 12:04

I think what you ask for is the distribution achieved using a square root function.

[position] = sqrt(rand(0, 1))


This will give a distribution in the single dimension field [0, 1] where the probability for a position is equivalent to that position, i.e. a "triangular distribution".

Alternate squareroot-free generation:

[position] = 1-abs(rand(0, 1)-rand(0, 1))


A square root in optimal implementation is just a few multiplication and sum commands with no branches. (See: http://en.wikipedia.org/wiki/Fast_inverse_square_root). Which one of these two functions are faster may vary depending on platform and random generator. On an x86 platform for instance it would take only a few unpredictable branches in the random generator to make the second method slower.

• The probability of a position won't be equal to the position (that's mathematically impossible - trivially, the domain and range of the function includes both 0.50 and 0.51), nor is it a triangular distribution. (en.wikipedia.org/wiki/Triangular_distribution) – user744 May 23 '11 at 18:45
• While sqrt gives some interesting patterns, particle systems generally need to be very CPU light per particle, so I would recommend avoiding square roots (which are computationally slow) where possible. You can sometimes get away with just pre-computing them, but it can make your particles have noticeable patters over time. – Lunin May 23 '11 at 20:25
• @Joe Wreschnig, did you read that Wikipedia article yourself, stuff a=0, b=1, c=1 into the generation formula and you get the formula in my post. – aaaaaaaaaaaa May 23 '11 at 22:13
• @Lunin, why are you complaining about the square root when you have got an exponent in your answer? – aaaaaaaaaaaa May 23 '11 at 22:34
• @Lunin: Performance theory is a pretty neglected field, a lot of what people think they know where approximately correct 30 years ago when ALUs were big expensive and slow. Even the exponent function which you have just discovered to be a quite slow arithmetic function is rarely a highly significant performance sinner. Branching (using an if statement) and cache misses (reading a piece of data not currently residing in cache) are typically what cost the most performance. – aaaaaaaaaaaa May 24 '11 at 19:23

Just use a Beta distribution:

• Beta(1,1) is flat
• Beta(1,2) is a linear gradient

etc.

The two shape parameters need not be integers.

• thx for your help. as stated above, beta distribution sounds interesting. but i cannot make sense of the content of the wikipedia page yet. or a formula / code. well, also i don't have time right now to investigate further :s i see that boost has code for beta distributions, but this would be overkill. well, i guess i need to go through it first and then write my own simplified version. – didito May 24 '11 at 10:07
• @didito: It's not so hard. You just replace your uniform_generator() call with gsl_ran_beta(rng, a, b). See here: gnu.org/software/gsl/manual/html_node/… – Neil G May 26 '11 at 0:19
• thx for the hint. i do not use GSL (actually have not heard about it before), but good call. i will check the source! – didito May 26 '11 at 16:41
• @didito: In that case, I would go with Lunin's solution. Good luck. – Neil G May 26 '11 at 17:19

Even simpler, depending on the speed of your random generator, you can just generate two values and average them.

Or, even more simple, where X is the result of the rng, first double y = double(1/x);, x = y*[maximum return value of rng];. This will weight numbers exponentially to the lower numbers.

Generate and average more values to increase the likelihood of getting values closer to center.

Of course this only works for standard bell curves distributions or "folded" versions thereof*, but with a fast generator, it might be faster and simpler than using various math functions like sqrt.

You can find all sorts of research on this for dice bell curves. In fact, Anydice.com is a good site which generates graphs for various methods of rolling dice. Though you are using an RNG, the premise is the same, as are the results. So it is a good spot for seeing the distribution before even coding it.

*Also, you can "fold" the result distribution along an axis by taking the axis and subtracting the averaged result then adding the axis. For example, you want lower values to be more common, and lets say you want 15 to be your minimum value and 35 to be your max value, a range of 20. So you generate and average together two values with a range of 20 (twice the range you want), which will give a bellcurve centered on 20 (we subtract five at the end to shift the range from 20 to 40, to 15 to 35). Take the generated numbers X and Y.

Final number,

z =(x+y)/2;// average them
If (z<20){z = (20-z)+20;}// fold if below axis
return z-5;// return value adjusted to desired range


z= (x+y)/2;