[asm] Can this triangular rand function be more concise?

[Raijinili]

Input: n, an integer
Output: Random integer between 1 and n, inclusive. The results will tend toward the center of the distribution, symmetrically.

Python version:

Code (python) Select Expand

from random import random as rand
def triangular_rand(n):
    return int((rand() + rand()) * n / 2) + 1

def triangular_rand(r4):
    stack -= 8
    var n
    var x
    r2 = rand()
    ^n = r4
    r2 = rand()
    ^x = result
    x = x + result
    LO, HI = x * n
    ^pop n
    r2 = x >> 0x10
    stack -= 8
    pop x
    return r2
    ^r2 = r2 + 1


spoiler: v1

Code (python) Select Expand

from random import random as rand
def triangle_rand(n):
    lo = n // 2
    hi = (n + 1) // 2
    return int(rand()*lo + rand()*hi + 1)


Testing that the distribution is correct:

Code (python) Select Expand


from collections import Counter
def test(n, times=100000):
    print(sorted(Counter(triangle_rand(n) for i in range(times)).items()))

test(5)
test(6)


I got it down to 20 15 lines.
ASM pseudocode ("^" indicates delay slot or multiplication buffer slot.):

Code Select Expand

def triangular_rand(r4):
    stack -= 8
    var n
    var x
    r2 = rand()
    ^n = r4
    r2 = rand()
    ^x = result
    x = x + result
    LO, HI = x * n
    ^pop n
    r2 = x >> 0x10
    stack -= 8
    pop x
    return r2
    ^r2 = r2 + 1


spoiler: v1

Code Select Expand


def triangle_rand(r4):
    stack -= 8
    push lo
    push hi
    lo = r4 >> 1
    r2 = rand()
    ^hi = r4 + 1
    MLO = r2 * lo
    ^hi = hi >> 1
    r2 = rand()
    ^lo = MLO
    MLO = r2 * hi
    nop
    hi = MLO
    r2 = lo + hi
    pop hi
    pop lo
    r2 = r2 >> 0x0f
    r2 = r2 + 1
    return r2
    ^stack += 8


It might be a good idea to r4 = r4 & 0xFF, to prevent any risk of overflow.

[Glain]

I tried writing this as an ASM routine and I had it at 18 lines. I ended up with something very similar to what you have here, but there are a few things missing from the pseudocode:

You need to push the return address ($ra) before calling rand(), and pop it sometime after the last subroutine call, otherwise your routine will crash.  That adds 2 more lines, and also changes the stack offset to be 16 instead of 8. (Also, it should be -16 at the top, +16 at the bottom, not -16 in both spots.)

I also couldn't find a statement in your code moving the multiplication result out of LO (the ASM command for this would be mflo).  I may actually be misunderstanding this entire part:

Code Select Expand


LO, HI = x * n
(...)
r2 = x >> 0x10


The first line calculates x * n, but that result is never used and instead r2 is set to the high 16 bits of x?  Also, is the division by 2 accounted for somewhere?

[Raijinili]

Whoops. Corrected (18 lines):

Code Select Expand


def triangular_rand(r4):
    stack -= 16
    var n
    var x
    push $ra
    r2 = rand()
    ^n = r4
    r2 = rand()
    ^x = result
    x = x + result
    LO, HI = x * n
    ^pop n
    (r2 = LO)
    r2 = r2 >> 0x10
    stack += 16
    pop x
    pop $ra
    return r2
    ^r2 = r2 + 1


16, not 12?

r2 is set to the high 16 bits of x?  Also, is the division by 2 accounted for somewhere?

It needs to be divided by 0x8000, then divided by 2. That's combined into a single step of dividing by 0x10000, which is a shift of 0x10. The rand result is usually multiplied and shifted by 0x0F.

This assumes that rand() returns 0 to 0x7FFF, instead of -0x8000 to 0x7FFF.

[Glain]

Okay, I see what's going on with the bit shift.  I just didn't see that in the original formula, but it would make sense to do that so the result is in the range you want.

Technically the stack pointer offsets are supposed to be multiples of 8 (thus 16 instead of 12), although I can't exactly remember why.  Something to do with exception handling, if memory serves.

Overall, it looks good, except you shouldn't add to the stack pointer until after you're done popping, i.e. it should be like this:

Code Select Expand


    pop x
    pop $ra
    stack += 16