Jump to content

pseudo random arrangement of a ordinal set


irihapeti
 Share

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
Link to comment
Share on other sites

  • 3 weeks later...

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.

Link to comment
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.

Link to comment
Share on other sites

  • 9 years later...

example of a reversible arithmetic feistel network. Reversible meaning encoder/decoder

// reversible arithmetic feistel network
// public domain: elleevelyn February 2024
// credits: irihapeti/16/elizabeth
//
// typical use case: obfuscation of a sequence of ordinal numbers
//  - generate a sequence of "random-looking" unique numbers that can be mapped back 
//    to the sequence set
//  - for further obfuscation (given that the encoder/decoder algorithm is public)
//    then the simplist is to changeout the pseudorandom number generator for another
//    keeping the changeout a secret known only to yourself
//  - more obfuscation can be obtained by adding more layers to the mixing as
//    irihapeti did. Note that i keep the mixing to the barest so will be easier to
//    add layers of your own design 

// galois lfsr pseudorandom number generator
integer raN;  // state generated by raD
integer raD(integer magnitude)
{
    raN = (raN >> 1) ^ (-(raN & 0x1) & 0xD0000001);
    return (raN & 0x7FFFFFFF) % magnitude;
}

// brute factor magnitude
integer raF(integer magnitude)
{   // return low factor of magnitude
    integer result = (integer)llSqrt(magnitude);
    integer n = 1 + (magnitude & 0x1); 
    result -= ((!(result & 0x1)) && (n == 2)); 
    for (; (result > 2) && (magnitude % result); result -= n);
    return result;
}

// arithmetic feistel network encoder
integer encode(integer value, integer magnitude, integer lowfactor, integer seed)
{   // encode value using magnitude, lowfactor, seed
    raN = seed;
    integer highfactor = magnitude / lowfactor;    
    integer i;
    // forward mixing : fixed to 8 rounds
    integer low = value % lowfactor;        
    integer high = value / lowfactor;  
    for (i = 0; i < 8; ++i)
    {
        integer m = high % lowfactor;
        low = (low + (m * m) + raD(highfactor)) % lowfactor;
        m = low % highfactor;
        high = (high + (m * m) + raD(lowfactor)) % highfactor;
    }
    return high * lowfactor + low;
}

// arithmetic feistel network decoder
integer decode(integer value, integer magnitude, integer lowfactor, integer seed)
{   // decode value using magnitude, lowfactor, seed  
    raN = seed;
    integer highfactor = magnitude / lowfactor;
    integer i;
    // get the PRNG outputs used by encoder
    list prng;      
    for (i = 0; i < 8; ++i, prng += [raD(highfactor), raD(lowfactor)]);
    // reverse mixing : fixed to 8 rounds
    integer low = value % lowfactor;        
    integer high = value / lowfactor; 
    for (i = 14; i >= 0; i -= 2)
    {
        integer m = low % highfactor;
        high = (high - (m * m) - llList2Integer(prng, i+1)) % highfactor;
        if (high < 0) high += highfactor;       
        m = high % lowfactor;
        low = (low - (m * m) - llList2Integer(prng, i)) % lowfactor;
        if (low < 0) low += lowfactor;
    }
    return high * lowfactor + low;
}

default
{
    state_entry()
    {
        // encode/decode set [0..9] within magnitude range [0..9]
        integer seed = (integer)llFrand(0x10000) << 16 | (integer)llFrand(0x10000);
        integer magnitude = 10;
        integer lowfactor = raF(magnitude);
        integer i;
        for (i = 0; i < magnitude; ++i)
        {
           integer encoded = encode(i, magnitude, lowfactor, seed);
           integer decoded = decode(encoded, magnitude, lowfactor, seed);
           llOwnerSay(llDumpList2String(["i: ", i, " enc: ", encoded, " dec: ", decoded], ""));
        } 
      
        // encode/decode set [2000..2009] within magnitude range [0..99999999]
        seed = (integer)llFrand(0x10000) << 16 | (integer)llFrand(0x10000);
        magnitude = 100000000;
        lowfactor = raF(magnitude);
        for (i = 2000; i < 2010; ++i)
        {
           integer encoded = encode(i, magnitude, lowfactor, seed);
           integer decoded = decode(encoded, magnitude, lowfactor, seed);
           llOwnerSay(llDumpList2String(["i: ", i, " enc: ", encoded, " dec: ", decoded], ""));
        } 
    }
}

 

Edited by elleevelyn
Link to comment
Share on other sites

Please sign in to comment

You will be able to leave a comment after signing in



Sign In Now
 Share

×
×
  • Create New...