Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

How/why does this noise function work?

function noise(x)
    x = (x << 13) ^ x;
    return (1.0 - ((x * (x * x * 15731 + 789221) + 1376312589) & 0x7fffffff)
               / 1073741824.0);

I've found it in several places with different primes, but couldn't find an actual explanation of why/how it works.

I know what the code itself is doing (shift, xor, multiply-and-overflow, bitwise-and w/ intmax - 1, etc), but I don't get why those things are done or how it results in acceptable noise.

Why are these operations, why this order? Why primes? I know "because non-primes can generate observable patterns", but why is that?

Why divide by (2**32 - 1)/2? or rather, why does that give a 0..2 value?

share|improve this question

migrated from stackoverflow.com May 28 '11 at 17:44

This question came from our site for professional and enthusiast programmers.

3  
What is a noise function, and what does it mean for a noise function to work? –  Qiaochu Yuan Jun 15 '11 at 19:03
    
Looks like some kind of a PRNG to me. I'm not sure that there is much theory behind this. I added a random tag to attract people who might be more knowledgeable. That 0x7ff... is $2^{31}-1$ and the divisor is $2^{30}$. Therefore the result is 1.0-something, with something in the interval $[0,2)$. So (barring a mistake) the values $\in(-1,1]$. –  Jyrki Lahtonen Jun 15 '11 at 19:09
    
I suppose the word 'noise' is used here in the sense of 'white-noise' process. It seems some kind of pseudo-random number generator –  leonbloy Jun 15 '11 at 19:10
    
I've found it in several places Where? –  leonbloy Jun 15 '11 at 19:11
    
@leonbloy here's one page: freespace.virgin.net/hugo.elias/models/m_perlin.htm –  z0r Oct 27 at 13:09

2 Answers 2

It is a random noise generator. Did Google search on: "noise function" 0x7fffffff

See: http://www.qwerty-games.com/viewvc/Sardon3D/Branches/Networking/src/Noise.cpp?view=markup

http://libnoise.sourceforge.net/noisegen/index.html

share|improve this answer

The function spreads the information contained in the input value across the full 32 bits, then scales it down to the range $-1..1$.

This first part makes the input affect both lower and higher bits:

x = (x << 13) ^ x;

Then that information is spread across the available domain (32 bits) by multiplying and adding it to three constants of different magnitudes - one small, one medium and one large:

digest = x * (x * x * 15731 + 789221) + 1376312589

Finally, the "random" integer is scaled down. 0x7fffffff is $2^{31}$, so the bitwise AND operation makes sure the number is in the range $0..2^{31}$. 1073741824 is $2^{30}$, and $2^{31} \div 2^{30} = 2$, so after the division the range will be $0..2$. Subtracting from $1$ shifts the range to be $-1..1$.

return 1.0 - ((digest & 0x7fffffff) / 1073741824.0);

I'm not sure why the constants need to be prime. Perhaps primes have better bit patterns for this kind of thing.

It's worth noting that the result of this function will be different in different programming languages. It's very likely that there will be an integer overflow, which is language-dependent even for unsigned 32-bit integers. In Python3 the number may be promoted to have more than 32 bits, so it will give some result even though there will be no overflow (but overflow might be desirable to increase randomness). In JavaScript the function fails completely for large numbers, because the bitwise AND always results in 0 for very large numbers (in my tests).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.