Random Numbers

[mittelmark]

Hi,

is there any chance to get direct support for random numbers (Math.Rand)? Or should we create our own class and then use 'native' and then srand/rand etc for the different languages? Probably the problem is the time implementation to make the numbers really random.

Best,
Detlef

[pfusik]

There are quite a few methods to implement.

For now, your options are:

1. Dispatch to existing random number generators in native blocks as you described.

2. Get random numbers from outside Fusion code, e.g. by subclassing a Fusion class.

3. Use a pure-Fusion implementation. For example, in my recent project I have:

	long RandomState;

	static long LowBits(int n)
	{
		long one = 1;
		return (one << n) - 1;
	}

	float NextRandom!()
	{
		// https://en.wikipedia.org/wiki/Xorshift#xorshift.2A
		long state = RandomState;
		state ^= state >> 12 & LowBits(52);
		state ^= (state & LowBits(39)) << 25;
		state ^= state >> 27 & LowBits(37);
		RandomState = state;
		float f = (state * 0x2545f4914f6cdd1d >> 40) & LowBits(24);
		return f / 16777216;
	}

This returns floats between 0 (inclusive) and 1 (exclusive), but should be easy to adapt to other ranges and types.
You still need native or outside code to initialize the state, but you'll get same sequence of numbers and same performance on all targets.

[pfusik]

Yeah, this code uses modulo 2^64 multiplication and Swift detects integer overflows.
I agree with your way of addressing this.
When we introduce uint and ulong types (#61), perhaps we should define them as doing modulo arithmetic?

Fut now complains: Test5.fu(25): ERROR: Method can complete without a return value

Probably fut means "can not complete"? The question is how can I get the native replacement for the method NextRandom placed correctly in this native block?

It says what is sees in your code rather than what it expects. It doesn't see a return as it's a native return.
Just minimize the native part:

	/// Create a random number using the xorshift algorithm.
	public float NextRandom!()
	{
		// https://en.wikipedia.org/wiki/Xorshift#xorshift.2A
		long state = RandomState;
		state ^= state >> 12 & LowBits(52);
		state ^= (state & LowBits(39)) << 25;
		state ^= state >> 27 & LowBits(37);
		RandomState = state;
	#if SWIFT
	native {
		let a = UInt64(bitPattern: state)
		let m: UInt64 = 2685821657736338717

		// full 128-bit product split into high/low 64-bit parts
		let product = a.multipliedFullWidth(by: m) // (high: UInt64, low: UInt64)

		// Equivalent to: (state * m) >> 40
		state = Int64(bitPattern: (product.high << (64 - 40)) | (product.low >> 40))
	}
	#else
		state = state * 0x2545f4914f6cdd1d >> 40;
	#endif
		float f = state & LowBits(24);
		return f / 16777216.0;
    }

I did not test that much. state ^= (state & LowBits(39)) << 25; might also need special handling in Swift.

[mittelmark]

Yeah, that worked:

Here is the actual final code: https://github.com/mittelmark/snha4any/blob/main/fusion/test/Test5.fu

Thanks a lot!! I can now check all other files for Swift as well - random numbers were the entry point for Ywift.

[pfusik]

Discard product.high, for two reasons:

• C++ etc. give 64-bit product
• you'll eventually only need the low 24 bits

Also, consider https://developer.apple.com/documentation/swift/uint64/multipliedreportingoverflow(by:)

[pfusik]

I think you can do >> 40 in Fusion.

[pfusik]

Here's how I handled this in my project: pfusik/llama3.fu@ffb026a
Feel free to copy.

[ariankordi]

I'll contribute two snippets I've written that may be useful:

1. LCG-based random number generator reverse engineered from another program. It's made to match the 32-bit result of the original when transpiled to C++, Python, JS, C#.

class FFLiRandomContext
{
    // CFLiSystemContext.random/FFLiRandomContext: rnd, mul, add (last two are constants)
    public long Rnd; // Originally a uint, which doesn't work in inlined C/C++.

    // The constants are the same as in CFLi_InitializeSystemWork.
    // These are apparently RNG constants used by Japanese games.
    const uint LcgMultiplier = 0x5d588b65;
    const uint Addend = 0x269ec3;

    // Random__17FFLiSystemContextFUs
    public ushort Random!(ushort end)
    {
        assert end > 0;

        // Mix randomness.
        // NOTE: This RELIES on 32-bit overflow arithmetic, and
        // is NOT GUARANTEED to work in every language (e.g. Python).
        Rnd = ((LcgMultiplier * Rnd) + Addend) & 0xFFFFFFFF;

        // Get and "clamp" the random value.
        uint value = (Rnd & 0xFFFFFFFF) >> 16;
        if (end > 0)
            value = (value * end) >> 16;

        Console.Error.WriteLine($"random result (rnd = {Rnd:x8}): {value}");
        assert value > 0 || value == 0; // fusion eliminates >= 0
        assert value <= end;

        return value;
    }
}

3. Hash-like Fnv1a 128-bit implementation ported from simple C code. I use this to help make a UUID.

/// Ported from the following (LGPLv3 license): https://github.com/sdroege/snippets/blob/b760be3ef9c57e7a8a03fd73bb90666169cc3f39/snippets/fnv.c#L119-L183
/// See above for more simple snippets to port from.
public static class Fnv1a
{
    public static void Calculate128(byte[]! hash, byte[] data, uint size)
    {
        /* 128 bit prime  =             309485009821345068724781371 = 0x0000000001000000000000000000013b
         * 128 bit offset = 144066263297769815596495629667062367629 = 0x6c62272e07bb014262b821756295c58d
         */

        long[4] tmp;
        long[4] tmp2;

        /* 128 bit number, 32 bit per field, highest 32 bit first */
        tmp[0] = 0x6c62272e;
        tmp[1] = 0x07bb0142;
        tmp[2] = 0x62b82175;
        tmp[3] = 0x6295c58d;

        uint offset = 0;
        for (uint i = 0; i < size; i++)
        {
            /* Multiplication */

            /* lowest 32 bits */

            /* multiply and keep carries forward */
            // tmp2[3] = tmp[3] * 0x0000013b; // FNV1
            tmp2[3] = (data[offset] ^ tmp[3]) * 0x0000013b; // FNV1a

            tmp2[2] = tmp[2] * 0x0000013b + (tmp2[3] >> 32);
            tmp2[1] = tmp[1] * 0x0000013b + (tmp2[2] >> 32);
            tmp2[0] = tmp[0] * 0x0000013b + (tmp2[1] >> 32);
            /* drop carries */
            tmp2[3] &= 0xffffffff;
            tmp2[2] &= 0xffffffff;
            tmp2[1] &= 0xffffffff;
            tmp2[0] &= 0xffffffff;

            /* highest 32 bits */

            /* multiply and keep carries forward */
            tmp2[1] += tmp[3] * 0x01000000;
            tmp2[0] += tmp[2] * 0x01000000 + (tmp2[1] >> 32);
            /* drop carries */
            tmp2[1] &= 0xffffffff;
            tmp2[0] &= 0xffffffff;

            // tmp[3] = tmp2[3] ^ data[offset]; // FNV1
            tmp[3] = tmp2[3];// FNV1a

            tmp[2] = tmp2[2];
            tmp[1] = tmp2[1];
            tmp[0] = tmp2[0];

            offset += 1;
        }

        hash[0] = (tmp[0] >> 24) & 0xff;
        hash[1] = (tmp[0] >> 16) & 0xff;
        hash[2] = (tmp[0] >> 8) & 0xff;
        hash[3] = (tmp[0] >> 0) & 0xff;
        hash[4] = (tmp[1] >> 24) & 0xff;
        hash[5] = (tmp[1] >> 16) & 0xff;
        hash[6] = (tmp[1] >> 8) & 0xff;
        hash[7] = (tmp[1] >> 0) & 0xff;
        hash[8] = (tmp[2] >> 24) & 0xff;
        hash[9] = (tmp[2] >> 16) & 0xff;
        hash[10] = (tmp[2] >> 8) & 0xff;
        hash[11] = (tmp[2] >> 0) & 0xff;
        hash[12] = (tmp[3] >> 24) & 0xff;
        hash[13] = (tmp[3] >> 16) & 0xff;
        hash[14] = (tmp[3] >> 8) & 0xff;
        hash[15] = (tmp[3] >> 0) & 0xff;
    }

#if !NO_ALLOC
    public static byte[]# Create128(byte[] data, uint size)
    {
        byte[]# hash = new byte[16]; // 128-bit buffer.
        Calculate128(hash, data, size);
        return hash;
    }
#endif
}