1. Updated Resource Submission Rules: All model & skin resource submissions must now include an in-game screenshot. This is to help speed up the moderation process and to show how the model and/or texture looks like from the in-game camera.
    Dismiss Notice
  2. DID YOU KNOW - That you can unlock new rank icons by posting on the forums or winning contests? Click here to customize your rank or read our User Rank Policy to see a list of ranks that you can unlock. Have you won a contest and still havn't received your rank award? Then please contact the administration.
    Dismiss Notice
  3. The poll for Hive's 12th Concept Art Contest is up! Go cast your vote for your favourite genie!
    Dismiss Notice
  4. Travel to distant realms and encounter scenes unknown to the common folk. The Greatest of Adventures is upon us with the 8th Cinematic Contest. Join in on a fun ride.
    Dismiss Notice
  5. The 18th Icon Contest is ON! Choose any ingame unit and give him/her Hero abilities. Good luck to all.
    Dismiss Notice
  6. Contestants are to create a scene set in the Stone Age. Come and see what you can come up with. We wish you the best of luck!
    Dismiss Notice
  7. Colour outside the lines! Techtree Contest #13 is a go. The contest is optionally paired.
    Dismiss Notice
  8. Greetings cerebrates, our Swarm needs new spawners that will have numerous children. Join the HIVE's 31st Modeling Contest - Spawners and Spawned! The contest is optionally paired.
    Dismiss Notice
  9. Check out the Staff job openings thread.
    Dismiss Notice
Dismiss Notice
60,000 passwords have been reset on July 8, 2019. If you cannot login, read this.

Fast constant size overhead permutation generator

Discussion in 'The Lab' started by LeP, Sep 11, 2019.

  1. LeP

    LeP

    Joined:
    Feb 13, 2008
    Messages:
    445
    Resources:
    0
    Resources:
    0
    Fast constant size overhead permutation generator.
    You can use this whenever you need numbers between 0 and x in a random order.

    Demo


    Code (vJASS):

    function demo takes nothing returns nothing
        local integer i
     
        set i = 0
        loop
        exitwhen i == 5
            call BJDebugMsg(I2S(i) +": "+ I2S(Permutation_index(5, 1337, i)))
            set i = i +1
        endloop
     
        set i = 0
        loop
        exitwhen i == 5
            call BJDebugMsg(I2S(i) +": "+ I2S(Permutation_index(5, 42069, i)))
            set i = i +1
        endloop
     
    endfunction
     


    Will print something like this
    Code (Text):

    0: 4
    1: 3
    2: 2
    3: 0
    4: 1

    0: 4
    1: 0
    2: 3
    3: 2
    4: 1
     

    How does it work



    We use a bijective function r : integer -> integer where
    integer
    is our 32bit jass integer type. We want a good pseudo-random function for r. Such functions are rather easy to construct. Now to get from [0, 2^32] into our desired range [0, hi) we simply apply r until it returns a value in range [0, hi). Proving that this terminates is left as an excersize to the reader ;) (or just ask and i will provide a proof)
    To speed things up we truncate the value to [0, 2^n] for the smallest n such that hi <= 2^n.

    Looking at [2] one can see such a function r which could be adopted to jass easily. But for speeds sake we use a simpler pseudo-random function.

    Code



    Code (vJASS):

    library Permutation

    private function nextPowerOfTwo takes integer x returns integer
        local integer p = 1
        loop
        exitwhen x <= p
            set p = 2*p
        endloop
        return p
    endfunction

    // any bijective function from integer to integer
    private function R takes integer x, integer seed returns integer
        set x = x * 0xe170893d
        set x = x + 0x0929eb3f
        set x = x * 0x6935fa69
        set x = x - seed
        set x = x * 0xc860a3df
        return x
    endfunction

    /**
    Returns the i'th index of the permutated series [0, hi-1].

    @param hi The upper bound of this permutation
    @param seed Random seed for the permutation
    @param i Index of the permutation. Should be in range [0, hi-1]

    pure
    */

    public function index takes integer hi, integer seed, integer i returns integer
        local integer w = nextPowerOfTwo(hi)
        loop
            set i = R(i, seed)
       
            // this step isn't neccessary but it should speed up the search
            // Also jasshelper doesnt like %. Otherwise we could use i % w
            set i = BlzBitAnd(i, w-1)
        exitwhen i < hi
        endloop
        // again thanks to jasshelper we can't use %
        return ModuloInteger(i+seed, hi)
    endfunction

    endlibrary
     


    Sources


    [1]: https://web.cs.ucdavis.edu/~rogaway/papers/subset.pdf
    [2]: https://graphics.pixar.com/library/MultiJitteredSampling/paper.pdf
     
    Last edited: Sep 12, 2019
  2. Bribe

    Bribe

    Joined:
    Sep 26, 2009
    Messages:
    8,018
    Resources:
    25
    Maps:
    3
    Spells:
    10
    Tutorials:
    3
    JASS:
    9
    Resources:
    25
    I find it more user-friendly to just pop a random array index where needed via GetRandomInt(0, array_Size -1), and then re-build the array if you need to preserve it.
     
  3. LeP

    LeP

    Joined:
    Feb 13, 2008
    Messages:
    445
    Resources:
    0
    Resources:
    0
    You can provide the same api either way. And it all depends on the use case. Still this is constant size overhead while an array has linear size overhead (+ rebuilding take linear time).
     
  4. Bribe

    Bribe

    Joined:
    Sep 26, 2009
    Messages:
    8,018
    Resources:
    25
    Maps:
    3
    Spells:
    10
    Tutorials:
    3
    JASS:
    9
    Resources:
    25
    I'm taking a deeper dive into the code now and a couple things stood out to me:

    1)
    The user needing to pass a seed in order to utilize the system's behavior is necessary in order to maintain the integrity of each respective grouping, also the user needing to use a loop to extract the random sequence, might make the API overhead a bit high.

    I propose doing some optional wrapper functions in your resource that automates a bit of that redundant user-side stuff. Ie. something that returns a Table.

    2)
    Does % actually work in vanilla JASS as a mod character??
     
  5. LeP

    LeP

    Joined:
    Feb 13, 2008
    Messages:
    445
    Resources:
    0
    Resources:
    0
    Having a completely pure API is an upside. You can use any index in any order (or multiple times). I don't consider wrapping a mere integer seed into some stateful object an improvement.
    But writing some library which provides random seed generation/array syntax/iterator api is trivial.
    Another improvement would be allowing any range [lo, hi] instead of [0, hi-1].
    I don't intend to post this as a resource though. One of the reasons i posted this is its mathematical beauty.

    Also this can be trivially converted to pure jass: just remove
    library
    /
    public
    /
    private
    .

    Yes, since 1.29 or so. In fact using
    %
    is preferable over
    ModuloInteger
    since
    ModuloInteger
    is bugged for negative second argument.
     
  6. Prometheus3375

    Prometheus3375

    Joined:
    Jul 20, 2018
    Messages:
    90
    Resources:
    0
    Resources:
    0
    Can you explain, why?
     
  7. LeP

    LeP

    Joined:
    Feb 13, 2008
    Messages:
    445
    Resources:
    0
    Resources:
    0
    While
    ModuloInteger
    doesn't make any hard promises we have some expectations for it.
    The normal law for modulus is
    (x/y) * y + (x % y) == x
    , or x % y in [0 .. y-1].
    On the other hand
    ModuloInteger(-7, -3) == -4
    where -4 not in [-2 .. 0].
    In fact
    (-7/-3)*-3 + ModuloInteger(-7, -3) == -10 != -3
     
  8. Prometheus3375

    Prometheus3375

    Joined:
    Jul 20, 2018
    Messages:
    90
    Resources:
    0
    Resources:
    0
    Thanks, I realised the problem before reading you answer.
    Problem occurs when both args are negative. It checks whether modulus is negative, but did not check whether seconds arg is negative, so it adds -3 to -1, -4 is obtained.
    It can be easily fixed by taking absolute value of divisor.
    Code (vJASS):
    function ModuloInteger takes integer dividend, integer divisor returns integer
        local integer modulus = dividend - (dividend / divisor) * divisor

        // If the dividend was negative, the above modulus calculation will
        // be negative, but within (-divisor..0).  We can add (divisor) to
        // shift this result into the desired range of (0..divisor).
        if (modulus < 0) then
            set modulus = modulus + IAbsBJ(divisor)
        endif

        return modulus
    endfunction

    Or shorter.
    Code (vJASS):
    function ModuloN takes integer a, integer n returns integer
        return a - a / n * n
    endfunction

    function ModuloNPos takes integer a, integer n returns integer
        return ModuloN(IAbsBJ(a), n)
    endfunction

    First function must be used when you are sure that a is positive.

    The universal function.
    Code (vJASS):
    function ModuloN takes integer a, integer n returns integer
        set a = IAbsBJ(a)
        return a - a / n * n
    endfunction
     
    Last edited: Sep 14, 2019 at 1:35 PM
  9. LeP

    LeP

    Joined:
    Feb 13, 2008
    Messages:
    445
    Resources:
    0
    Resources:
    0
    Good thing is most people never use negative divisor so no-one ever experienced it probably. But yeah if you can't use
    %
    and need negative divisor you can use the above. In the case in my code in the OP
    ModuloInteger
    will always work (if you respect the API).