Pierre Alexandre Tremblay

I am looking for C code to obtain 4 quasi-random number between 0. 

Is there a good place to find some help on this? I do not care that 

much if the random is pure or not, I just want some good number 

Does it worth me having an altivec call for 4 randoms (if such a 

I have an intuition that I could avoid the division by casting 

Any help welcome, even sending me to a funky manual ;-)

I am looking for C code to obtain 4 quasi-random number between 0.  
and 1. per sample.

Is there a good place to find some help on this?  I do not care that  
much if the random is pure or not, I just want some good number  
crushing...

Does it worth me having an altivec call for 4 randoms (if such a  
thing exist)?

I have an intuition that I could avoid the division by casting  
somehow, but I am not sure...

the-most-efficient-way-to-obtain-quasi-random-number-between-0-and-1

On 06-11-29, at 1355, Pierre Alexandre Tremblay wrote:

> Any help welcome, even sending me to a funky manual ;-)

http://www.google.com/search?q=random+number+c+-c%2B%2B+code

On 06-11-29, at 1355, Pierre Alexandre Tremblay wrote:
>
> Any help welcome, even sending me to a funky manual ;-)
>
http://www.google.com/search?q=random+number+c+-c%2B%2B+code
http://www.ciphersbyritter.com/NEWS4/ 
RANDC.HTM#369B5E30.65A55FD1@stat.fsu.edu

The easiest way to avoid division is to multiply with

    const double kOneOverMaxULong = 1.0 / 4294967296.0;

(The division is calculated once at compile time rather than on every 

call to your RNG). A really smart optimizing compiler would do that 

for you, but since you're probably using XCode, better do the above.-)

There is a technique to map unsigned ints to double by typecasting 

and some fancy bitshifting. In my experience it is _not_ 

significantly faster than converting to double and multiplying. I can 

dig up the code if you really want it, I originally saw it in a post 

by James McCartney to the musicdsp list (which is probably still 

There is the feedback shift register technique which is probably the 

fastest out there. However it only produces 1s and 0s, not 32-bit words.

Tausworthe 88 is very fast (a few shifts and XORs) and has a very 

LC (what you're doing) is one of the fastest but has poor random 

quality (too many correlations pop up). You say you don't care.

I have numerous random processes in MSP objects in Litter Power that 

require as many as 4 pseudo-randoms per sample and, in my experience, 

the core RNG is not the real bottleneck. I recently implemented a 

major speed-up to lp.gsss~ by using a clever algorithm that avoids 

the trig functions required in the standard Box-Muller algorithms. 

What I have done for MSP (and Jitter) objects is to write the code 

such that all data is kept in registers for the duration of a perform 

loop. That made a significant performance improvement.

What are you trying to do that Litter Power doesn't already do?

On 29-Nov-2006, at 22:55, Pierre Alexandre Tremblay wrote:

> I am looking for C code to obtain 4 quasi-random number between 0. 

> Is there a good place to find some help on this? I do not care 

> that much if the random is pure or not, I just want some good 

> Does it worth me having an altivec call for 4 randoms (if such a 

> I have an intuition that I could avoid the division by casting 

Peter Castine +--> Litter Power & Litter Bundle for Jitter

Interface Building for |home | chez nous|

Max/MSP Extremely cool |bei uns | i nostri|

	const double kOneOverMaxULong = 1.0 / 4294967296.0;

(The division is calculated once at compile time rather than on every  
call to your RNG). A really smart optimizing compiler would do that  
for you, but since you're probably using XCode, better do the above.-)

There is a technique to map unsigned ints to double by typecasting  
and some fancy bitshifting. In my experience it is _not_  
significantly faster than converting to double and multiplying. I can  
dig up the code if you really want it, I originally saw it in a post  
by James McCartney to the musicdsp list (which is probably still  
available to the determined Googler).

There is the feedback shift register technique which is probably the  
fastest out there. However it only produces 1s and 0s, not 32-bit words.

Tausworthe 88 is very fast (a few shifts and XORs) and has a very  
good pedigree.

LC (what you're doing) is one of the fastest but has poor random  
quality (too many correlations pop up). You say you don't care.

I have numerous random processes in MSP objects in Litter Power that  
require as many as 4 pseudo-randoms per sample and, in my experience,  
the core RNG is not the real bottleneck. I recently implemented a  
major speed-up to lp.gsss~ by using a clever algorithm that avoids  
the trig functions required in the standard Box-Muller algorithms.  
What I have done for MSP (and Jitter) objects is to write the code  
such that all data is kept in registers for the duration of a perform  
loop. That made a significant performance improvement.

> Dear all
>
> I am looking for C code to obtain 4 quasi-random number between 0.  
> and 1. per sample.
>
> Right now, I use the good old
>
> seed = seed * 1103515245 + 12345;
>
> and I divise by 4294967296.0
>
> but is is cycle consuming...
>
> Is there a good place to find some help on this?  I do not care  
> that much if the random is pure or not, I just want some good  
> number crushing...
>
> Does it worth me having an altivec call for 4 randoms (if such a  
> thing exist)?
>
> I have an intuition that I could avoid the division by casting  
> somehow, but I am not sure...
>
> Any help welcome, even sending me to a funky manual ;-)
>
> p.a.

--------------    http://www.bek.no/~pcastine/Litter/    -------------
Peter Castine             +--> Litter Power & Litter Bundle for Jitter
                                Universal Binaries on the way
iCE:  Sequencing,  Recording &
       Interface  Building  for                   |home    | chez nous|
       Max/MSP   Extremely cool                   |bei uns |  i nostri|
       http://www.dspaudio.com/                   http://www.castine.de

On 29-Nov-2006, at 23:57, Pierre Alexandre Tremblay wrote:

Oh, the other obvious thing... you *are* inlining the RNG in your 

Oh, the other obvious thing... you *are* inlining the RNG in your  
perform method, aren't you?

I was hoping for your answer to my call for help ;-)

>     const double kOneOverMaxULong = 1.0 / 4294967296.0;

> There is a technique to map unsigned ints to double by typecasting 

> and some fancy bitshifting. In my experience it is _not_ 

> significantly faster than converting to double and multiplying. I 

> can dig up the code if you really want it, I originally saw it in a 

> post by James McCartney to the musicdsp list (which is probably 

> still available to the determined Googler).

I was exploring that avenue yesterday. A great site to get my head 

thinkin of masking with 3FFF FFFF and then typecast to float and 

> Tausworthe 88 is very fast (a few shifts and XORs) and has a very 

> LC (what you're doing) is one of the fastest but has poor random 

> quality (too many correlations pop up).

at all! I just want 4 random values per sample.

> I have numerous random processes in MSP objects in Litter Power 

> that require as many as 4 pseudo-randoms per sample and, in my 

> experience, the core RNG is not the real bottleneck. I recently 

> implemented a major speed-up to lp.gsss~ by using a clever 

> algorithm that avoids the trig functions required in the standard 

> Box-Muller algorithms. What I have done for MSP (and Jitter) 

> objects is to write the code such that all data is kept in 

> registers for the duration of a perform loop. That made a 

any hints of how I should do this? My next step was to use altivec 

for this number crushing, because when I remove my random stuff, I 

> Oh, the other obvious thing... you *are* inlining the RNG in your 

nope. I have done a function called alea() that does my LC, but 

where can I read about inlining? Sorry to be thick here.

> What are you trying to do that Litter Power doesn't already do?

I want to improve my butt~ external. It is a dirty filter - it 

simply adds some noise on the coefficient of a biquad. The code will 

be public domain as soon as I release this version 2. It is 

> 	const double kOneOverMaxULong = 1.0 / 4294967296.0;

> There is a technique to map unsigned ints to double by typecasting  
> and some fancy bitshifting. In my experience it is _not_  
> significantly faster than converting to double and multiplying. I  
> can dig up the code if you really want it, I originally saw it in a  
> post by James McCartney to the musicdsp list (which is probably  
> still available to the determined Googler).

I was exploring that avenue yesterday.  A great site to get my head  
around my intuition was http://babbage.cs.qc.edu/IEEE-754/.  I was  
thinkin of masking with 3FFF FFFF and then typecast to float and  
substract one...

> Tausworthe 88 is very fast (a few shifts and XORs) and has a very  
> good pedigree.
> LC (what you're doing) is one of the fastest but has poor random  
> quality (too many correlations pop up).

at all!  I just want 4 random values per sample.

> I have numerous random processes in MSP objects in Litter Power  
> that require as many as 4 pseudo-randoms per sample and, in my  
> experience, the core RNG is not the real bottleneck. I recently  
> implemented a major speed-up to lp.gsss~ by using a clever  
> algorithm that avoids the trig functions required in the standard  
> Box-Muller algorithms. What I have done for MSP (and Jitter)  
> objects is to write the code such that all data is kept in  
> registers for the duration of a perform loop. That made a  
> significant performance improvement.

any hints of how I should do this?  My next step was to use altivec  
for this number crushing, because when I remove my random stuff, I  
divide the processor load by 4...

> Oh, the other obvious thing... you *are* inlining the RNG in your  
> perform method, aren't you?

nope.  I have done a function called alea() that does my LC, but  
where can I read about inlining?  Sorry to be thick here.

I want to improve my butt~ external.  It is a dirty filter - it  
simply adds some noise on the coefficient of a biquad.  The code will  
be public domain as soon as I release this version 2.  It is  
shamelessly simple, but sounds so good!

It's pretty close. LC looks like it should be a bit faster, but I 

would want to benchmark before making a call. It could even depend on 

In any case, replacing div by multiplication and inlining (see below) 

will bring far more gain than the difference between the two algorithms.

>> I have numerous random processes in MSP objects in Litter Power 

>> that require as many as 4 pseudo-randoms per sample and, in my 

>> experience, the core RNG is not the real bottleneck. I recently 

>> implemented a major speed-up to lp.gsss~ by using a clever 

>> algorithm that avoids the trig functions required in the standard 

>> Box-Muller algorithms. What I have done for MSP (and Jitter) 

>> objects is to write the code such that all data is kept in 

>> registers for the duration of a perform loop. That made a 

> any hints of how I should do this? My next step was to use altivec 

> for this number crushing, because when I remove my random stuff, I 

Really depends on what you're doing. I spent many hours on the web 

and in the library (yes! physical relocation to a depository of dead 

trees!!) researching alternatives in the literature before I found an 

BTW, for all we go on about being efficient in MSP, it was doing 

Gaussian noise in Jitter where the optimizations really paid off. 

>> Oh, the other obvious thing... you *are* inlining the RNG in your 

> nope. I have done a function called alea() that does my LC, but 

> where can I read about inlining? Sorry to be thick here.

    static inline double alea(void /*or whatever*/)

That one reserved word will speed up processing in this case by 

While we're here, you're not calling it in a loop, are you?

>> What are you trying to do that Litter Power doesn't already do?

> I want to improve my butt~ external. It is a dirty filter - it 

> simply adds some noise on the coefficient of a biquad. The code 

> will be public domain as soon as I release this version 2. It is 

> shamelessly simple, but sounds so good!

It's pretty close. LC looks like it should be a bit faster, but I  
would want to benchmark before making a call. It could even depend on  
processor architecture.

In any case, replacing div by multiplication and inlining (see below)  
will bring far more gain than the difference between the two algorithms.

>> I have numerous random processes in MSP objects in Litter Power  
>> that require as many as 4 pseudo-randoms per sample and, in my  
>> experience, the core RNG is not the real bottleneck. I recently  
>> implemented a major speed-up to lp.gsss~ by using a clever  
>> algorithm that avoids the trig functions required in the standard  
>> Box-Muller algorithms. What I have done for MSP (and Jitter)  
>> objects is to write the code such that all data is kept in  
>> registers for the duration of a perform loop. That made a  
>> significant performance improvement.
>
> any hints of how I should do this?  My next step was to use altivec  
> for this number crushing, because when I remove my random stuff, I  
> divide the processor load by 4...

Really depends on what you're doing. I spent many hours on the web  
and in the library (yes! physical relocation to a depository of dead  
trees!!) researching alternatives in the literature before I found an  
appropriate algorithm.

BTW, for all we go on about being efficient in MSP, it was doing  
Gaussian noise in Jitter where the optimizations really paid off.  
Audio is _pippifax_ compared to video.

>> Oh, the other obvious thing... you *are* inlining the RNG in your  
>> perform method, aren't you?
>
> nope.  I have done a function called alea() that does my LC, but  
> where can I read about inlining?  Sorry to be thick here.

	static inline double alea(void /*or whatever*/)
		{
		// whatever
		}

That one reserved word will speed up processing in this case by  
something in the 20-50% ballpark.

	for (i = 0; i < 4; i += 1)
		x[i] = alea();

	x0 = alea();
	x1 = alea();
	x2 = alea();
	x3 = alea();

>> What are you trying to do that Litter Power doesn't already do?
>
> I want to improve my butt~ external.  It is a dirty filter - it  
> simply adds some noise on the coefficient of a biquad.  The code  
> will be public domain as soon as I release this version 2.  It is  
> shamelessly simple, but sounds so good!

The multiplication instead of division, but more important once 

instead of 4 times, did save more than 25% of horsepower!

So to make it clear, the version one was:

        yn = b0a0*in0 + b1a0*in1 + b2a0*in2 - a1a0*ou1 - a2a0*ou2;

        in2 = in1 * (1. - (sale * alea() / 4294967296.0));

        in1 = in0 * (1. - (sale * alea() / 4294967296.0));

        ou2 = ou1 * (1. - (sale * alea() / 4294967296.0));

        ou1 = yn * (1. - (sale * alea() / 4294967296.0));

where alea gives me an unsigned long and sale is a dirtiness factor.

        in2 = in1 * (1. - (sale * alea()));

        in1 = in0 * (1. - (sale * alea()));

        ou2 = ou1 * (1. - (sale * alea()));

        ou1 = yn * (1. - (sale * alea()));

where sale is now the dirtiness factor multiplied by the 

The inline did not make any difference, which surprised me. If I 

understood well, I just have to change my declaration by adding 

I still want to optimise, because the following code is still 75% 

faster. The only thing I remove is the dirtiness in the biquad 

        in2 = in1;                                                        // * (1. - (sale * alea()));

        in1 = in0;                                                        // * (1. - (sale * alea()));

        ou2 = ou1;                                                        // * (1. - (sale * alea()));

        ou1 = yn;                                                        // * (1. - (sale * alea()));

I am thinking of going vectorial since I have 4 times the same maths, 

The multiplication instead of division, but more important once  
instead of 4 times, did save more than 25% of horsepower!

	while (n--)
	{
		in0 = *entree++;
		yn = b0a0*in0 + b1a0*in1 + b2a0*in2 - a1a0*ou1 - a2a0*ou2;
		*sortie++ = yn;
		in2 = in1 * (1. - (sale * alea() / 4294967296.0));
		in1 = in0 * (1. - (sale * alea() / 4294967296.0));
		ou2 = ou1 * (1. - (sale * alea() / 4294967296.0));
		ou1 = yn * (1. - (sale * alea() / 4294967296.0));
	}

where alea gives me an unsigned long  and sale is a dirtiness factor.

	while (n--)
	{
		in0 = *entree++;
		yn = b0a0*in0 + b1a0*in1 + b2a0*in2 - a1a0*ou1 - a2a0*ou2;
		*sortie++ = yn;
		in2 = in1 * (1. - (sale * alea()));
		in1 = in0 * (1. - (sale * alea()));
		ou2 = ou1 * (1. - (sale * alea()));
		ou1 = yn * (1. - (sale * alea()));
	}

where sale is now the dirtiness factor multiplied by the  
kOneOverMaxULong constant as proposed...

The inline did not make any difference, which surprised me.  If I  
understood well, I just have to change my declaration by adding  
'static inline' to it?

--
I still want to optimise, because the following code is still 75%  
faster.  The only thing I remove is the dirtiness in the biquad  
memory swap...

	while (n--)
	{
		in0 = *entree++;
		yn = b0a0*in0 + b1a0*in1 + b2a0*in2 - a1a0*ou1 - a2a0*ou2;
		*sortie++ = yn;
		in2 = in1;														// * (1. - (sale * alea()));
		in1 = in0;														// * (1. - (sale * alea()));
		ou2 = ou1;														// * (1. - (sale * alea()));
		ou1 = yn;														// * (1. - (sale * alea()));
	}

--
I am thinking of going vectorial since I have 4 times the same maths,  
but maybe it is not relevant...

I haven't time to read this thread totally now, but I do have an audio rate rand generator (between -1 an 1 I think) for max which could be modified to produce numbers between 0 and 1. It's a replacemnet for noise~ that seeds differently (but not randomly) for each new instance, up to 600 odd different versions. It's not ultra efficient, but it's not that much more expensive than noise~, so if your results are not as efficient as noise~ than might be useful to you. I can send it to you off-list if you'd like, both as a UB external, and also as code.

On 1-Dec-2006, at 14:14, Pierre Alexandre Tremblay wrote:

> The inline did not make any difference, which surprised me. If I 

> understood well, I just have to change my declaration by adding 

Surprises me a little, too. But some details of inline handling are 

There is a very slight chance that a really intelligent compiler 

would already be inlining automatically, but that seems unlikely to 

me. You could look at the disassembled code to check. (Reading 

assembly code is one of my favorite pastimes. Pas.)

1) The definition of alea() (not just the declaration) needs to be 

2) The definition of alea() needs to be available to the file using 

it (either directly in the file or #include'd)

3) For some compilers it may be necessary for the definition to occur 

If you're only using alea() your perform method, then something like

    static UInt32 sSeed = 0;    // Initialize to uptime()

                    // or something from main()

     const double kFactor = 1.0 / 4294967296.0;

     sSeed = 123456789 * sSeed + 987654321; // *really* bad RNG

     return (double) sSeed * kFactor;

should convince any compiler to do the right thing. Defining the 

function static inline has the side-effect that you should not need 

to declare it, providing the definition occurs before the first call 

(Who really regrets aiding and abetting anyone using Linear 

Congruence as a RNG... c'est comme manger de sanglier avec sauce de 

On 1-Dec-2006, at 14:14, Pierre Alexandre Tremblay wrote:
> The inline did not make any difference, which surprised me.  If I  
> understood well, I just have to change my declaration by adding  
> 'static inline' to it?

Surprises me a little, too. But some details of inline handling are  
compiler dependent.

The most efficient way to obtain quasi-random number between 0. and 1.