有理数

有理数のクラスを自作する。有理数のクラスといっても構成法はいろいろとあるし、 どこまでの性質を取り入れるかによって、構成難度もかわる。 単純なケースから始め、徐々に新しい機能を追加していく。

必要な知識

C#の知識: 演算子オーバーロード,LINQ,インターフェイスなど.
数学的知識: 有理数の性質,整数論の基礎(GCD)など.

usingディレクティブ

以下では、usingディレクティブは省略するが、

using System;
using System.Collections.Generic;
using System.Linq;
などを利用する。もし不足している場合は補ってほしい。 また、コード例3以降は、BigIntegerを使用するために、
using System.Numerics;
をさらに追加するが、これには「参照の追加」をする必要があるので注意。

コード例1(単純なケース)

基本的な構造を理解するため、ほとんどint型データのペアとなるようなクラスから始める。

class Program
{
    static void Main(string[] args)
    {
        Rational r1 = new Rational(1, 2);
        Rational r2 = new Rational(2, 4);
        Console.WriteLine($"r1 = {r1}");
        Console.WriteLine($"r2 = {r2}");
        Console.WriteLine($"{r1} + {r2} = {r1+r2}");
    }
}
class Rational
{
    public int N { get; set; }
    public int D { get; set; }
    public Rational(int n, int d)
    {
        N = n;
        D = d;
    }
    public static Rational operator +(Rational x, Rational y)
    {
        var a = x.N; var b = x.D; var c = y.N; var d = y.D;
        return new Rational(a * d + b * c, b * d);
    }
    public override string ToString() { return $"{N}/{D}"; }
}

実行結果.

r1 = 1/2
r2 = 2/4
1/2 + 2/4 = 8/8

解説

プロパティのNは分子。Dは分母とする。コンストラクタでは引数をそのまま渡している。したがって、 実行結果のように、約分可能な有理数がそのまま約分されずに表示される。

有理数クラスの2項演算子「+」定義部分が次の個所.

public static Rational operator +(Rational x, Rational y)
{
    var a = x.N; var b = x.D; var c = y.N; var d = y.D;
    return new Rational(a * d + b * c, b * d);
}

ここでは

\[\frac{a}{b} + \frac{c}{d} = \frac{ad+bc}{bd}\]

という関係式を用いている。他の2項演算子「-,*,/」も同様に定義できる。

改善したい点

  • 約分を自動化したい。
  • 大きな数を扱いたい。
  • "1/2"のような文字列からインスタンスを生成したい。
  • LINQの集合演算機能を使用したい。
  • LINQのOrderByを利用したい。

コード例2(自動的に約分する機能を追加)

約分を自動化し、分母が常に正となるように設定する。

class Program
{
    static void Main(string[] args)
    {
        Rational r1 = new Rational(3, 6);
        Rational r2 = new Rational(1, -3);
        Console.WriteLine($"r1 = {r1}");
        Console.WriteLine($"r2 = {r2}");
        Console.WriteLine($"{r1} + ({r2}) = {r1 + r2}");
    }
}

class Rational
{
    public int N { get; set; }
    public int D { get; set; }
    public Rational(int n, int d)
    {
        if (d < 0)
        {
            n *= -1;
            d *= -1;
        }
        var gcd = GCD(n, d);
        N = n/gcd;
        D = d/gcd;
    }
    public static Rational operator +(Rational x, Rational y)
    {
        var a = x.N; var b = x.D; var c = y.N; var d = y.D;
        return new Rational(a * d + b * c, b * d);
    }
    public static int GCD(int a, int b)
    {
        if (a < 0) { a *= -1; }
        if (b < 0) { b *= -1; }
        while(b != 0)
        {
            var tmp = a;
            a = b;
            b = tmp % b;
        }
        return a;
    }
    public override string ToString() { return $"{N}/{D}"; }
}

実行結果.

r1 = 1/2
r2 = -1/3
1/2 + (-1/3) = 1/6

解説

最大公約数を求めるGCDを追加。今回は、コンストラクタでは引数を約分してから渡している。 約分というのは、最大公約数GCD(n,d)で分子と分母を割るということ。GCDはMathクラスに入っていても良さそうだが なぜか存在しないので、自作している。

コンストラクタの

if (d < 0) { n *= -1; d *= -1; }

では分母が負であった場合は、分母分子を-1倍して、分母を正にする操作を行っている。 この処理を行うことで、常に分母は負でないと仮定できる。

Main関数の中ではr1=3/6として定義しているが、表示するとしっかりと約分されて1/2になっていることが確認できるし また、分母も負を取らないようになっていることも注目したい。

改善したい点(残り)

  • 大きな数を扱いたい。
  • "1/2"のような文字列からインスタンスを生成したい。
  • LINQの集合演算機能を使用したい。
  • LINQのOrderByを利用したい。

コード例3(大きな数を扱えるようにする)

ここからBigIntegerを用いるので、using System.Numerics; が必要。ただこれは参照の追加をする必要がある。

参照の追加方法.

ソリューションエクスプローラーから「参照」を右クリックして「参照の追加」。アセンブリから「System.Numerics」を選ぶ。

class Program
{
    static void Main(string[] args)
    {
        BigInteger b1 = 12323218;
        BigInteger b2 = 12311222;
        BigInteger b3 = 21239;
        BigInteger b4 = BigInteger.Parse("15623442231315512432"); 
        // とても大きな数は ↑ のように利用する。(ただし少し面倒なので次の例でこの点を改善する。)
        Rational r1 = new Rational(b1,b2);
        Rational r2 = new Rational(b3, b4);
        Console.WriteLine($"r1={r1}");
        Console.WriteLine($"r2={r2}");
        Console.WriteLine($"{r1}+{r2}={r1 + r2}");
    }
}
class Rational
{
    public BigInteger N;
    public BigInteger D;
    public Rational(BigInteger n, BigInteger d)
    {
        var gcd = BigInteger.GreatestCommonDivisor(n, d);
        if (d < 0) { n *= -1; d *= -1; }
        N = n / gcd;
        D = d / gcd;
    }
    public static Rational operator +(Rational x, Rational y)
    {
        var a = x.N; var b = x.D; var c = y.N; var d = y.D;
        return new Rational(a * d + b * c, b * d);
    }
    public override string ToString()
    {
        return $"{N}/{D}";
    }
}

実行結果.

r1=6161609/6155611
r2=21239/15623442231315512432
6161609/6155611+21239/15623442231315512432=96265542263453873979645117/96171832856950312797055952

解説

BigIntegerは特に桁数制限がない整数のクラス。 分子分母をBigIntegerにすることでオーバーフローを防止する。 コード例2では、最大公約数を計算するメソッドを自作したが、幸いBigIntegerには GCDを計算するメソッドが用意されているのでこれを利用した。

改善したい点(残り)

  • "1/2"のような文字列からインスタンスを生成したい。
  • LINQの集合演算機能を使用したい。
  • LINQのOrderByを利用したい。

コード例4 (インスタンス生成を簡略化する)

新たにコンストラクタを追加して "1/2" というような文字列からインスタンスを生成できるようにする。 小さい数だと初期化の労力はあまり変わらないが、大きな数になると相当簡略化される。

class Program
{
    static void Main(string[] args)
    {
        Rational r1 = new Rational("123123123123123123123123/122132");
        Rational r2 = new Rational("21312/1232");
        Console.WriteLine($"r1={r1}");
        Console.WriteLine($"r2={r2}");
        Console.WriteLine($"{r1}+{r2}={r1 + r2}");
    }
}
class Rational
{
    public BigInteger N;
    public BigInteger D;
    public Rational(BigInteger n, BigInteger d)
    {
        var gcd = BigInteger.GreatestCommonDivisor(n, d);
        if (d < 0) { n *= -1; d *= -1; }
        N = n / gcd;
        D = d / gcd;
    }
    public Rational(string s)
    {
        if (s.Contains('.'))
        {
            throw new ArgumentException("小数点「.」には対応していません。");
        }
        if (s.Contains('/'))
        {
            var words = s.Split('/');
            var n = BigInteger.Parse(words[0]);
            var d = BigInteger.Parse(words[1]);
            var gcd = BigInteger.GreatestCommonDivisor(n, d);
            if (d < 0) { n *= -1; d *= -1; }
            N = n / gcd; D = d / gcd;
        }
        else
        {
            N = BigInteger.Parse(s);
            D = 1;
        }
    }

    public static Rational operator +(Rational x, Rational y)
    {
        var a = x.N; var b = x.D; var c = y.N; var d = y.D;
        return new Rational(a * d + b * c, b * d);
    }
    public override string ToString()
    {
        return $"{N}/{D}";
    }
}

実行結果.

r1=123123123123123123123123/122132
r2=1332/77
123123123123123123123123/122132+1332/77=9480480480480480643160295/9404164

解説

新たに追加したコンストラクタは文字列からインスタンスを作るもの。 小数点付きの数も扱えるのが望ましいが、今回はそのような文字列が与えられた場合エラーとする。

改善したい点(残り)

  • LINQの集合演算機能を使用したい。
  • LINQのOrderByを利用したい。

コード例5 (暗黙的型変換を利用する)

暗黙的型変換を利用して、さらにインスタンス生成を簡略化する。

class Program
{
    static void Main(string[] args)
    {
        Rational r1 = "31/2";
        Rational r2 = "17/3205";
        Rational r3 = 123;
        Console.WriteLine($"r1={r1}");
        Console.WriteLine($"r2={r2}");
        Console.WriteLine($"r3={r3}");
    }
}
class Rational
{
    public BigInteger N { get; set; }
    public BigInteger D { get; set; }
    public Rational(BigInteger n, BigInteger d)
    {
        var gcd = BigInteger.GreatestCommonDivisor(n, d);
        if (d < 0) { n *= -1; d *= -1; }
        N = n / gcd; D = d / gcd;
    }
    public Rational(string s)
    {
        if (s.Contains('.'))
        {
            throw new ArgumentException("小数点「.」には対応していません。");
        }
        if (s.Contains('/'))
        {
            var words = s.Split('/');
            var n = BigInteger.Parse(words[0]);
            var d = BigInteger.Parse(words[1]);
            var gcd = BigInteger.GreatestCommonDivisor(n, d);
            if (d < 0) { n *= -1; d *= -1; }
            N = n / gcd; D = d / gcd;
        }
        else
        {
            N = BigInteger.Parse(s);
            D = 1;
        }
    }
    public static Rational operator +(Rational x, Rational y)
    {
        var a = x.N; var b = x.D; var c = y.N; var d = y.D;
        return new Rational(a * d + b * c, b * d);
    }
   
    public static implicit operator Rational(BigInteger a)
    {
        return new Rational(a, 1);
    }
    public static implicit operator Rational(int a)
    {
        return new Rational(a, 1);
    }
    public static implicit operator Rational(string s)
    {
        return new Rational(s);
    }
    public override string ToString()
    {
        if (D == 1)
        {
            return $"{N}";
        }
        return $"{N}/{D}";
    }
}

実行結果.

r1=31/2
r2=17/3205
r3=123

解説

暗黙的変換を利用して、直接文字列や整数を代入することができるように設定した。 これによってインスタンス生成が簡略化される。ついでに、分母が1のときは、分母を表示しないように ToStringを少し書きかえた。

改善したい点(残り)

  • LINQの集合演算機能を使用したい。
  • LINQのOrderByを利用したい。

コード例6 (LINQに対応させる)

これまでの定義ではまだ、Rational型の配列やリストに対して、集合演算や並べ替えのOrderByメソッドは利用できない。 これらのメソッドを利用できるようにするには、特定のインターフェイスを継承する必要がある。

class Program
{
    static void Main(string[] args)
    {
        List<Rational> list = new List<Rational>();
        for (int i = 1; i <= 4; i++)
        {
            for (int k = 1; k <= i; k++)
            {
                list.Add($"{k}/{i}");
            }
        }
        Console.WriteLine("A={" + string.Join(",",list)+"}");
        Console.WriteLine("B={" + string.Join(",",list.Distinct())+"}");
        Console.WriteLine("C={" + string.Join(",",list.Distinct().OrderBy(x=>x))+"}");
    }
}
class Rational : IEquatable<Rational>, IComparable<Rational>
{
    public BigInteger N { get; set; }
    public BigInteger D { get; set; }
    public Rational(BigInteger n, BigInteger d)
    {
        var gcd = BigInteger.GreatestCommonDivisor(n, d);
        if (d < 0) { n *= -1; d *= -1; }
        N = n / gcd; D = d / gcd;
    }
    public Rational(string s)
    {
        if (s.Contains('.'))
        {
            throw new ArgumentException("小数点「.」には対応していません。");
        }
        if (s.Contains('/'))
        {
            var words = s.Split('/');
            var n = BigInteger.Parse(words[0]);
            var d = BigInteger.Parse(words[1]);
            var gcd = BigInteger.GreatestCommonDivisor(n, d);
            if (d < 0) { n *= -1; d *= -1; }
            N = n / gcd; D = d / gcd;
        }
        else
        {
            N = BigInteger.Parse(s);
            D = 1;
        }
    }
    public static Rational operator +(Rational x, Rational y)
    {
        var a = x.N; var b = x.D; var c = y.N; var d = y.D;
        return new Rational(a * d + b * c, b * d);
    }
    public static Rational operator -(Rational x, Rational y)
    {
        var a = x.N; var b = x.D; var c = y.N; var d = y.D;
        return new Rational(a * d - b * c, b * d);
    }
    public static Rational operator *(Rational x, Rational y)
    {
        var a = x.N; var b = x.D; var c = y.N; var d = y.D;
        return new Rational(a * c, b * d);
    }
    public static Rational operator *(BigInteger k, Rational y)
    {
        return new Rational(k * y.N, y.D);
    }
    public static Rational operator *(Rational x, BigInteger k)
    {
        return new Rational(k * x.N, x.D);
    }
    public static Rational operator /(Rational x, Rational y)
    {
        var a = x.N; var b = x.D; var c = y.D; var d = y.N;
        return new Rational(a * c, b * d);
    }
    public static implicit operator Rational(BigInteger a)
    {
        return new Rational(a, 1);
    }
    public static implicit operator Rational(int a)
    {
        return new Rational(a, 1);
    }
    public static implicit operator Rational(string s)
    {
        return new Rational(s);
    }
    bool IEquatable<Rational>.Equals(Rational r)
    {
        if (r == null)
        {
            return false;
        }
        return N * r.D - D * r.N == 0;
    }
    public override int GetHashCode()
    {
        return (int)(N + 97 * D);
    }
    int IComparable<Rational>.CompareTo(Rational r)
    {
        var c = N * r.D - D * r.N;
        if (c > 0)
        {
            return 1;
        }
        else if (c < 0)
        {
            return -1;
        }
        else
        {
            return 0;
        }
    }
    public override string ToString()
    {
        if (D == 1){
            return $"{N}";
        }
        return $"{N}/{D}";
    }
}

実行結果.

A={1,1/2,1,1/3,2/3,1,1/4,1/2,3/4,1}
B={1,1/2,1/3,2/3,1/4,3/4}
C={1/4,1/3,1/2,2/3,3/4,1}

解説

継承すべきインターフェイスは、

IEquatable<Rational>, IComparable<Rational>

の二つ。前者は等しいかどうかを定めるもので、LINQの集合演算に必要。 後者は、大小関係を定義するもので、OrderByを利用するために必要。

実行結果を見ると、集合Aには重複した要素が見られるが、集合Bにはそれら重複要素はない。 また集合Cでは昇順に並べ替えが行われている。

ついでというわけではないが、かけ算や割り算なども追加でオーバーロードしている。

GetHashCodeの定義中の97という数にはさほどの理由はない。例えば100にして実行速度がどの程度 かわるのかは不明。ただし、1や2にしたとき、実行スピードが落ちる例は簡単に構成できる。