Jump to content
Sign in to follow this  
irihapeti

pseudo random arrangement of a ordinal set

Recommended Posts

sometimes you might want a "random" arrangement (sequence) of unique numbers from some large ordinal set that cant fit in a list or string. "random" as in pseudorandom

this script can help with this. Is a script I done about 2 years ago now. I just tidy it up a bit for to post here

+

I do just for fun really these kinda things. I quite like solving puzzles. How many how few how fast how high how low. stuff like that. I just like to know bc nosey (:

anyways. If want more reading on how feistel network and galois lfsr work then:

http://en.wikipedia.org/wiki/Feistel_network
http://en.wikipedia.org/wiki/Linear_feedback_shift_register

+

the codes

 

// example pseudorandom arrangement of a ordinal set
// Public Domain May 2014 by elizabeth (irihapeti)(16)
// credits: Horst Feistel, Evariste Galois
// can mod and use as you like // // makes a "random" arrangement) of the set[0 < magnitude] // where magnitude in [1..0x7FFFFFFE]
// see test codes at bottom for usage
// // notes
// - the same magnitude and seed (raM + raS) will always // return the same arrangement as wrote // - cannot return all arrangements of a set. use a knuth // shuffle algo if you need that // initial defaults. are changed in the codes integer raM = 1; // magnitude of arrangement. not less than 1 integer raS = 1; // seed for arrangement. cannot be 0 integer raL = 1; // lo factor of magnitude integer raH = 1; // hi factor of magnitude integer raR = 8; // count of mixing rounds integer raI = 0; // current position in arrangement // galois lfsr pseudorandom number generator integer raN; // state generated by rnD integer raD(integer m) { raN = (raN >> 1) ^ (-(raN & 0x1) & 0xD0000001); return (raN & 0x7FFFFFFF) % m; } // brute factor magnitude raF() { raL = (integer)llSqrt(raM); integer n = 1 + (raM & 0x1); raL -= ((!(raL & 0x1)) && (n == 2)); for (; (raL > 2) && (raM % raL); raL -= n); raH = raM / raL; } // get next number in arrangement // will roll over when arrangement is exhausted // arithmetic feistel network integer raNext() { raN = raS; raI++; if (raI == raM) raI = 0; integer n = raI; integer i; for (i = 0; i < raR; i++) { integer m = n ^ raD(raM); if (m < raM) n = m; integer a = n % raL; integer b = n / raL; m = b % raL; a = (a + (m * m) + raD(raH)) % raL; m = a % raH; b = (b + (m * m) + raD(raL)) % raH; n = (a * raH) + b; } return n; } // call this to initialise raInit(integer m) { // set the magnitude. should not be > 0x7FFFFFFE else overflow // should always be at least 1 element in arrangement if ((m < 1) || (m > 0x7FFFFFFE)) m = 1; // factor when m changes raM if (m != raM) { raM = m; raF(); } // seed with some value. set raS to a constant value to produce // same arrangement for same magnitude // raS = yourseed; raS = (integer)llFrand(0x10000) << 16 | (integer)llFrand(0x10000); // uses galois lfsr so raS should never be 0 if (raS == 0) raS = 1; // seed the rnd raN = raS; // pick either 7 or 8 rounds. comment out if happy with 8 raR = 8 - raD(2); // pick a place to start in the arrangement raI = raD(raM); } // --- some test code --- default { touch_start(integer total_number) { llOwnerSay("begin... arrange 0..9"); integer mag = 10; raInit(mag); integer i; for (i = 0; i < mag; i++) llOwnerSay((string)i + " : " + (string)raNext()); llOwnerSay("...end"); llOwnerSay("begin... arrange 0..0x7FFFFFFD"); mag = 0x7FFFFFFE; raInit(mag); for (i = 0; i < 10; i++) llOwnerSay((string)i + " : " + (string)raNext()); llOwnerSay("...end"); } }

 

  • Like 1

Share this post


Link to post
Share on other sites

Very well done and illustrative how LSL (with all its warts LOL) can be used to implement even advanced math algorithms.

 

With its reproducible pseudorandom results within a set, I can see how this would be useful for a number of game situations and your excellent commenting should enable any intermediate coder the means to modify it to their use.

Share this post


Link to post
Share on other sites

Those cheap LED candles that flicker like the real thing use LFSR hardware to generate pseudo-random intensities...

http://hackaday.com/2014/03/02/reverse-engineering-candle-flicker-leds-again/

I learned to program FPGAs (Field Programmable Gate Arrays) early in my engineering career. They are wonderful platforms upon which to design remarkably fast and compact logic systems and are now sophisticated enough that you can implement full blown computers in them, or even compile a C program into a logic design that directly implements the algorithm.

Every design I did required numerous counters to sequence things. The fastest counters were Galois LFSR based. Conventional binary counters require logic that examines all bits in the counter to determine when the terminal count is reached. When only narrow gates (2-4 inputs) are available, watching wide counters results in cascading many levels of logic. This limits clock frequency, as all logic must settle before the next clock.

LFSR counters can be constructed to reach arbitrary terminal counts while generally examining less than all bits in the counter. This simplifies the count logic, but still requires observing multiple bits simultaneously, again potentially requiring chains of gates. Galois counters break the count termination logic into minimal XOR gates, which are then distributed along the register chain. This results in the maximum possible count frequency.

The LFSR Wiki page you linked shows a Fibonacci LFSR with cascaded XOR logic three gates deep, feeding the register chain's single input. If each XOR takes 1ns to process the function, and the register must have a stable input at the instant you clock it, and produces its output 1ns later, you can't go faster than 250MHz (4ns). In the Galois counter on that same page, you'll see that the three XOR gates are distributed across multiple input points in the register chain. With only one XOR between any register output and a register input, you can now clock the counter at 500MHz (2ns).

Those were fun times.

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Sign in to follow this  

×
×
  • Create New...