Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Faster check algorithm #21

Open
bWFuanVzYWth opened this issue Nov 2, 2021 · 1 comment
Open

Faster check algorithm #21

bWFuanVzYWth opened this issue Nov 2, 2021 · 1 comment

Comments

@bWFuanVzYWth
Copy link

let seed      = umul32_lo(x_uint, 0x1f1f1f1f) ^ z_uint;
let mt        = new MersenneTwister(seed);
let n         = mt.random_int();
this._isSlimy = (n % 10 == 0);

MersenneTwister() is actually calculation an array with a length of 624, but only the first 397 numbers are used. If you write this function manually and simplify unnecessary parts, it can be much faster.

I'm sorry that I can't use typescript language, but I can provide code in C language.
Here is my programming in C language, The correctness of the algorithm has been tested:
https://github.com/origin0110/SlimeChunkFinder

uint32_t get_seed(int32_t x, int32_t z)
{
    return x * 0x1f1f1f1f ^ z;
}

fast_t is_slime_chunk_mt(uint32_t s)
{
    uint32_t m = 0x6c078965 * (s ^ s >> 30) + 1;
    s = s & 0x80000000 | m & 0x7fffffff;
    for (int i = 2; i < 398; i++)
        m = 0x6c078965 * (m ^ m >> 30) + i;
    m ^= (s >> 1) ^ ((-((int32_t)(s & 1))) & 0x9908b0df);
    m ^= m >> 11;
    m ^= m << 07 & 0x9d2c5680;
    m ^= m << 15 & 0xefc60000;
    m ^= m >> 18;
    return (fast_t)(!(m % 10));
}
@McbeEringi
Copy link

McbeEringi commented Apr 25, 2022

I also simplified my Mersenne Twister after seeing this issue.
As a result, I ended up in almost the same place as Origin0110.
It just transforms the expression so it gives exactly the same result as the original.
Here is a pure JavaScript implementation.

const slime=m=>{//der MersenneTwister m=[chunkX,chunkZ]
	m=Math.imul(m[0],0x1f1f1f1f)^m[1];
	const f=(x,y)=>Math.imul(x^x>>>30,0x6c078965)+y,a=m&0x80000000|(m=f(m,1))&0x7fffffff;
	for(let i=2;i<398;i++)m=f(m,i);
	m^=a>>> 1 ^[0,0x9908b0df][a&1];
	m^=m>>>11;
	m^=m<<  7 &0x9d2c5680;
	m^=m<< 15 &0xefc60000;
	m^=m>>>18;
	return!((m>>>0)%10);
};

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants