体の基本演算

components/field_base.hpp · GitHub で見る

共通ページ

要素型 T の演算をそのまま使う field_detail::Field<T> です。行列などの内部で使います。

操作	内容	計算量
Field<T>::add(a,b) / mul(a,b) / neg(a) / inv(a)	加算・乗算・符号反転・逆元	型 T の演算による
Field<T>::zero(a,eps) / better(a,b)	0 判定／ピボットの比較	\(O(1)\)
Field<T>::dot(a,b,n)	長さ n の内積	\(O(n)\)
Field<T>::scale(a,n,x) / axpy(a,b,n,x)	定数倍／a += x*b	\(O(n)\)

要素の演算を \(O(1)\) とすると、配列の操作は時間 \(O(n)\)、追加空間は \(O(1)\) です。浮動小数点では eps 以下を 0 と判定し、絶対値の大きなピボットを優先します。

検証コード

• test/berlekamp_massey.test.cpp
• test/matrix_adjugate.test.cpp
• test/matrix_characteristic_polynomial.test.cpp
• test/matrix_det.test.cpp
• test/matrix_inverse.test.cpp
• test/matrix_pow.test.cpp
• test/matrix_product.test.cpp
• test/matrix_rank.test.cpp
• test/matrix_solve.test.cpp

コード

#ifndef FIELD_BASE_HPP
#define FIELD_BASE_HPP

#include <cmath>
#include <type_traits>

namespace field_detail {
template <class T>
struct Field {
	using V = T;
	static T add(T a, T b) { return a + b; }
	static T mul(T a, T b) { return a * b; }
	static T neg(T a) { return -a; }
	static T inv(T a) { return T(1) / a; }
	static bool zero(T a, long double eps) {
		if constexpr (std::is_floating_point_v<T>) return std::abs(a) <= eps;
		else { (void)eps; return a == T(0); }
	}
	static bool better(T a, T b) {
		if constexpr (std::is_floating_point_v<T>) return std::abs(a) > std::abs(b);
		else { (void)a; (void)b; return false; }
	}
	static T dot(const T *a, const T *b, int n) {
		T result = 0;
		for (int i = 0; i < n; ++i) result += a[i] * b[i];
		return result;
	}
	static void scale(T *a, int n, T x) { for (int i = 0; i < n; ++i) a[i] *= x; }
	static void axpy(T *a, const T *b, int n, T x) { for (int i = 0; i < n; ++i) a[i] += x * b[i]; }
};

}

#endif

Back to top page