prng

some implementations of pseudo-random number generators, wip
git clone git://nihaljere.xyz/prng
Log | Files | Refs

commit 6bcc766b4e3d6670aa8dd0af1ec96751642188b8
Author: Nihal Jere <nihal@nihaljere.xyz>
Date:   Fri,  3 Apr 2020 17:35:13 -0500

initial commit

Diffstat:
Aacorn/README | 8++++++++
Aacorn/acorn.c | 27+++++++++++++++++++++++++++
Aacorn/acorn.h | 13+++++++++++++
Amtwister/README.md | 45+++++++++++++++++++++++++++++++++++++++++++++
Amtwister/mtwister.c | 76++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Amtwister/mtwister.h | 16++++++++++++++++
6 files changed, 185 insertions(+), 0 deletions(-)

diff --git a/acorn/README b/acorn/README @@ -0,0 +1,8 @@ +This is a simple C implementation of +[ACORN](https://en.wikipedia.org/wiki/ACORN_(PRNG)), +a pseudorandom number generator. The implementation is modeled after +[this](https://github.com/ESultanik/mtwister) +implementation of a Mersenne Twister. The implementation is very simple and +readable, and tries to be faithful to the mathematical definition described +[here](http://www.acorn.wikramaratna.org/concept.html), +where you can also find a FORTRAN implementation. diff --git a/acorn/acorn.c b/acorn/acorn.c @@ -0,0 +1,27 @@ +#include "acorn.h" + +unsigned long STATE_VECTOR_M = 1 << 30; + +AcornState +acorn_seed(unsigned long seed) +{ + AcornState acorn; + acorn.state[0] = seed & 0xffffffff; + for (acorn.index=1; acorn.index<STATE_VECTOR_LENGTH; ++acorn.index) + acorn.state[acorn.index] = (69069 * acorn.state[acorn.index-1]) % STATE_VECTOR_M; + return acorn; +} +unsigned long +acorn_get_long(AcornState* acorn) +{ + for (acorn->index = 1; acorn->index < STATE_VECTOR_LENGTH; ++acorn->index) { + acorn->state[acorn->index] += acorn->state[acorn->index-1]; + acorn->state[acorn->index] %= STATE_VECTOR_M; + } + + return acorn->state[STATE_VECTOR_LENGTH - 1]; +} +double acorn_get_double(AcornState* acorn) { + unsigned long val = acorn_get_long(acorn); + return (double)val / STATE_VECTOR_M; +} diff --git a/acorn/acorn.h b/acorn/acorn.h @@ -0,0 +1,13 @@ +#pragma once + +#define STATE_VECTOR_LENGTH 624 +extern unsigned long STATE_VECTOR_M; + +typedef struct { + unsigned long state[STATE_VECTOR_LENGTH]; + int index; +} AcornState; + +AcornState acorn_seed(unsigned long seed); +unsigned long acorn_get_long(AcornState* acorn); +double acorn_get_double(AcornState* acorn); diff --git a/mtwister/README.md b/mtwister/README.md @@ -0,0 +1,45 @@ +Note: I stole this from [here](https://github.com/ESultanik/mtwister) + +# The MTwister C Library + +The **Mersenne twister** is a pseudo-random number generation +algorithm that was [developed in 1997 by Makoto Matsumoto (松本 眞) and +Takuji Nishimura (西村 拓 +士)](http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html). +Although [improvements on the original algorithm have since been +made](http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/index.html), +the original algorithm is still both faster and "more random" than the +built-in generators in many common programming languages (C and Java +included). + +There are already many implementations of the algorithm, so why did I +write one myself? There are a number of reasons: + +1. the [pseudocode on Wikipedia](http://en.wikipedia.org/wiki/Mersenne_twister#Pseudocode) suggested that it was relatively simple to implement; +2. I never trust pseudocode on Wikipedia, so I wanted an implementation from [the original academic paper](http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/ARTICLES/mt.pdf); and +3. it would have been just as easy to implement it myself than to figure out the API of someone else's ugly C code. + +Note that this code has not been tested to a sufficient extent to be +confidently used for cryptography. + +# Example + +The following code will create a new random generator seeded at <code>1337</code> and print out one thousand random doubles between 0 and 1. + +```C +#include <stdio.h> +#include "mtwister.h" + +int main() { + MTRand r = seedRand(1337); + int i; + for(i=0; i<1000; i++) { + printf("%f\n", genRand(&r)); + } + return 0; +} +``` + +# License + +Public domain. Have fun! diff --git a/mtwister/mtwister.c b/mtwister/mtwister.c @@ -0,0 +1,76 @@ +/* An implementation of the MT19937 Algorithm for the Mersenne Twister + * by Evan Sultanik. Based upon the pseudocode in: M. Matsumoto and + * T. Nishimura, "Mersenne Twister: A 623-dimensionally + * equidistributed uniform pseudorandom number generator," ACM + * Transactions on Modeling and Computer Simulation Vol. 8, No. 1, + * January pp.3-30 1998. + * + * http://www.sultanik.com/Mersenne_twister + */ + +#define UPPER_MASK 0x80000000 +#define LOWER_MASK 0x7fffffff +#define TEMPERING_MASK_B 0x9d2c5680 +#define TEMPERING_MASK_C 0xefc60000 + +#include "mtwister.h" + +inline void m_seedRand(MTRand* rand, unsigned long seed) { + /* set initial seeds to mt[STATE_VECTOR_LENGTH] using the generator + * from Line 25 of Table 1 in: Donald Knuth, "The Art of Computer + * Programming," Vol. 2 (2nd Ed.) pp.102. + */ + rand->mt[0] = seed & 0xffffffff; + for(rand->index=1; rand->index<STATE_VECTOR_LENGTH; rand->index++) { + rand->mt[rand->index] = (6069 * rand->mt[rand->index-1]) & 0xffffffff; + } +} + +/** +* Creates a new random number generator from a given seed. +*/ +MTRand seedRand(unsigned long seed) { + MTRand rand; + m_seedRand(&rand, seed); + return rand; +} + +/** + * Generates a pseudo-randomly generated long. + */ +unsigned long genRandLong(MTRand* rand) { + + unsigned long y; + static unsigned long mag[2] = {0x0, 0x9908b0df}; /* mag[x] = x * 0x9908b0df for x = 0,1 */ + if(rand->index >= STATE_VECTOR_LENGTH || rand->index < 0) { + /* generate STATE_VECTOR_LENGTH words at a time */ + int kk; + if(rand->index >= STATE_VECTOR_LENGTH+1 || rand->index < 0) { + m_seedRand(rand, 4357); + } + for(kk=0; kk<STATE_VECTOR_LENGTH-STATE_VECTOR_M; kk++) { + y = (rand->mt[kk] & UPPER_MASK) | (rand->mt[kk+1] & LOWER_MASK); + rand->mt[kk] = rand->mt[kk+STATE_VECTOR_M] ^ (y >> 1) ^ mag[y & 0x1]; + } + for(; kk<STATE_VECTOR_LENGTH-1; kk++) { + y = (rand->mt[kk] & UPPER_MASK) | (rand->mt[kk+1] & LOWER_MASK); + rand->mt[kk] = rand->mt[kk+(STATE_VECTOR_M-STATE_VECTOR_LENGTH)] ^ (y >> 1) ^ mag[y & 0x1]; + } + y = (rand->mt[STATE_VECTOR_LENGTH-1] & UPPER_MASK) | (rand->mt[0] & LOWER_MASK); + rand->mt[STATE_VECTOR_LENGTH-1] = rand->mt[STATE_VECTOR_M-1] ^ (y >> 1) ^ mag[y & 0x1]; + rand->index = 0; + } + y = rand->mt[rand->index++]; + y ^= (y >> 11); + y ^= (y << 7) & TEMPERING_MASK_B; + y ^= (y << 15) & TEMPERING_MASK_C; + y ^= (y >> 18); + return y; +} + +/** + * Generates a pseudo-randomly generated double in the range [0..1]. + */ +double genRand(MTRand* rand) { + return((double)genRandLong(rand) / (unsigned long)0xffffffff); +} diff --git a/mtwister/mtwister.h b/mtwister/mtwister.h @@ -0,0 +1,16 @@ +#ifndef __MTWISTER_H +#define __MTWISTER_H + +#define STATE_VECTOR_LENGTH 624 +#define STATE_VECTOR_M 397 /* changes to STATE_VECTOR_LENGTH also require changes to this */ + +typedef struct tagMTRand { + unsigned long mt[STATE_VECTOR_LENGTH]; + int index; +} MTRand; + +MTRand seedRand(unsigned long seed); +unsigned long genRandLong(MTRand* rand); +double genRand(MTRand* rand); + +#endif /* #ifndef __MTWISTER_H */