FC2ブログ

# 拡張版ユークリッドの互除法 Extended Euclidean Algorithm
# 引数 自然数 自然数 ($a, $b)
# 戻り値 最大公約数 ($ExtendedEuclideanAlgorithm)
sub EXTENDEDEUCLIDEANALGORITHM{
my ($a, $b) = @_;
my $ExtendedEuclideanAlgorithm = 0;
my $A = int(abs($a));
my $B = int(abs($b));
my ($PrevX, $PrevY, $PrevRemainder) = (1, 0, $A);
my ($X, $Y, $Remainder) = (0, 1, $B);
my ($NextX, $NextY, $NextRemainder) = (0, 0, 0);
my $Quotient = 0;

# 値の確認
if(($A == 0) || ($B == 0)){
return 0;
}

($A, $B) = ($B, $A) if($A < $B);

# 計算
while($Remainder != 0){
# 商の整数部
$Quotient = int($PrevRemainder / $Remainder);
# 値
$NextX = $PrevX - ($X * $Quotient);
$NextY = $PrevY - ($Y * $Quotient);
# 余り
$NextRemainder = $PrevRemainder - ($Remainder * $Quotient);

# 次
($PrevX, $PrevY, $PrevRemainder) = ($X, $Y, $Remainder);
($X, $Y, $Remainder) = ($NextX, $NextY, $NextRemainder);
}

# 拡張版ユークリッドの互除法 Extended Euclidean Algorithm
$ExtendedEuclideanAlgorithm = $PrevRemainder;

return $ExtendedEuclideanAlgorithm;
}


参考URL
ユークリッドの互除法<アルゴリズム<Web教材<木暮
Extended Euclidean algorithm - Wikipedia, the free encyclopedia
オンライン コンパイラ/インタプリタ
テクニカル分析
プロフィール

Author:雨宮
Firefoxを使用しているので気づかなかったけど、IE6でソースコードを上手くコピーできない

5/3
携帯用ならIE6でもソースコードをコピーできる
携帯用

検索フォーム


あわせて読みたいブログパーツ
一寸先は闇 RSS