Talk:Seedable PRNG
Shouldn't prng_get update the seed? This works on the same principal as a script i wrote (Pseudo-Random Number Generator). Strife Onizuka 00:51, 19 March 2007 (PDT)
- I don't think so, though it is interesting how similar mine came out to be to yours. I swear I wasn't looking at yours when I wrote this. :P Yours doesn't seem to generate random numbers, at least not in any way I'm used to calling random!
integer pseudo_random(string text, integer nonce, integer start, integer end)
{//(c)(cc-by) Strife Onizuka, http://creativecommons.org/licenses/by/2.5/
return (integer)("0x"+llGetSubString(llMD5String(text, nonce), start, end));
}
string feed = "How much wood would a wood chuck chuck if a wood chuck could chuck wood?";
default
{
state_entry()
{
}
touch_start(integer next)
{
integer x;
next = pseudo_random(feed, 30 * ((integer)llGetGMTclock() / 30), 0, 7);
for (x=0;x<10;x++)
llSay(0, (string)next);
}
}
Output:
[12:19] Object: 120920825 [12:19] Object: 120920825 [12:19] Object: 120920825 [12:19] Object: 120920825 [12:19] Object: 120920825 [12:19] Object: 120920825 [12:19] Object: 120920825 [12:19] Object: 120920825 [12:19] Object: 120920825 [12:19] Object: 120920825
Mine has something yours doesn't have, it basically runs the MD5 in OFB mode by rehashing the previous hash over again. Gigs Taggart 12:32, 19 March 2007 (PDT)
*goes back and rereads* Oh wow i totally missed that the first seven times. Very interesting indeed. I am curious if there are any tendencies for bits to remain turned on or off. You could also make it more interesting by setting a default value on the string (jump starting the cumulative seed). One thing that bothers me is the possibility of it getting stuck in a loop. Where a loop would happen is not easily predicted. MD5 collisions make the prospect of a loop even more interesting, you could have 1,000,000 non looping results and then get stuck in a 10 result loop (as a result of a collision). The issue isn't if you will loop, it is when and what the period will be. If you incremented the MD5 nonce each iteration, the period of the loop could only be a multiple of 4,294,967,296 (which would probably go unnoticed).
integer prng_get()
{
return (integer)("0x" + llGetSubString(gLastHash = llMD5String(gLastHash, gSeed = -~gSeed ), 0, 7)) & 0x7FFFFFFF; //the bitwise thingy gets rid of negative numbers
}
//or...
//me like negative numbers :p
integer prng_get()
{
return (integer)("0x" + llGetSubString(gLastHash = llMD5String(gLastHash, gSeed = -~gSeed ), 0, 7));
}
And you are correct mine does not generate a random number per say, as a random number generator it is incomplete. This was intentional. The method of generating a Pseudo-Random Number for secure communications is important. My method requires the user to provide the inputs and handle their incrementation. With your method an object just rezzed won't have the same cumulative seed as an older object. Syncing the seeds would require A) spinning the newcomer until the communications sync (which would take a *very* long time), or B) communicating the cumulative seed which would create a new attack vector. Time dilation, sim reboot, or just general funkiness could cause scripts to fall out of sync. How do you determine which ones need to be resynced? As a default example, I have an example that use a time based algorithm with a common secret text that allows for two objects to communicate; it isn't a perfect solution but it is a solution none the less.
Both methods have their place.
My float modes need work, they loose a bit of precision. I'm not happy about it. Out of curiosity in that example you posted above what was it supposed to show? You have it reading a local integer to chat 10 times. Did you mean somethign like... Strife Onizuka 06:07, 20 March 2007 (PDT)
integer pos;
integer rand()
{
return pseudo_random(feed, (integer)llGetGMTclock(), pos, pos - 29);
}
integer pseudo_random(string text, integer nonce, integer start, integer end)
{//(c)(cc-by) Strife Onizuka, http://creativecommons.org/licenses/by/2.5/
return (integer)("0x"+llGetSubString(llMD5String(text, nonce), start, end));
}
string feed = "How much wood would a wood chuck chuck if a wood chuck could chuck wood?";
default
{
state_entry()
{
pos = 0;
}
touch_start(integer next)
{
integer x;
for (x=0;x<10;x++)
{
llSay(0, (string)rand());
llSleep(1.0);
}
}
}
- Yeah I did screw that up in my example of yours. Similar to your suggestion, one suggestion in #crypto was to just hash the seed + a counter with no feedback. I tested this and it seems valid too, but it is slightly slower for some reason (probably the extra cast).
Changing OFB to CTR mode:
integer prng_get()
{
gHashCounter++;
return (integer)("0x" + llGetSubString(llMD5String((string)gHashCounter, gSeed), 0, 7)) & 0x7FFFFFFF; //the bitwise thingy gets rid of negative numbers
}
This method should reduce the potential for short periods, since there is no feedback. Gigs Taggart 08:26, 20 March 2007 (PDT)
- using c++ is slower then ++c, if you want to shave a bit more off you can use (c = -~c). To shave even a bit more off you put it inline. The LSL compiler doesn't optimize code at all, it sucks. I don't really like that CTR mode one, it's got a 4,294,967,296 period. The OFB mode is really keen. Q: What does OFB and CTR stand for? Strife Onizuka 09:27, 20 March 2007 (PDT)