Final Fantasy Hacktics

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:
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



Testing that the distribution is correct:

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.):
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



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

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:


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?

Whoops. Corrected (18 lines):

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?

Quoter2 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 (http://ffhacktics.com/wiki/Random_Process,_gives_a_number_between_0-7fff), instead of -0x8000 to 0x7FFF.

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:


    pop x
    pop $ra
    stack += 16