メメメモモ

プログラミング、筋トレ、ゲーム、etc

ユークリッドの互除法

ユークリッドの互除法perlで書いてみました。

use strict;
use warnings;

{
    gcd(160,48);
}

sub gcd {
    my ($x, $y) = @_;

    my $c;

    while ($x > 0 && $y > 0) {
        if ($y > $x) {
            $c = $x;
            $x = $y;
            $y = $c;
        }

        print "$x, $y\n";

        $c = $y;

        $x = $x - $y;
        $y = $c;
    }
}


表示結果は下記のようになり、2つの自然数の最大公約数が求まります。

160, 48
112, 48
64, 48
48, 16
32, 16
16, 16


引き算で求まっていくのが不思議です。ということで、どういう感じで求まっていくのかを確かめてみました。


 x_{0} = 160 = 10 * 16
 y_{0} = 48 = 3 * 16


 x_{0} - y_{0} = (10 - 3) * 16 = 7 * 16 = x_{1}
 y_{0} = 3 * 16 = y_{1}


 x_{1} - y_{1} = (7 - 3) * 16 = 4 * 16 = x_{2}
 y_{1} = 3 * 16 = y_{2}


 x_{2} - y_{2} = (4 - 3) * 16 = 1 * 16 = y_{3}
 y_{2} = 3 * 16 = x_{3}


 x_{3} - y_{3} = (3 - 1) * 16 = 2 * 16 = x_{4}
 y_{3} = 1 * 16 = y_{4}


 x_{4} - y_{4} = (2 - 1) * 16 = 1 * 16


という感じになりますね。