【C#】最大公約数を求める/分数の約分をする（ユークリッドの互除法）

2020/11/13 Fri [edit]

　ちょっとアプリを作っていて、画面解像度のアスペクト比(整数)を計算させようと思ったのだが、C# ではユークリッドの互除法のライブラリを作ってなかった…。

　というわけで、以前に作った Java のコードをそのまま移植してみた。私はライブラリに関しては、割と古い書き方をするので、ほぼ Java → C# への移植はコピペに近い感じでできる。Java8 なら、LINQ 的なもできるけど、C# とは互換性あまり無いし、実行速度の問題もある。ライブラリは古い書き方で、メインコードは LINQ や Rx など新しい書き方で、なんて使い分けも実はオススメだ(笑)。

■最大公約数を求める（ユークリッドの互除法）[非再帰版]
■最大公約数を求める（ユークリッドの互除法）[再帰版]
■分数の約分をする
■３つ以上の最大公約数を求める（ユークリッドの互除法②）

■最大公約数を求める（ユークリッドの互除法）[非再帰版]

　ユークリッドの互除法の実装を調べると、非再帰と再帰でのやり方が出てくると思うが、一応両方書いておこう。普通に使うなら、非再帰版で良いと思うが、シンプルに書きたいときなどは再帰版でも良いかもね。

●最大公約数を求める（ユークリッドの互除法）[非再帰版]

/// <summary>
/// 最大公約数を求める(Greatest Common Divisor).
/// ユークリッドの互除法 (非再帰版).
/// 2020/11/12 Fantom (Java から移植)
/// http://fantom1x.blog130.fc2.com/blog-entry-384.html
/// http://fantom1x.blog130.fc2.com/blog-entry-215.html
/// </summary>
/// <param name="a">数値1 (>0)</param>
/// <param name="b">数値2 (>0)</param>
/// <returns>最大公約数 (なし=1 [互いに素])</returns>
public static int Gcd(this int a, int b)
{
    //a > b にする（スワップ）
    if (a < b)
    {
        int tmp = a;
        a = b;
        b = tmp;
    }

    //ユークリッドの互除法
    int r = -1;
    while (r != 0)
    {
        r = a % b;
        a = b;
        b = r;
    }

    return a;  //b には r = 0 の値が入るため、a を返す
}

●メインコード例

using System;

int a = 1920;
int b = 1080;
int d = Gcd(a, b);
Console.WriteLine("d = " + d);  //最大公約数
Console.WriteLine(a + "x" + b + " => " + (a / d) + ":" + (b / d));  //約分に利用

d = 120
1920x1080 => 16:9

　a > 0, b > 0 となっているので注意（特に負の剰余は言語によって結果が違うので注意）。

　Java からのそのまま移植なので、解説は以前の記事を見て欲しい。ユークリッド互除法に関する説明も Wikipedia で良いだろう（アニメーションがとてもわかり易い）。数学的なものはこの辺りの例を見ればわかるだろう。

・【Java】最大公約数・最小公倍数を求める（ユークリッドの互除法）
・ユークリッドの互除法 (Wikipedia)
・最大公約数と最小公倍数

■最大公約数を求める（ユークリッドの互除法）[再帰版]

●最大公約数を求める（ユークリッドの互除法）[再帰版]

/// <summary>
/// 最大公約数を求める(Greatest Common Divisor).
/// [ユークリッドの互除法] (再帰版).
/// 2020/11/12 Fantom (Java から移植)
/// http://fantom1x.blog130.fc2.com/blog-entry-384.html
/// http://fantom1x.blog130.fc2.com/blog-entry-215.html
/// </summary>
/// <param name="a">数値1 (>0) (a >= b)</param>
/// <param name="b">数値2 (>0)</param>
/// <returns>最大公約数 (なし=1 [互いに素])</returns>
public static int GcdRec(int a, int b) 
{
    return (b == 0) ? a : GcdRec(b, a % b);
}

●メインコード例

using System;

int a = 1920;
int b = 1080;
int d =  (a >= b) ? GcdRec(a, b) : GcdRec(b, a);  //a >= b にする
Console.WriteLine("d = " + d);  //最大公約数
Console.WriteLine(a + "x" + b + " => " + (a / d) + ":" + (b / d));  //約分に利用

d = 120
1920x1080 => 16:9

　a > 0, b > 0 となっているので注意（特に負の剰余は言語によって結果が違うので注意）。
　また、再帰版は、a >= b を関数内でチェックしてないので少し注意だ。

　また、シンプルなので再帰的な書き方は好まれる傾向があるが、再帰というのは自身のメソッドを呼ぶたびにスタックを積むため、メモリ的には優しくない。特にスマホみたいなメモリが小さいものには要注意だ。Gcd ではそれほど深くはならないかもだが、フィボナッチ数などで大きな数になると、かなりの深さになることもある。もし使わなくても書けるなら、使わない方が良い（フィボナッチ数も動的計画法を使うと良い）。

■分数の約分をする

　Gcd の使用例で約分しているが、それを簡単にまとめたものを作ってみよう。引数 a, b を分数の分子/分母に見立てただけのものである。これが分数の約分計算と同等になる。

●分数の約分をする

/// <summary>
/// a / b の約分をする
/// 2020/11/12 Fantom 
/// http://fantom1x.blog130.fc2.com/blog-entry-384.html
/// </summary>
/// <param name="a">分子 (>0)</param>
/// <param name="b">分母 (>0)</param>
/// <returns></returns>
public static (int, int) Reduce(this int a, int b)
{
    int d = Gcd(a, b);  //最大公約数
    return (a / d, b / d);
}

●メインコード例

using System;

int width = 1920;
int height = 1080;
var aspect = Reduce(width, height);
Console.WriteLine($"{width}x{height} => {aspect.Item1}:{aspect.Item2}");

1920x1080 => 16:9

　a > 0, b > 0 となっているので注意（特に負の剰余は言語によって結果が違うので注意）。

　.NET 4.x の書き方となっているので、.NET 3.5 以前なら、

public static int[] Reduce(this int a, int b)
{
    int d = Gcd(a, b);  //最大公約数
    return new int[]{ a / d, b / d };
}

にして、[0]分子/[1]分母にすれば良いだろう。

　これを使えば、アスペクト比(整数)の計算も簡単だ(笑)。

　ちなみに、.NET 4.x の方の書き方の戻値に (int, int) を使っているが、これはタプルと言い、C#7.3 以降からは値型の ValueTuple がデフォルトとなり、メモリパフォーマンスも良くなったようだ（以前は参照型で、パフォーマンスも悪かったらしい）。また、ここでは .Item1, .Item2,... のアクセサを使っているが、名前を付けることもできる。

　Unity の場合、2018.3 以降ではデフォルトで使えるようになっているので、int[] よりタプルの方が良いかも知れない（int[] は参照型なので、無駄にヒープを使うため）。詳しい内容は以下に参考資料を載せておくので、確認してみるのも良いだろう。

（参考）
・タプル記法 (ValueTuple)
・タプル型 (C# リファレンス)
・C# のメモリ管理
・Unity と C# のバージョン

■３つ以上の最大公約数を求める（ユークリッドの互除法②）

　もう１つ、ついでに３つ以上の数の最大公約数を求めるユークリッドの互除法も作っておこう。テスト用のコードには２つの Gcd との計算比較も書いておくので、それをまとめたものということもわかるだろう。

●３つ以上の最大公約数を求める（ユークリッドの互除法②）

/// <summary>
/// ３つ以上の最大公約数を求める[gcd(a, b, c,...)].
/// ユークリッドの互除法の繰り返しで求める.
/// 2020/11/12 Fantom (Java から移植)
/// http://fantom1x.blog130.fc2.com/blog-entry-384.html
/// http://fantom1x.blog130.fc2.com/blog-entry-220.html
/// </summary>
/// <param name="param">数値1, 2, 3,... (a, b, c,...) (>0) [引数は3個以上]</param>
/// <returns>最大公約数(なし=1[互いに素])</returns>
public static int Gcd(params int[] param) {
    int len = param.Length;
    int g = Gcd(param[0], param[1]);
    for (int i = 1; i < len - 1; i++)
    {
        g = Gcd(g, param[i + 1]);
    }
    return g;
}

●メインコード例

using System;

int a = 12;
int b = 36;
int c = 60;
int d = 96;

int g1 = Gcd(a, b);
int g2 = Gcd(g1, c);
int g3 = Gcd(g2, d);
Console.WriteLine("g3 = " + g3);

int g = Gcd(a, b, c, d);
Console.WriteLine("g  = " + g);
Console.WriteLine(g == g3);

g3 = 12
g = 12
true

　a > 0, b > 0 となっているので注意（特に負の剰余は言語によって結果が違うので注意）。

　これも Java コードそのままなので、解説は以前の記事を参照して欲しい。

・【Java】３つ以上の最大公約数を求める（ユークリッドの互除法②）
・The case of more than two numbers (Wikipedia)

　私は以前、アルゴリズム系の問題をよく Java で解いていたが、ちょっとしたとき、便利なアルゴリズムなんかもあったりするので、興味あったら勉強してみるのも良いかもね。アルゴリズム自体を完全理解しなくても（物によっては数学的に難しいものもある）、使い方だけ覚えておけば、色々なものに応用できることもある。アルゴリズム自体は特に言語に関係ないしね。１冊くらい何か読んでおくのはオススメ。