If you've read any of L'Ecuyer you're probably aware of this already
(but I'll mention it just the same)

He published parameters and analysis results for several
combined Tausworthe.

I think I even posted links to some of his papers here somewhere

iirc he gives C code for them and there were other implimentations
that appeared on the web

My recollection is that they were all >32 bits and that he looked at 32 bits
and only found four worth extensive testing and of those only one that was
passable and that one wasn't very good.

If you like I can try and dig up a few links (but like I said it's
probably nothing new to anybody interested in the subject)

In the mean time, I'd be interested in (links to) anything you found
particularly interesting or informative.

This may be the paper you are referring to (pp. 31-32):

http://www.iro.umontreal.ca/~lecuyer/my ... estu01.pdf



This may be the post you are referring to:

viewtopic.php?p=3062#3062



C code for the combined Tausworthe generators LFSR113 and LFSR258 mentioned in the paper above is given on the 8th page in the .pdf file (the page itself is numbered 268):

http://www.ams.org/mcom/1999-68-225/S00 ... 1039-X.pdf



The generator is of my own invention (I'll wait for you to stop screaming in horror -- hey, Halloween's not too far away, anyway ) -- or at least it's an independent discovery -- so there's nothing online yet. It might be described as a simplified combined Tausworthe generator, as it's between an LFSR and a combined Tausworthe. There's some wishful thinking in the design, in that all shifts are by only one bit (or a full byte), which is helpful on processors like the 6502 and PIC whose shift instructions only shift by one bit. The testing I've done is only to weed out generators that are either obviously and severely flawed or outright broken, and as such the testing has not been terribly stringent.

Maybe I'm overly paranoid about the old "fiddling with an RNG tends to make it worse" adage, but I was surprised that I didn't introduce some horrible obvious flaw. I really like Marsaglia's philosophy of keeping the generator simple. Because it's such a simple variation on the theme, I was also suprised that no one (or maybe it's just no one that I could find) seems to have tried it. Plus, to me, it seems like it's got a bit of a too good to be true aspect to it. So yeah, I can't help but feel I'm missing something. That's one of the reasons why I want to subject it to the various test suites.

There are three versions of the generator:

• A "lite" generator, which yields a 16-bit result, with period 2^16 * (2^16 - 1), for applications where extreme speed (e.g. to leave time for other bells and whistles) is more important than statistical randomness, such as arcade-style games (e.g. selecting the next piece to drop in Tetris). In this case, as long as it there isn't an obvious pattern, few people, if anyone, will notice if its statisical properties aren't all that wonderful, with the other action going on.
• A minimally (hopefully) statisically acceptable generator, which yields a 32-bit result, with period 2^32 * (2^32 - 1)
• A general purpose generator which yields a 32-bit result, with a period that I am targeting to be 2^32 * (2^32 - 1) * (2^191 - 1). Currently there are two versions of this generator, one with period 2^32 * (2^32 - 1) * (2^191 - 1), and a faster (yes, faster) one with period 2^32 * (2^32 - 1) * (2^215 - 1). Using shuffling a deck of cards as a practical application to target, I've chosen a period in the neighborhood of 2^256, because 2^256 is a nice round (in binary) number > 52!. There are 52! ways of arranging a deck of cards, so the period of an RNG used to shuffle the deck should be at least 52! (2^ 225 < 52! < 2^226).

The generator is not as fast as an LFSR by itself (few things are), one example being the code from Lee's website:

http://members.lycos.co.uk/leeedavison/ ... /prng.html

But it's faster than just about anything else, including an LC generator (even the fast version with tables), the every Kth value of a N-bit LFSR used by EhBASIC (every 19th value of a 32-bit LFSR) and the Apple II "Integer" BASIC (every 17th value of a 15-bit LFSR), a Mersenne twister, either of combined Tausworthe generators mentioned above, or even the TAUS88 combined Tausworthe generator. C code for TAUS88 is on the 10th page in the .pdf file (the page itself is numbered 211):

http://www.ams.org/mcom/1996-65-213/S00 ... 0696-5.pdf

One thing I like about LC generators with a modulus that is a power of 2 is that the period is 2^N (or a multiple of it) for an N-bit result, and each of the 2^N possible values is equally common, so I've designed that property into my generator, even though it becomes less and less significant the longer the period is.

By contrast, a LFSR has period 2^N - 1, the combined Tausworthe generators TAUS88 and LFSR113 (which yield a 32-bit result) and LFSR258 (which yields a 64-bit result) have periods (2^31 - 1) * (2^29 - 1) * (2^28 - 1), and (2^31 - 1) * (2^29 - 1) * (2^28 - 1) * (2^25 - 1), and (2^63 - 1) * (2^55 - 1) * (2^52 - 1) * (2^47 - 1) * (2^41 - 1) respectively, all of which are odd, and therefore not a multiple of any power of 2, so some values must be more common than others.

Interestingly, assuming you can find a suitable LFSR (easier said than done) the speed doesn't depend on the length of the period. (Well, less than 256 is faster than 256 or more bytes, because in the former you can use absolute,X addressing rather than (zp),Y addressing, but that's an artifact of the 6502, not the algorithm.) In concept, you can target a period in the neighborhood of any power of two; it just depends on finding a suitable maximal length LFSR with the appropriate period.

For the "general purpose" generator, I don't yet have an LFSR that gives me the shorter period (the idea is to not waste space with more state than you need/want) at the faster speed. I've found a few programs on the web for testing LFSR polynomials for primitiveness, but none that meet all of my needs. Besides, some websites list incorrect criteria for an LFSR polynomial to be primitive. For that reason, I would prefer to write my own polynomial pritimiveness test routine. So that's a bit of a side project in itself. Once I've got a final LFSR polynomial, I'll run it through my weed-out test, and then it's finger crossing time, as it's off to the legitimate test suites.

I'm expecting the "lite" version to fail due to the short period (and possibly due to the low resolution as well), but I'm hoping the other two versions will at least pass the Diehard tests. The L'Ecuyer tests have a test to catch (and fail) linear generators. Its possible my generator will fail this test just as LFSR and combined Tausworthe generators do, but it's also possible my generator will mask that quality. I haven't looked through the tests in detail yet, but if there's a test that expects longer and longer runs of zeros the longer the period is, my generator may fail that one. Those are the possible weaknesses that I foresee, at least in theory. The results of a combined Tausworthe is probably a reasonable standard to hold my generator to. As as absolute best case scenario, I'd be ecstatic if my generator is even with shouting distance, statisically, of a Mersenne twister (assuming a comparable period). My impression of some of the more stringent test suites is that they are designed to find at least one weakness in everything, i.e. every generator is supposed to fail at least one test.

Incidentally (not that anybody's still reading, so I'll just keep going ), another open question is whether my generator will be suitable for cryptography. I'm no expert there, but it doesn't appear that the internal state can be deduced from the output, at least not in the way that an LFSR or combined Tausworthe can. I also don't know if it's possible to recover the output (of my generator) given the internal state but not the LFSR feedback bits. All interesting questions, but I'm not planning to explore this at all, since the generator is not intended for cryptography. It's hard to believe that something so simple would be secure, but the shrinking generator has apparently held up fairly well in that regard, despite its simplicity.

Finally, there is one other thing to do, the most important thing of all, really (:)): come up with a name for this generator.