next »

[zovirl]

Here's a piece of code for a random number generator. I'm trying figure out the name of the algorithm it is implementing:

Code:

double IntegerNoise (int n)
{
  n = (n >> 13) ^ n;
  int nn = (n * (n * n * 60493 + 19990303) + 1376312589) & 0x7fffffff;
  return 1.0 - ((double)nn / 1073741824.0);
}

Now, this code shows up on dozens of sites...all you have to do to find them is search for the primes: google.com/search?q=60493+19990303+1376312589. I happened to find it on libnoise.sourceforge.net, but this popular page on perlin noise has a very similar implementation (different primes, but very similar code): http://freespace.virgin.net/hugo.elias/models/m_perlin.htm

None of the sites say what the name of the algorithm is, though. Most say something like "I found this on the internet, it seems to work..."

It looks related to either Linear congruential generators (http://en.wikipedia.org/wiki/Linear_congruential_generator) or maybe multiply-with-carry (http://en.wikipedia.org/wiki/Multiply-with-carry). It doesn't look exactly like either of those though.

Anyone recognize this?

[Evan Balster]

No idea.  D:

Is it a lagged fibonacci?

[zovirl]

I don't know. According to Wikipedia, Freeciv uses lagged-fibbonaci, and http://svn.gna.org/viewcvs/freeciv/trunk/utility/rand.c?view=markup looks a lot more complicated than what I have. I think that means this isn't lagged-fibbonaci, but that's pretty tenuous

[eigenbom]

Algorithmic archaeology!

I found an early reference in Gfx Gems II, dating back to 1988 ... Maybe you should email Greg Ward (the author) to ask him where he got it from...

http://tog.acm.org/resources/GraphicsGems/gemsii/noise3.c

[Nix]

It seems like one of those techniques that's so trivial and well-known it's not associated with a title. Maybe there's a paper lying out there about it though.

[zovirl]

Algorithmic archaeology!

I found an early reference in Gfx Gems II, dating back to 1988 ... Maybe you should email Greg Ward (the author) to ask him where he got it from...

http://tog.acm.org/resources/GraphicsGems/gemsii/noise3.c

Nice find!  I emailed Greg Ward and he didn't remember its origins either. Lost to the depths of time, I guess?  It is kind of strange since many of the other well-known PRNG algorithms are even simpler (and therefore easier to copy/paste). Oh well.

[eigenbom]

Algorithmic archaeology!

I found an early reference in Gfx Gems II, dating back to 1988 ... Maybe you should email Greg Ward (the author) to ask him where he got it from...

http://tog.acm.org/resources/GraphicsGems/gemsii/noise3.c

Nice find!  I emailed Greg Ward and he didn't remember its origins either. Lost to the depths of time, I guess?  It is kind of strange since many of the other well-known PRNG algorithms are even simpler (and therefore easier to copy/paste). Oh well.

Ah that's too bad, But at least we now know GW didn't come up with it. Just call it the Pre-Ward method.

B

[zovirl]

Ah that's too bad, But at least we now know GW didn't come up with it. Just call it the Pre-Ward method.

Actually, he said he didn't remember if he came up with it or if he grabbed it from someplace else, so we don't even know that much

[Mipe]

I recall seeing this algorithm in Perlin noise...

[Nix]

I recall seeing this algorithm in Perlin noise...

There are lots of ways to create Perlin noise, so there are probably a number of implementations that use this as an RNG

[Jasmine]

It comes from a branch of mathematics called elliptic curves.

It's a pretty deep subject, and it was all the rage in the 1960/70s.

If you want to give it a name, it's an elliptic curve pseudorandom number generator.


What are elliptic curves you ask?


The number systems we use are characterised by two operators: addition and multiplication. And these two operators make sense and behave nicely. Numbers are nicely structured additively and multiplicatively.

In mathematics we call such number systems Rings.

Well it was discovered that there is actually another operation through which numbers behave nicely, but it is extremely complicated and arcane.

Imagine if all you ever knew was addition. Imagine trying to live without knowledge of multiplication. Imagine how flat the world would feel, and how impossible some things would be. Then one day you discovered multiplication - that would be a major discovery, yes? Your understanding of quantity would be dramatically changed.

Elliptic curves are exactly like that! Discovering them is as eye opening as the discovery of multiplication.

[zovirl]

Fascinating...the equation does have the form ax^3 + bx + c, yet searching for "elliptic curve pseudorandom number generator" yields very little information...mostly scholarly articles, and mostly post-1988.

[Jasmine]

That's probably because the internet only came about post-1988. All the original articles will be in old books in old libraries. Some of the research may be classified too as it has implications for code breaking.

Try searching for the acronym;

http://www.google.com/search?q=ecrng