I frequently run my genetic programming software with different parameters, seeing what it will find. When asked to find a pseudo-random number generator under some given constraints, it is fairly good at finding a solution. The solution it finds is typically chaotic, though, with an unverifiable period. That\u2019s not very useful practically, as the chaotic nature means that some seeds may have very short times before they start repeating. Take, for example, the generator below, produced by a short simulation:<\/p>\n\n\n\n

RMU S2,51,954523823516132654;\nXSR S2,13;\nXOR OP,S2;<\/code><\/pre>\n\n\n\n
Translated into C# (where there is a class-level \u201cstate\u201d variable), this is<\/p>\n\n\n\n
public ulong NextRandom()\n{\n    state = BitOperations.RotateLeft(state, 51);\n    state = state * 954523823516132654;\n    state = state ^ (state >> 13);\n    return state;\n}<\/code><\/pre>\n\n\n\n
Recall that ^ is the XOR operator in C#. People keep asking me if that\u2019s a \u201craise to a power\u201d operator.<\/p>\n\n\n\n
This generator passes some randomness tests at a million numbers generated, and can probably be tuned to pass some fairly strong tests if some of the parameters are changed. Unfortunately, it mutates the state in a fairly chaotic way, and I\u2019m unaware of a way to determine what the shortest possible period is. There might be some seed value of state for which it repeats after 16 values, or a billion. Without guarantees about period, it\u2019s impractical to use.<\/p>\n\n\n\n
However, recently I ran the genetic simulation with a constraint of not using multiplication, and it found the solution below.<\/p>\n\n\n\n
ADD S2,S1;\r\nROR S2,1;\r\nSUB S1,12076313562642528635;\r\nXOR OP,S2;<\/code><\/pre>\n\n\n\n
Translated into C# (this time with two class-level state variables), this is<\/p>\n\n\n\n
public ulong NextRandom()\n{\n    state2 = state2 + state1;\n    state2 = BitOperations.RotateRight(state2, 1);\n    state1 = state1 - 12076313562642528635;\n    return state2;\n}<\/code><\/pre>\n\n\n\n
This generator is interesting because state1 changes from iteration to iteration by subtracting an odd number, and thus state1 will go through every possible ulong before repeating. I have no idea what the actual period of state2, and thus the whole generator is, but it is atleast the period of state1, which is 2^64. This is interesting because it is a rare case where I can prove a lower bound on the period by inspection, and the generator actually passes some decent tests of randomness. The generator is also remarkably simple, using only a single add, subtract, and rotate, so it should be competitive speedwise with some of the existing cutting edge PRNG\u2019s.<\/p>\n\n\n\n
I have tested this generator on a given seed to 100 billion numbers, using the GCD test, the gorilla test with word lengths 7 and 17, and the linear serial correllation test, and it passed all of the tests. I think the rotate constant it found was actually 4, not 1. I tested it at 1 in an attempt to see if that weakened it, but it apparently is quite strong at those parameters. I haven\u2019t yet tuned any of the parameters, but it is remarkably simple. State1 is what Marsaglia called a Weyl sequence. Not very random. State2 is an accumulator that gets rotated between accumulations. Apparently that\u2019s a fairly decent way to randomize things.<\/p>\n","protected":false},"excerpt":{"rendered":"
I frequently run my genetic programming software with different parameters, seeing what it will find. When asked to find a pseudo-random number generator under some given constraints, it is fairly good at finding a solution. The solution it finds is typically chaotic, though, with an unverifiable period. That\u2019s not very useful practically, as the chaotic […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"nf_dc_page":"","om_disable_all_campaigns":false,"WB4WB4WP_MODE":"","WB4WP_PAGE_SCRIPTS":"","WB4WP_PAGE_STYLES":"","WB4WP_PAGE_FONTS":"","WB4WP_PAGE_HEADER":"","WB4WP_PAGE_FOOTER":"","_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[1],"tags":[],"class_list":["post-111","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"yoast_head":"\n