FC2ブログ

# ペル方程式 Pell's Equation
# 引数 平方数でない整数 ($N)
# 戻り値 ペル方程式の最小の解 (@PellsEquation)
sub PELLSEQUATION{
my ($N) = @_;
my @PellsEquation = ();
my $Constant = 1;
my $IntSqrtN = int(sqrt($N));
my $Quotient = $IntSqrtN;
my ($PrevX, $X, $NextX) = (1, $IntSqrtN, 0);
my ($PrevY, $Y, $NextY) = (0, 1, 0);
my $P = 0;
my $Q = 1;

# 平方数でない整数の確認
if((int($N) <= 0) || ($N != int($N)) || (($IntSqrtN * $IntSqrtN) == $N)){
return 0;
}

# 計算
do{
# 値
$P = ($Quotient * $Q) - $P;
$Q = ($N - ($P * $P)) / $Q;
# 商の整数部
$Quotient = int(($IntSqrtN + $P) / $Q);
# 解
$NextX = $Quotient * $X + $PrevX;
$NextY = $Quotient * $Y + $PrevY;

# 漸化式
($PrevX, $X) = ($X, $NextX);
($PrevY, $Y) = ($Y, $NextY);
} while($Q != $Constant);

# ペル方程式 Pell's Equation
@PellsEquation = ($PrevX, $PrevY);

return @PellsEquation;
}


参考URL
ペル方程式 - Wikipedia
ペル方程式
2章 Pell方程式と連分数展開
8章 連分数とPell方程式
ペル方程式の最小解 - 高精度計算サイト

一言
PELLSEQUATION(61) = (29718, 3805)
Wikipedia では (61) = (1766319049, 226153980)が最小解である。
(29718, 3805)を利用しないと(1766319049, 226153980)は出せないのかな?
オンライン コンパイラ/インタプリタ
テクニカル分析
プロフィール

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

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

検索フォーム


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