library/modint/barrett.hpp

• View this file on GitHub
• Last update: 2023-04-16 03:09:05+08:00
• Include: #include "library/modint/barrett.hpp"
• Link: https://en.wikipedia.org/wiki/Barrett_reduction

Required by

• Discrete Log (離散對數 $a^x \equiv b \pmod m$) (library/math/discrete-log.hpp)

Verified with

• test/math/discrete-log/yosupo-Discrete-Logarithm.test.cpp

Code

#pragma once

namespace felix {

namespace internal {

// Fast modular multiplication by barrett reduction

// Reference: https://en.wikipedia.org/wiki/Barrett_reduction

struct barrett {
	unsigned int m;
	unsigned long long im;

	explicit barrett(unsigned int _m) : m(_m), im((unsigned long long)(-1) / _m + 1) {}

	unsigned int umod() const { return m; }

	unsigned int mul(unsigned int a, unsigned int b) const {
		unsigned long long z = a;
		z *= b;
#ifdef _MSC_VER
		unsigned long long x;
		_umul128(z, im, &x);
#else
		unsigned long long x = (unsigned long long)(((unsigned __int128)(z) * im) >> 64);
#endif
		unsigned long long y = x * m;
		return (unsigned int)(z - y + (z < y ? m : 0));
	}
};

} // namespace internal


} // namespace felix

#line 2 "library/modint/barrett.hpp"

namespace felix {

namespace internal {

// Fast modular multiplication by barrett reduction

// Reference: https://en.wikipedia.org/wiki/Barrett_reduction

struct barrett {
	unsigned int m;
	unsigned long long im;

	explicit barrett(unsigned int _m) : m(_m), im((unsigned long long)(-1) / _m + 1) {}

	unsigned int umod() const { return m; }

	unsigned int mul(unsigned int a, unsigned int b) const {
		unsigned long long z = a;
		z *= b;
#ifdef _MSC_VER
		unsigned long long x;
		_umul128(z, im, &x);
#else
		unsigned long long x = (unsigned long long)(((unsigned __int128)(z) * im) >> 64);
#endif
		unsigned long long y = x * m;
		return (unsigned int)(z - y + (z < y ? m : 0));
	}
};

} // namespace internal


} // namespace felix

Back to top page