Java に限らないと思うけど、最大公約数(GCD:Greatest Common Divisor)を求めるには、ユークリッドの互除法 というものが良さ気らしい

f:id:ts0818:20190720104401j:plain

「エイドリア~ン!【映画:ロッキー】(監督:シルベスター・スタローン)」

ピエト・モンドリアンピート・モンドリアン、Piet Mondrian、本名ピーテル・コルネーリス・モンドリアーン Pieter Cornelis Mondriaan 1872年3月7日 - 1944年2月1日)は、19世紀末-20世紀オランダ出身の画家ワシリー・カンディンスキーカジミール・マレーヴィチらと並び、本格的な抽象絵画を描いた最初期の画家とされる。

ピエト・モンドリアン - Wikipedia

はい~、皆様ご存知、「ピエト・モンドリアン」の絵画の画像ですね。抽象絵画の傑作でございます、あ、どうもボクです。

というわけで、 今回は、

アレクサンドリアエウクレイデス古代ギリシャ語ΕὐκλείδηςEukleídēsラテン語Euclīdēs英語Euclidユークリッド)、紀元前3世紀? - )は、古代エジプトギリシャ系数学者天文学者とされる。数学史上最も重要な著作の1つ『原論』(ユークリッド原論)の著者であり、「幾何学の父」と称される。 

エウクレイデス - Wikipedia

⇧  ユークリッドさん が生み出したと言われる、「ユークリッドの互除法」のお話です。

ちなみに、全然関係ない話ですが、

ccse2019.peatix.com

⇧  行って参りました~。数学が重要になってくるという話が多かったですかね...私は文系ですが、何か?(涙)

 

そんでは、レッツトライ~。

 

ユークリッドの互除法 とは?

Wikipedia さんは、今日も答えてくれた。 

ユークリッドの互除法ユークリッドのごじょほう、Euclidean Algorithm)は、2 つの自然数最大公約数を求める手法の一つである。

2 つの自然数 ab (a ≧ b) について、a の b による剰余を r とすると、 a と b との最大公約数は b と r との最大公約数に等しいという性質が成り立つ。この性質を利用して、 b を r で割った剰余、 除数 r をその剰余で割った剰余、と剰余を求める計算を逐次繰り返すと、剰余が 0 になった時の除数が a と b との最大公約数となる。

明示的に記述された最古のアルゴリズムとしても知られ、紀元前300年頃に記されたユークリッドの『原論』第 7 巻、命題 1 から 3 がそれである。

ユークリッドの互除法 - Wikipedia

⇧  う~ん...、言葉にするとなんだかなぁ~な感じなんですが、

www.yukisako.xyz

⇧  上記サイト様の図が分かりやすかったので、流用させていただきました。

ということらしいっす。 

なんか、再帰処理でイケそうなロジックですかね~と思っていたところ、

qiita.com

⇧  上記サイト様によりますと、イケるらしいです。

 

ユークリッドの互除法は、視覚的に捉えると、アハ!体験的に、エウレカ!ってなる感じですかね。

 

  

Javaユークリッドの互除法

んでは、Java で実装してみますか~。

qiita.com

⇧  上記サイト様を写経させていただきました。

Eclipseで適当に、Javaプロジェクトを作成し、クラスも作成。

f:id:ts0818:20190720120338p:plain

ソースはこんな感じで。
 

package main;

import java.math.BigInteger;
import java.util.stream.Stream;

public class Euclidean {

  public static void main(String[] args) {
    // 最大公約数を求めたい、数
    BigInteger[] bigIntArr = {
        BigInteger.valueOf(290021904), 
        BigInteger.valueOf(927964716), 
        BigInteger.valueOf(826824516), 
        BigInteger.valueOf(817140688)
    };
    // 実際の処理と結果
    System.out.println(gcd(bigIntArr));
  }
  
  public static BigInteger gcd(BigInteger[] arr) {
    return Stream.of(arr)
    .reduce(BigInteger::gcd)
    .orElse(BigInteger.ZERO);
  }
}
    

で動かしてみる。

f:id:ts0818:20190720120202p:plain

f:id:ts0818:20190720120120p:plain

よく分からんけど、StreamAPIの reduce メソッドと、orElse メソッドの組み合わせで再帰処理のようなことを行っている?らしいと思う。

というわけで、数学的な知識が欲しいな~と常に思う今日この頃です。

今回はこのへんで。