初歩的な数学のアルゴリズムを考えてみよう

はじめに

こんにちは。よっしーと申します。
私の趣味の一つに数学があるのですが数学の公式や定理をプログラミングで実装したりすると
アルゴリズムの勉強になったり、頭の体操になったりしますので今日はその紹介をしようと思います。
今回は最大公約数を求めるアルゴリズムを考えてみます。
素直に求めるやり方と、効率よく求める方法を考えてそれぞれコードに落とし込んでみます。

最大公約数を求める

最大公約数って何

2つの正の整数の共通の約数のうちの最大のものを最大公約数と言います。

例えば、72 と 1620 は以下で表せます。

$72 = 2 \times 36$
$1620 = 45 \times 36$

互いに36という約数を持っており、2数で共通の約数はもう持てません(2と45で共通の約数はない)。
そのため、72と1620は共通の約数で最大のものは36となります。
36は72と1620の最大公約数です。

最大公約数の求め方

愚直にやってみます。
いきなり36と出すのは難しいので、まず2数を素因数分解します。

$72 = 2^3 \times 3^2$
$1620 = 2^2 \times 3^4 \times 5$

このうち、出てきた素因数で、お互いに登場している数のうち指数が小さい数を取得し掛け算すれば最大公約数が求まります。
ここでは、2という素因数と3という素因数が2数で登場しています。
そのうち $2^2$ , $3^2$ を取得すればそれの掛け算である36が最大公約数です。

これをプログラムで求める

先程の最大公約数の求め方を実装してみます。
実装は先程の求め方に忠実に行います(よりいいアルゴリズムがあるかもしれませんが、忠実に再現します)。
言語はC#です。

using System;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleApp1
{
  class Program
  {
    static void Main(string[] args)
    {
      var val1 = 72;
      var val2 = 1620;
      var largeVal = val1 > val2 ? val1 : val2;
      Primes = CreatePrimes(largeVal);

      Console.WriteLine(CalculateGcd(val1, val2));
    }

    private static List<int> Primes;

    private static int CalculateGcd(int val1, int val2)
    {
      var gcd = 1;

      var val1Primes = PrimeFactorization(val1);
      var val2Primes = PrimeFactorization(val2);

      var commonPrimes = val1Primes.Keys.Where(x => val2Primes.Keys.Contains(x));
      foreach (var prime in commonPrimes)
      {
        // 個数が少ない方を採用して累乗を掛ける
        gcd *= val1Primes[prime] > val2Primes[prime]
          ? (int)Math.Pow(prime, val2Primes[prime])
          : (int)Math.Pow(prime, val1Primes[prime]);
      }

      return gcd;
    }

    // 素因数分解をする。 例えば 1620 = 2^2 * 3^4 * 5 なら以下のようになる
    // {
    //   {2, 3},
    //   {3, 4},
    //   {5, 1}
    // }
    private static IDictionary<int, int> PrimeFactorization(int val)
    {
      var dic = new Dictionary<int, int>();

      do
      {
        foreach (var prime in Primes)
        {
          if (val % prime != 0)
          {
            continue;
          }

          val /= prime;
          if (!dic.Keys.Contains(prime))
          {
            dic.Add(prime, 0);
          }

          dic[prime] = dic[prime] + 1;
          break;
        }
      } while (val != 1);

      return dic;
    }

    // 最大の数までの素数リストを取得
    private static List<int> CreatePrimes(int max)
    {
      // 素数のリスト作成の手法はエラトステネスのふるいというアルゴリズムを参考に作成しています。
      // 興味がある方はそちらも是非ご確認ください。

      int prime;
      double sqrtMax = Math.Sqrt(max);
      var primeList = new List<int>();

      var searchList = Enumerable.Range(2, max - 1).ToList();

      do
      {
        prime = searchList.First();
        primeList.Add(prime);
        searchList.RemoveAll(n => n % prime == 0);

      } while (prime < sqrtMax);

      primeList.AddRange(searchList);

      return primeList;
    }
  }
}

using System;

using System.Collections.Generic;

using System.Linq;

namespace ConsoleApp1

{

class Program

{

static void Main(string[] args)

{

var val1 = 72;

var val2 = 1620;

var largeVal = val1 > val2 ? val1 : val2;

Primes = CreatePrimes(largeVal);

Console.WriteLine(CalculateGcd(val1, val2));

}

private static List<int> Primes;

private static int CalculateGcd(int val1, int val2)

{

var gcd = 1;

var val1Primes = PrimeFactorization(val1);

var val2Primes = PrimeFactorization(val2);

var commonPrimes = val1Primes.Keys.Where(x => val2Primes.Keys.Contains(x));

foreach (var prime in commonPrimes)

{

// 個数が少ない方を採用して累乗を掛ける

gcd *= val1Primes[prime] > val2Primes[prime]

? (int)Math.Pow(prime, val2Primes[prime])

: (int)Math.Pow(prime, val1Primes[prime]);

}

return gcd;

}

// 素因数分解をする。例えば 1620 = 2^2 * 3^4 * 5 なら以下のようになる

// {

// {2, 3},

// {3, 4},

// {5, 1}

// }

private static IDictionary<int, int> PrimeFactorization(int val)

{

var dic = new Dictionary<int, int>();

{

foreach (var prime in Primes)

{

if (val % prime != 0)

{

continue;

}

val /= prime;

if (!dic.Keys.Contains(prime))

{

dic.Add(prime, 0);

}

dic[prime] = dic[prime] + 1;

break;

}

} while (val != 1);

return dic;

}

// 最大の数までの素数リストを取得

private static List<int> CreatePrimes(int max)

{

// 素数のリスト作成の手法はエラトステネスのふるいというアルゴリズムを参考に作成しています。

// 興味がある方はそちらも是非ご確認ください。

int prime;

double sqrtMax = Math.Sqrt(max);

var primeList = new List<int>();

var searchList = Enumerable.Range(2, max - 1).ToList();

{

prime = searchList.First();

primeList.Add(prime);

searchList.RemoveAll(n => n % prime == 0);

} while (prime < sqrtMax);

primeList.AddRange(searchList);

return primeList;

}

これで求めることができました。
手順としては

素因数分解に必要な素数を準備
2数を素因数分解する
素因数の中から最大公約数を見つける

という手順を用いました。

ユーグリッド互除法により最大公約数を求める

今度は少し複雑な数を考えてみましょう。
3355と11895の最大公約数を求めてくださいと言われたらどうしますか？
プログラムでやるなら今まで説明してきた方法でもすぐに解答が出ます。
しかし、人の手で計算するとなると、素因数分解がやや面倒です(2, 3, 5….で割れるかいちいち試すのは少し面倒)。

最大公約数を求める方法としてユーグリッド互除法というものがあります。

手法としては以下です

大きい数を小さい数で割る
あまりが出た場合、先程割った小さい数をあまりで割る
更にあまりが出た場合、手順2で割った数をあまりで割る
手順3をあまりが0になるまで続ける
最後に割った数が最大公約数

先程あげた数で行うと以下です

$11895 \div 3355 = 3$ あまり $1830$
$3355 \div 1830 = 1$ あまり $1525$
$1830 \div 1525 = 1$ あまり $305$
$1525 \div 305 = 5$ あまり $0$

よって305が3355と11895の最大公約数となります。
この証明方法は特に解説しませんが、詳しく知りたい方はユーグリット互除法と調べていただけると出てきます。

これをプログラムに落とし込む

上記のユーグリット互除法をプログラムで書いてみましょう。
手順4あたりで同じ操作を何度も繰り返していることがわかると思います。
プログラムでは、再帰的なメソッド呼び出しになりそうという予想が立ちます。
言語はまたしてもC#です。

using System;

namespace ConsoleApp2
{
  class Program
  {
    static void Main(string[] args)
    {
      var val1 = 3355;
      var val2 = 11895;

      Console.WriteLine(CalculateGcd(val2, val1));
    }

    public static int CalculateGcd(int val1, int val2)
    {
      if (val2 == 0)
      {
        return val1;
      }

      return CalculateGcd(val2, val1 % val2);
    }
  }
}

using System;

namespace ConsoleApp2

{

class Program

{

static void Main(string[] args)

{

var val1 = 3355;

var val2 = 11895;

Console.WriteLine(CalculateGcd(val2, val1));

}

public static int CalculateGcd(int val1, int val2)

{

if (val2 == 0)

{

return val1;

}

return CalculateGcd(val2, val1 % val2);

}

とてもシンプルなメソッドになりました。
それに、やってることもわかりやすいと思います。
(元々割っていた数字をあまりで割っていくという構図)

終わりに

2つの方法で最大公約数を求めるアルゴリズムを考えてみました。
後者のコードはより簡単な計算手法を考えてからコードに落としたこともあり、相当スッキリしたコードになりました。
数学の公式というのは複雑な計算を、より簡単な計算式や、容易な考え方に落とし込んだものが本質となります。
アルゴリズムを考えるときも同じようにどのような計算方法で行えば楽なコードが書けるかを考えてみると今後の開発の役に立つかもしれません。
そういうトレーニングをしたい場合は数学の公式の成り立ち等を勉強してそれをコードに落とし込んだりすると練習になるかもしれません。
ここまで読んでくださった皆様ありがとうございます！ではまた。

社員インタビュー第8弾：修羅場ってどのように乗り越えるんですか？？？

量子フーリエ変換

初歩的な数学のアルゴリズムを考えてみよう

はじめに

最大公約数を求める

最大公約数って何

最大公約数の求め方

これをプログラムで求める

ユーグリッド互除法により最大公約数を求める

これをプログラムに落とし込む

終わりに

最近の記事

レイアウト解析

ChatGPTを用いた画像異常検知

クォータニオンと回転行列の関係

OpenCVで深層学習

OpenCVのcv::Matに関する小ネタ集

テンソルネットワークの入り口（その2）

毎月アルゴリズム – 第3回 –

毎月アルゴリズム – 第7回 –

毎月アルゴリズム – 第2回 –

毎月アルゴリズム – 第6回 –

毎月アルゴリズム – 第4回 –

毎月アルゴリズム – 第1回 –

Google Vision APIでOCR

アーカイブ

カテゴリー