Modular Multiplication

Written by me (Anixias).

function mulmod(a, b, modulo)
{
	var res = 0;
	a %= modulo;
	while(b > 0)
	{
		if (b % 2 == 1)
		{
			res = (res + a) % modulo;
		}
		
		a = (a * 2) % modulo;
		
		b = b >> 1;
	}
	
	return res % modulo;
}

Usage

This function will multiply two numbers, a and b, and ensure the product doesn’t overflow past modulo. It avoids actually multiplying a by b so GMS2 doesn’t lose precision. After several tests with large 32-bit integers, it is perfectly accurate, whereas using normal operations (literally using (a * b) % 0x100000000) produced slightly inaccurate results. Here is a simple function to multiply two unsigned 32-bit integers, ensuring the product is an unsigned 32-bit integer (via overflow):

function multiply_u32(a, b)
{
	return mulmod(a, b, 0x100000000);
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s