有理数を分数精度のまま計算するクラス（C#）
別に計算用途があったわけでもないけど、有理数を分数のまま計算するためのクラスを作成してみた。1/3が0.333...にならずに1/3のまま計算できるもの。
ソースコード
ちょっと長いけど全文載せる。
class RationalNumber : IEquatable<RationalNumber>, IEquatable<long>, IComparable<RationalNumber>
{
private bool sign = true;
private long a = 0;
private long b = 1;
private static Regex Pattern
= new Regex("\s*(-?[0-9]+)\s*(/\s*([0-9]+)\s*)?");
//--------------------
/// <summary>
/// 分子の絶対値を取得します。
/// </summary>
public long Numerator {
get { return a; }
}
/// <summary>
/// 分母の絶対値を取得します。
/// </summary>
public long Denominator {
get { return b; }
}
/// <summary>
/// 小数値を取得します。
/// </summary>
public double DoubleValue {
get {
var v = (double)a / (double)b;
return SignValue * v;
}
}
/// <summary>
/// 値が0であるかを取得します。
/// </summary>
public bool IsZero {
get { return a == 0; }
}
/// <summary>
/// 正の数の場合1、負の数の場合-1を取得します。
/// </summary>
public int SignValue {
get { return this.sign ? 1 : -1; }
}
//--------------------
/// <summary>
/// 0を生成します。
/// </summary>
public RationalNumber() {
}
/// <summary>
/// 分子と分母を指定して数を生成します。
/// </summary>
/// <param name="a">分子</param>
/// <param name="b">分母</param>
public RationalNumber(long a, long b = 1) {
if (b == 0) {
throw new DivideByZeroException("分母が0に指定されました。");
}
if (a == 0) {
sign = true;
this.a = 0;
this.b = 1;
} else {
sign = IsSign(a, b);
this.a = Math.Abs(a);
this.b = Math.Abs(b);
Reduction();
}
}
//--------------------
/// <summary>
/// 分数形式で表記されたの文字列から数を生成します。
/// </summary>
/// <param name="s">分数または整数式の文字列</param>
public static RationalNumber Parse(string s) {
var mc = Pattern.Match(s);
if (!mc.Success) {
throw new FormatException("文字列が分数の形式ではありません。");
}
var a = long.Parse(mc.Groups[1].Value);
var b = mc.Groups[3].Success ? long.Parse(mc.Groups[3].Value) : 1;
return new RationalNumber(a, b);
}
/// <summary>
/// 符号を検証します。
/// </summary>
private bool IsSign(long a, long b) {
if (a >= 0 && b >= 0) return true;
if (a < 0 && b < 0) return true;
return false;
}
/// <summary>
/// 約分します。
/// </summary>
private void Reduction() {
var c = Gcd(a, b);
a /= c;
b /= c;
}
/// <summary>
/// 逆数を取得します。
/// </summary>
/// <returns>この有理数の逆数を表すオブジェクト</returns>
public RationalNumber Inverse() {
return new RationalNumber(b * SignValue, a);
}
/// <summary>
/// 約分された分数の文字列表現を取得します。
/// </summary>
public override string ToString() {
return $"{(sign ? "" : "-")}{a}{(b > 1 ? $"/{b}" : "")}";
}
/// <summary>
/// 数値の一致を評価します。
/// </summary>
public bool Equals(RationalNumber other) {
return sign == other.sign
&& a == other.a && b == other.b;
}
/// <summary>
/// オブジェクトがこのクラスのインスタンスかつ数値が一致するかを評価します。
/// </summary>
public override bool Equals(object obj) {
var x = obj as RationalNumber;
return x != null && Equals(x);
}
/// <summary>
/// 数値の一致を評価します。
/// </summary>
public bool Equals(long v) {
if (b != 1) return false;
var aa = SignValue * a;
return aa == v;
}
/// <summary>
/// 指定した値との大小を評価します。
/// </summary>
public int CompareTo(RationalNumber other) {
if(this > other) return 1;
if(this < other) return -1;
return 0;
}
public override int GetHashCode() {
//return sign.GetHashCode()
// ^ a.GetHashCode()
// ^ b.GetHashCode();
//return ToString().GetHashCode();
return ((0x5555555555555555 & a) ^ (0x2AAAAAAAAAAAAAAA & b)).GetHashCode();
}
//--------------------
//演算
public static RationalNumber operator +(RationalNumber x1, RationalNumber x2) {
var c = Lcm(x1.b, x2.b);
var x1a = x1.a * (c / x1.b) * x1.SignValue;
var x2a = x2.a * (c / x2.b) * x2.SignValue;
return new RationalNumber(x1a + x2a, c);
}
public static RationalNumber operator -(RationalNumber x1, RationalNumber x2) {
var c = Lcm(x1.b, x2.b);
var x1a = x1.a * (c / x1.b) * x1.SignValue;
var x2a = x2.a * (c / x2.b) * x2.SignValue;
return new RationalNumber(x1a - x2a, c);
}
public static RationalNumber operator *(RationalNumber x1, RationalNumber x2) {
var x1a = x1.a * x1.SignValue;
var x2a = x2.a * x2.SignValue;
return new RationalNumber(x1a * x2a, x1.b * x2.b);
}
public static RationalNumber operator /(RationalNumber x1, RationalNumber x2) {
var x1a = x1.a * x1.SignValue;
var x2a = x2.a * x2.SignValue;
return new RationalNumber(x1a * x2.b, x2a * x1.b);
}
public static bool operator ==(RationalNumber x1, RationalNumber x2) {
return x1.Equals(x2);
}
public static bool operator !=(RationalNumber x1, RationalNumber x2) {
return !x1.Equals(x2);
}
public static bool operator >(RationalNumber x1, RationalNumber x2) {
var c = Lcm(x1.b, x2.b);
var x1a = x1.a * (c / x1.b) * x1.SignValue;
var x2a = x2.a * (c / x2.b) * x2.SignValue;
return x1a > x2a;
}
public static bool operator >=(RationalNumber x1, RationalNumber x2) {
return x1 == x2 || x1 > x2;
}
public static bool operator <(RationalNumber x1, RationalNumber x2) {
return !(x1 >= x2);
}
public static bool operator <=(RationalNumber x1, RationalNumber x2) {
return !(x1 > x2);
}
//整数との演算
public static RationalNumber operator +(RationalNumber x1, long i) {
var x1a = x1.a * x1.SignValue;
return new RationalNumber(x1a + i * x1.b, x1.b);
}
public static RationalNumber operator -(RationalNumber x1, long i) {
var x1a = x1.a * x1.SignValue;
return new RationalNumber(x1a - i * x1.b, x1.b);
}
public static RationalNumber operator *(RationalNumber x1, long i) {
var x1a = x1.a * x1.SignValue;
return new RationalNumber(x1a * i, x1.b);
}
public static RationalNumber operator /(RationalNumber x1, long i) {
if (i == 0) throw new DivideByZeroException("0で除算を行いました。");
var x1a = x1.a * x1.SignValue;
return new RationalNumber(x1a, x1.b * i);
}
public static bool operator ==(RationalNumber x1, long i) {
return x1.Equals(i);
}
public static bool operator !=(RationalNumber x1, long i) {
return !x1.Equals(i);
}
public static bool operator >(RationalNumber x1, long i) {
return x1.a * x1.SignValue > i * x1.b;
}
public static bool operator >=(RationalNumber x1, long i) {
return x1 == i || x1 > i;
}
public static bool operator <(RationalNumber x1, long i) {
return !(x1 >= i);
}
public static bool operator <=(RationalNumber x1, long i) {
return !(x1 > i);
}
/// <summary>
/// 最大公約数
/// </summary>
private static long Gcd(long m, long n) {
var x1 = Math.Max(m, n);
var x2 = Math.Min(m, n);
while (true) {
var mod = x1 % x2;
if (mod == 0) return x2;
x1 = x2;
x2 = mod;
}
}
/// <summary>
/// 最小公倍数
/// </summary>
private static long Lcm(long m, long n) {
var x1 = Math.Max(m, n);
var x2 = Math.Min(m, n);
var gcd = Gcd(x1, x2);
return x1 / gcd * x2;
}
}解説
インスタンス生成
var x = new RationalNumber(1, 3);
var y = RationalNumber.Parse("1/3");コンストラクタに分子と分母の値を指定してインスタンスを生成する。または分数形式の文字列をパースする。分母に0を渡すと0除算例外が発生する。フィールドは符号・分子・分母をそれぞれ保持していて、数値の統一のため値は約分された状態で格納される。
約分
/// <summary>
/// 約分します。
/// </summary>
private void Reduction() {
var c = Gcd(a, b);
a /= c;
b /= c;
}約分は分子と分母の最大公約数でその両方を除算する。
最大公約数はユークリッド互除法で実装してある。これと最小公倍数の二つを駆使して分数を操作する。
四則演算
public static RationalNumber operator +(RationalNumber x1, RationalNumber x2) {
var c = Lcm(x1.b, x2.b);
var x1a = x1.a * (c / x1.b) * x1.SignValue;
var x2a = x2.a * (c / x2.b) * x2.SignValue;
return new RationalNumber(x1a + x2a, c);
}
～普段は滅多に使うことがない演算子のオーバーロードを利用して四則演算を実装する。各計算は分数の手計算をやるのと同じ手順。
加減算
通分して計算する。つまり互いの分母の最小公倍数を取得し、それに合わせた分子の値で加減算を行う。
乗算
分子と分母の値をそれぞれ乗算する。極力オーバーフローを防ぐなら、事前に2つの値のたすき掛けに約分を行った方が良い。ただ結局は約分できない数の場合があり上限値が変わるわけでは無いので、そのまま計算して後で約分している。
除算
逆数を乗算する。これも事前の約分はしていない。
比較演算
public static bool operator >(RationalNumber x1, RationalNumber x2) {
var c = Lcm(x1.b, x2.b);
var x1a = x1.a * (c / x1.b) * x1.SignValue;
var x2a = x2.a * (c / x2.b) * x2.SignValue;
return x1a > x2a;
}
～比較演算子も同様にオーバーロードすることができる。基本的に加減算と同じで通分してから比較を行う。なお >, >=, <, <= は一つ実装すれば後は組み合わせて表現できる。
ソート
/// <summary>
/// 指定した値との大小を評価します。
/// </summary>
public int CompareTo(RationalNumber other) {
if(this > other) return 1;
if(this < other) return -1;
return 0;
}Listなどでソートが可能なようにICompareTo<T>メソッドも実装する。演算子を呼んでるだけ。
ハッシュ値
public override int GetHashCode() {
//return sign.GetHashCode()
// ^ a.GetHashCode()
// ^ b.GetHashCode();
//return ToString().GetHashCode();
return ((0x5555555555555555 & a) ^ (0x2AAAAAAAAAAAAAAA & b)).GetHashCode();
}ハッシュテーブルや辞書で使えるようにGetHashメソッドをオーバーライドする。
実はこのクラスはAtCoderのABC168-Eのために作ったのだが、一部のケースでLTEが出てしまっていた。
自作クラスのハッシュ値はコメントのように各フィールドのハッシュ値の排他的論理和をとるのが一般的らしいが、どうもそれだと値の衝突が多いケースがあり、Dictionaryの検索に時間がかかってるようだった。
辞書用のハッシュ値が32ビットである限り情報の欠落は免れないので、サンプルによって衝突率は変わってしまう。とりあえずコードのようなハッシュにした。
平均的には文字表現のハッシュ値とするのが、生成コストは高いがバラつきが少なそうな気はする。
テストケースと結果
分数や整数のまま計算を進めることができる。
Debug.WriteLine("生成");
Debug.WriteLine(" 1,3 = " + new RationalNumber(1, 3));
Debug.WriteLine("-1,3 = " + new RationalNumber(-1, 3));
Debug.WriteLine(" 2,6 = " + new RationalNumber(2, 6));
Debug.WriteLine("");
Debug.WriteLine("' 1/3' = " + RationalNumber.Parse("1/3"));
Debug.WriteLine("'-1/3' = " + RationalNumber.Parse("-1/3"));
Debug.WriteLine("' 2/6' = " + RationalNumber.Parse("2/6"));生成 1,3 = 1/3 -1,3 = -1/3 2,6 = 1/3 ' 1/3' = 1/3 '-1/3' = -1/3 ' 2/6' = 1/3
Debug.WriteLine("逆数");
x1 = new RationalNumber(5);
Debug.WriteLine($"{x1}^-1 = {x1.Inverse()}");
Debug.WriteLine($"{x1}^-1^-1 = {x1.Inverse().Inverse()}");逆数 5^-1 = 1/5 5^-1^-1 = 5
Debug.WriteLine("計算");
x1 = new RationalNumber(3, 8);
x2 = new RationalNumber(1, 3);
Debug.WriteLine($"{x1} ＋ {x2} = {x1 + x2}");
Debug.WriteLine($"{x1} － {x2} = {x1 - x2}");
Debug.WriteLine($"{x1} × {x2} = {x1 * x2}");
Debug.WriteLine($"{x1} ÷ {x2} = {x1 / x2}");
Debug.WriteLine("");
x1 = new RationalNumber(1, 3);
x2 = new RationalNumber(-1, 3);
Debug.WriteLine($"{x1} ＋ {x2} = {x1 + x2}");
Debug.WriteLine($"{x1} － {x2} = {x1 - x2}");
Debug.WriteLine($"{x1} × {x2} = {x1 * x2}");
Debug.WriteLine($"{x1} ÷ {x2} = {x1 / x2}");
Debug.WriteLine("");
x1 = new RationalNumber(1, 3);
Debug.WriteLine($"{x1} ＋ {1} = {x1 + 1}");
Debug.WriteLine($"{x1} － {1} = {x1 - 1}");
Debug.WriteLine($"{x1} × {2} = {x1 * 2}");
Debug.WriteLine($"{x1} ÷ {2} = {x1 / 2}");計算 3/8 ＋ 1/3 = 17/24 3/8 － 1/3 = 1/24 3/8 × 1/3 = 1/8 3/8 ÷ 1/3 = 9/8 1/3 ＋ -1/3 = 0 1/3 － -1/3 = 2/3 1/3 × -1/3 = -1/9 1/3 ÷ -1/3 = -1 1/3 ＋ 1 = 4/3 1/3 － 1 = -2/3 1/3 × 2 = 2/3 1/3 ÷ 2 = 1/6
Debug.WriteLine("評価");
Debug.WriteLine($"1/3 == 1/3 ? {new RationalNumber(1, 3) == new RationalNumber(1, 3)}");
Debug.WriteLine($"1/3 == 2/6 ? {new RationalNumber(1, 3) == new RationalNumber(2, 6)}");
Debug.WriteLine($"1/3 == 1/6 ? {new RationalNumber(1, 3) == new RationalNumber(1, 6)}");
Debug.WriteLine($"9/3 == 3 ? {new RationalNumber(9, 3) == 3}");
Debug.WriteLine($"9/3 == 5 ? {new RationalNumber(9, 3) == 5}");
Debug.WriteLine("");
x1 = new RationalNumber(1, 3);
x2 = new RationalNumber(2, 5);
Debug.WriteLine($"{x1} < {x2} ? {x1 < x2}");
Debug.WriteLine($"{x1} > {x2} ? {x1 > x2}");
Debug.WriteLine($"{x1} <= {x2} ? {x1 <= x2}");
Debug.WriteLine($"{x1} >= {x2} ? {x1 >= x2}");
x1 = new RationalNumber(1, 3);
x2 = new RationalNumber(1, 3);
Debug.WriteLine($"{x1} <= {x2} ? {x1 <= x2}");
Debug.WriteLine($"{x1} >= {x2} ? {x1 >= x2}");
x1 = new RationalNumber(1, 3);
x2 = new RationalNumber(-2, 5);
Debug.WriteLine($"{x1} < {x2} ? {x1 < x2}");
Debug.WriteLine($"{x1} > {x2} ? {x1 > x2}");
Debug.WriteLine("");
x1 = new RationalNumber(7, 3);
Debug.WriteLine($"{x1} < {2} ? {x1 < 2}");
Debug.WriteLine($"{x1} > {2} ? {x1 > 2}");
Debug.WriteLine($"{x1} <= {2} ? {x1 <= 2}");
Debug.WriteLine($"{x1} >= {2} ? {x1 >= 2}");
x1 = new RationalNumber(6, 3);
Debug.WriteLine($"{x1} <= {2} ? {x1 <= 2}");
Debug.WriteLine($"{x1} >= {2} ? {x1 >= 2}");評価 1/3 == 1/3 ? True 1/3 == 2/6 ? True 1/3 == 1/6 ? False 9/3 == 3 ? True 9/3 == 5 ? False 1/3 < 2/5 ? True 1/3 > 2/5 ? False 1/3 <= 2/5 ? True 1/3 >= 2/5 ? False 1/3 <= 1/3 ? True 1/3 >= 1/3 ? True 1/3 < -2/5 ? False 1/3 > -2/5 ? True 7/3 < 2 ? False 7/3 > 2 ? True 7/3 <= 2 ? False 7/3 >= 2 ? True 2 <= 2 ? True 2 >= 2 ? True
Debug.WriteLine("計算式");
x1 = new RationalNumber(1, 3);
Debug.WriteLine("(1/3 ＋ 2) × 5 ÷ 2 － 3 = " + $"{ (x1 + 2) * 5 / 2 - 3 }");計算式 (1/3 ＋ 2) × 5 ÷ 2 － 3 = 17/6
とれる値の範囲
通分や乗算による分子および分母の掛け算が計算過程で出現する最大値になる。値は64bit整数のため分子と分母それぞれの絶対値が √long.MaxValue 未満であれば、それらの計算ではオーバーフローしないことになる。
つまり最小精度は 1/3037000000 程度。checkedを入れておくのが吉。
課題
たとえば x がこのクラスだとして「x + 1 / 2」のような式は理想の結果にならない。「1 / 2」の部分が先に評価され、整数同士の演算で小数点以下が切り捨てられ0になる。
ここまで来たら「整数型 / 整数型」でこのオブジェクトを返すようにしたいところだが、拡張メソッドなどを用いても、組み込み型の演算子をオーバーライドする方法は今のところ無いようだ。今後のC#の仕様拡張でできるようになるかもしれないが。
コメント
コメントを投稿