Original source of `(seed * 9301 and 49297) % 233280` random algorithm? (2014)
softwareengineering.stackexchange.com
softwareengineering.stackexchange.com
> We discuss how to configure and use turbid, which is a Hardware Random Number Generator (HRNG), also called a True Random Generator (TRNG). It is suitable for a wide range of applications, from the simplest benign applications to the most demanding high-stakes adversarial applications, including cryptography and gaming. It relies on a combination of physical process and cryptological algorithms, rather than either of those separately. It harvests randomness from physical processes, and uses that randomness efficiently. The hash saturation principle is used to distill the data, so that the output is virtually 100% random for all practical purposes. This is calculated based on physical properties of the inputs, not merely estimated by looking at the statistics of the outputs. In contrast to a Pseudo-Random Generator, it has no internal state to worry about. In particular, we describe a low-cost high-performance implementation, using the computer’s audio I/O system.
> The steps above that convert a 64-bit integer to a double precision floating-point value involves both a non-trivial type conversion and a 64-bit floating multiply. They are performance bottlenecks. One can instead directly move the random bits into the right place in the double word with a union structure, a mask, and some 64-bit logical operations; but in our experience this is not significantly faster
It goes on to describe a lagged Fibonacci generator which generates values directly as floating point.
On modern CPUs, its computational advantage over full-precision mapping methods, such as multiplication by a float, is not always clear [1].
On modern hardware, you should instead use a count-leading-zeroes or count-trailing-zeroes instruction on a uniform bit pattern to directly generate the exponent. This is what is done in the Zig standard library:
A very common situation is for instance to plug the random number in a log, in which case you need to use log(1-r) rather than log(r) to avoid an infinite at r=0. The problem is, by doing this simple subtraction you have already lost all the subnormal precision.
[1]: https://en.wikipedia.org/wiki/Linear_congruential_generator
I also think the only additions that might be needed to that are mentions of newer algorithms that are comparatively simple, but better. The subject itself is pretty well-trodden.
Knuth does mention the extremely simple additive random number generator
Xn = (Xn-24 + Xn-55) mod m
It uses 55 words of state (initialized to not all be even), needs only about ten simple instructions to implement (in particular, no multiplications or divisions), has period of at least 2^55-1, and Knuth said it’s very good in practice, isn’t known to be bad, and ends with (in the 1980 second edition of volume 2, with the first edition being from 1968):
The only reason it is difficult to recommend sequence (7) wholeheartedly is that there is very little theory to prove that it does or does not have desirable randomness properties; essentially all we know for sure is that the period is very long, and this is not enough”
I can’t find anything more recent about this RNG. Has it been forgotten, or was it shown to be bad in some important sense?
In the third edition (1998) there are a few more notes, most importantly:
"Lagged Fibonacci generators have been used successfully in many situations since 1958, so it came as a shock to discover in the 1990s that they actually fail an extremely simple, non-contrived test for randomness" with reference to exercise 3.3.2-31 asking "prove that if we generate 79 consecutive random bits ... starting at a random point in the period, the probability is more than 51% that there are more 1s than 0s".
The solution references this paper on the tests: https://arxiv.org/abs/cond-mat/9406054
There's a recommendation to generate X numbers and only use the first Y an order of magnitude smaller, citing Lüscher's RANLUX, but I don't know how much that holds up either.
Since it's too late to edit the earlier post, this is the specifics around discarding (p571):
Lüscher's discarding technique can be used to avoid the bias towards 1s. For example, with lags 55 and 24, no deviation for randomness is observed for random walks of length 1001 when the numbers are generated in batches of 165, if only the first 55 numbers of each batch are used.
It’s an incantation that’s propagated for 50+ years because it’s minimal and effective. Over time, it’s been fully distilled to those properties.
Since comments aren’t essential to being minimal and effective, they don’t survive the distillation.
Think of it like a clever gist that got pasted and shared a hundred times. Even if the original source had explained every step in great detail, with inline comments and deep explanatory discourses and citations to prior art and etc, they’d eventually get trimmed away as fat as people repeatedly prune it down to some “important” bits pasted into their own copies and then later share those trimmed copies, ad infinitum.
This is that, but 50 years out.
These should be documented.
It's a rather weak PRNG of short cycle, so the suspicion is that it's made for particular dispersion properties, such as for a hash table of particular data and size or other bucketing algorithm.
They're trivial to look up, and any modern source would likely outlive the game of telephone of trying to keep such a comment intact correctly.
Maybe not.
https://www.pcg-random.org/posts/does-it-beat-the-minimal-st...
let state = 6, iters = 0;
do {
state = (state * 9301 + 49297) % 233280;
iters++;
} while(state !== 6);
console.log("period is", iters, "iters");
//period is 233280 iters
Except they can't: any seed in the range 230888 thru 233279 will produce a signed integer overflow when multiplied by 9301 (eg 9301*230888 = 0x80001608).
> "According to Steven Levy, IBM Watson researchers discovered differential cryptanalytic attacks in 1974 and were asked by the NSA to keep the technique secret. Coppersmith explains IBM's secrecy decision by saying, "that was because [differential cryptanalysis] can be a very powerful tool, used against many schemes, and there was concern that such information in the public domain could adversely affect national security." Levy quotes Walter Tuchman: "[t]hey asked us to stamp all our documents confidential... We actually put a number on each one and locked them up in safes, because they were considered U.S. government classified. They said do it. So I did it".
Bruce Schneier observed that "It took the academic community two decades to figure out that the NSA 'tweaks' actually improved the security of DES."
> Sometime before its first known publication in 2004, a possible kleptographic backdoor was discovered with the Dual_EC_DRBG's design, with the design of Dual_EC_DRBG having the unusual property that it was theoretically impossible for anyone but Dual_EC_DRBG's designers (NSA) to confirm the backdoor's existence. Bruce Schneier concluded shortly after standardization that the "rather obvious" backdoor (along with other deficiencies) would mean that nobody would use Dual_EC_DRBG.[4] The backdoor would allow NSA to decrypt for example SSL/TLS encryption which used Dual_EC_DRBG as a CSPRNG.[5]
> Members of the ANSI standard group, to which Dual_EC_DRBG was first submitted, were aware of the exact mechanism of the potential backdoor and how to disable it,[6] but did not take sufficient steps to unconditionally disable the backdoor or to widely publicize it. The general cryptographic community was initially not aware of the potential backdoor, until Dan Shumow and Niels Ferguson's publication, or of Certicom's Daniel R. L. Brown and Scott Vanstone's 2005 patent application describing the backdoor mechanism.
> In September 2013, The New York Times reported that internal NSA memos leaked by Edward Snowden indicated that the NSA had worked during the standardization process to eventually become the sole editor of the Dual_EC_DRBG standard,[7] and concluded that the Dual_EC_DRBG standard did indeed contain a backdoor for the NSA.[8] As response, NIST stated that "NIST would not deliberately weaken a cryptographic standard."[9] According to the New York Times story, the NSA spends $250 million per year to insert backdoors in software and hardware as part of the Bullrun program.[10] A Presidential advisory committee subsequently set up to examine NSA's conduct recommended among other things that the US government "fully support and not undermine efforts to create encryption standards".[11]
Then it appears on HN, and more people half guessing, but better content in general.
Based on yesterday's post, BYTE magazine would have actually given an answer with both why and how.
EDIT: Granted, the link DOES go to Wikipedia which has a great explanation, but in general, providing a link and not answer is a poor model because links decay so quickly.
That might be true in many places, and I agree with the general sentiment that the answer should provide an answer and not just a link to an answer. But wikipedia links are generally pretty stable. It’s not some random blog post.
Never found it again on the site. Years ago I remember digging up a link to the question but got the 404 page when I followed it.
I wonder if the answer survives in an old data dump or in the Archive?
(The question was deleted in July 2014 and undeleted in December 2020: https://stackoverflow.com/posts/3637668/revisions , so right now anyone can see it. BTW with ≥10000 reputation one can see deleted posts, per https://stackoverflow.com/help/privileges and https://stackoverflow.com/help/privileges/moderator-tools — e.g., as you mentioned you have ~16k points, try the much-mirrored "programmer joke" deleted question (linked from e.g. https://meta.stackexchange.com/questions/76584).)
Who invented this algorithm and tested the distribution? Is there a paper or something to cite?
That would have made another question.
i don't think it's SE's fault as much as it is a historical rough edge between two fields (computer programming and applied mathematics).
the first constant is klaatu, the second is barada and the third is nikto.
(NR also tends to be fairly rigorous in terms of citations, for the curious)
I googled all these things and I can't still make any sense of your comment except that it's intentionally confusing with some popular fiction references?
I feel like SE being stack exchange is pretty clear here.
The remaining reference is not an acronym or abbreviation, nor do I think it looks like one.
It's doubly famous because Sam Raimi recycled it in "Army of Darkness" as an incantation to dispel the curse of the Necronomicon (book of the dead, portrayed as the arch book of black magic in any number of stories), which our hapless anti-hero Ash fucks up and thus unleashes the armies of the dead on a roughly medieval and wholly unprepared world.
If you like campy horror movies, there is so much camp in Army of Darkness that there's barely any room for the horror. It is technically a sequel but it works as a standalone movie. I watched it years before I finally sat down and watched The Evil Dead.
• One is a historical question: who first used these numbers and when? who copied from where?
• The other is a conceptual question: why might someone choose these numbers, what do they "mean", how do we interpret these constants?
The former is purely a question of facts and there is nothing to "explain the nature of the numbers", and this is what the answerer on Stack Exchange seems to have interpreted it as. Under this interpretation saying things like "the modulus is the period" is not really germane to the question; what's required is to search sources and try to find the chronologically earliest one. (The answer doesn't seem to have done a definitive job, but it's a reasonable start.)
This is like synchronic vs diachronic in linguistics: in the latter interpretation you mainly just want to understand the random-number generator.
> providing a link and not answer is a poor model because links decay so quickly.
Providing a link and not answer is not the stackexchange model. On the Stack Exchange network, such answers are often (not always, of course) commented with a request to expand the answer.
[1] https://en.wikipedia.org/wiki/Fast_inverse_square_root
float Q_rsqrt( float number )
{
long i;
float x2, y;
const float threehalfs = 1.5F;
x2 = number \* 0.5F;
y = number;
i = \* ( long \* ) &y; // evil floating point bit level hacking
i = 0x5f3759df - ( i >> 1 ); // what the fuck?
y = \* ( float \* ) &i;
y = y \* ( threehalfs - ( x2 \* y \* y ) ); // 1st iteration
// y = y \* ( threehalfs - ( x2 \* y \* y ) ); // 2nd iteration, this can be removed
return y;
}(even though I think now the constant above has a paper on why it's actually so good)
> The algorithm was originally attributed to John Carmack, but an investigation showed that the code had deeper roots in the hardware and software side of computer graphics. Adjustments and alterations passed through both Silicon Graphics and 3dfx Interactive, with the original constant being derived in a collaboration between Cleve Moler and Gregory Walsh, while Gregory worked for Ardent Computing in the late 1980s.[3] Walsh and Moler adapted their version from an unpublished paper by William Kahan and K.C. Ng circulated in May 1986.