Tiny Mersenne-Twister pseudo random number generator

[hanschou]

Test implementation of TMT.

Source code copied from https://github.com/MersenneTwister-Lab/TinyMT

Tiny Mersenne Twister(TinyMT). Pseudo random number generators whose periods are 2¹²⁷-1. Mutsuo Saito (Hiroshima University) and Makoto Matsumoto (The University of Tokyo) Copyright (C) 2011 Mutsuo Saito, Makoto Matsumoto, Hiroshima University and The University of Tokyo. All rights reserved.

After making this implementation I realized that the program is huge and uses a lot of memory so one would only use it in security situation like encryption. If this is going to be used for real the code really need a clean up. Also it returns 32bit instead of one byte as this is the way to verify that the result of the first 5 random numbers are correct.

[RobTillaart]

Thanks for the PR, Looks interesting , some questions pop up

• copyright ?
• performance (current version, comparion)
• footprint (idem)
• optimizations
• documentation

[chlordk]

Most of your questions are addressed her https://github.com/MersenneTwister-Lab/TinyMT

As written in https://github.com/MersenneTwister-Lab/TinyMT/blob/master/LICENSE.txt this copyright notice must be applied:

Copyright (c) 2011, 2013 Mutsuo Saito, Makoto Matsumoto, Hiroshima University and The University of Tokyo. All rights reserved.

Performance: Much slower than Marsaglia so it might be a good idea to make a demo which show how many bytes per second each method can produce.

Otimization: The Tiny version is already optimized. It's not trivial to write security code so one should be careful with optimization.

RNG for games?: Keep it simple. Use Marsaglia if it is good enough.

[RobTillaart]

The performance comparison is a good idea, however if the footprint is big and performance low, it adds no new value. Only the longer period seems interesting.

Please have a look at

• https://www.sdu.se/blog/marsaglia-random-numbers/

It has some different RNG's one with a claimed period of 2^7578 ~ 10 ^2300 which is imho very interesting as it performs roughly as fast as current Marsaglia.

[chlordk]

I can't do all the math required to predict weakness, so I have to rely on what other experts say. In your code Marsaglia only uses 2x4 bytes

In this article it says that MT has a periode of 2¹⁹⁹³⁷-1 but in the original paper of MT it says only 2¹²⁷-1. I'm a bit confused here. https://www.sciencedirect.com/topics/computer-science/mersenne-twister

[RobTillaart]

The Marsaglia in the library indeed uses only 64 bit, so period can be max 2^64.

In that blog there are other algorithms by M. that use more bits and possibly have a longer period.

I agree to leave this kind of math to the experts.

[RobTillaart]

Gave it some time to sink in. Although interesting I decided not to merge this proposal into the library. Extra footprint an no performance gain, however it has a longer period. For now this is too little value.

---

That said the issue gave me another idea, make it possible to add a generator function runtime, something like

bool addGenerator(uint32_t (*rng)());
bool addSeed(void (*seed)(uint32_t value));
setMode(EXT_RNG); 

opinion?

[hanschou]

Actually I was about to not showing it to you because it was so big. But for secure encryption it is useful.

[RobTillaart]

Did you find time to write the comparison sketch? (Your remark ~2weeks above)

[hanschou]

Ohh, this is poor mans C++ compiler:

bool addGenerator(uint32_t (*rng)());
bool addSeed(void (*seed)(uint32_t value));
setMode(EXT_RNG);

In C++ it is made with a virtual class. In this way you have a menu of say 3 different RNGs. At compile time you choose one and only PROGMEM for that one is used. You can also include all of them and let the user choose RNG in the setup() section. I'll make an example of how it looks and post it.

[RobTillaart]

@hanschou As this PR will not be included I close this PR.

Imho this Tiny Mersenne-Twister pseudo random number generator deserves a library of its own. Preferably with a very easy to use interface e.g.

class TMTPRNG
{
public:
  TMTPRNG();  //  constructor
  seed(value);
  getRandom();
  etc...
}