不定方程式
１．概要
０でない整数Ａ,Ｂ,Ｃを係数とする２変数の一次方程式の整数解Ｘ,Ｙを求める
ＡＸ＋ＢＹ＝Ｃ
◆主な機能
ユークリッドの互除法で最大公約数gcd(Ａ,Ｂ)を計算する過程で得られる情報Kiを
記憶しておいて、それを用いてＸを計算する方法がある。
この場合、Kiの記憶領域とgcd計算のループとは別のループが必要になる。
再帰アルゴリズムを使えばループが１つに見えるが、関数の呼出しと戻りの過程でKiを記憶している。
◆特徴
本アルゴリズムの最大の特徴は、gcdが得られた時点で変数Ｘの値が同時に得られることである。
Kiを記憶しておく必要は無く、ループがgcdを計算する１回だけで済む。
ではそのメリットは何かと言われると特筆すべきものは無いかもしれない。
しかしながら、Kiの記憶が不要であり、１回のループで済む点でよりエレガントに見える。
詳細なアルゴリズム説明はダウンロードファイルの中にあります。
ＡＸ＋ＢＹ＝Ｃ
◆主な機能
ユークリッドの互除法で最大公約数gcd(Ａ,Ｂ)を計算する過程で得られる情報Kiを
記憶しておいて、それを用いてＸを計算する方法がある。
この場合、Kiの記憶領域とgcd計算のループとは別のループが必要になる。
再帰アルゴリズムを使えばループが１つに見えるが、関数の呼出しと戻りの過程でKiを記憶している。
◆特徴
本アルゴリズムの最大の特徴は、gcdが得られた時点で変数Ｘの値が同時に得られることである。
Kiを記憶しておく必要は無く、ループがgcdを計算する１回だけで済む。
ではそのメリットは何かと言われると特筆すべきものは無いかもしれない。
しかしながら、Kiの記憶が不要であり、１回のループで済む点でよりエレガントに見える。
詳細なアルゴリズム説明はダウンロードファイルの中にあります。
２．アルゴリズム概要
◆不定方程式
ＡＸ＋ＢＹ＝Ｃ (1)
ＡＸ＝ＢＹ＋Ｃ (2)
(1)(2)の解のＸは同じ値である。(2)を書き直して
ＡＸ＋Ｂ(-Ｙ)＝Ｃ
とすれば、解のＹの符号が反転するだけであることがわかる。
どちらのタイプでも本アルゴリズムでＸは計算できる。
(1)(2)のＹは計算式だけ変えれば簡単に求まる。例えば(2)の場合は以下となる。
Ｙ＝(ＡＸーＣ)／Ｂ
◆ユークリッドの互除法による漸化式
(1)でN1＝Ａ, N0＝Ｂ, X0＝Ｘ, X1＝Ｙと書き直すと
Ni＊Xi-1＋Ni-1＊Xi＝Ｃ (i＝1) (3)
となる。Ni-1をNiで割った商をKi、剰余をNi+1とする。すなわち
Ki＝[Ni-1／Ni] 商 []は切り捨て (4)
Ni+1＝Ni-1−Ki＊Ni 剰余 |Ni+1|＜|Ni| (5)
(5)を使って(3)からNi-1を消去して整理すると(6)式を得る。
Ni+1＊Xi＋Ni＊(Xi-1＋Ki＊Xi)＝Ｃ (6)
ここでXi+1を次式(7)とすると、(6)は(8)式になる。
Xi+1＝(Xi-1＋Ki＊Xi) (7)
Ni+1＊Xi＋Ni＊Xi+1＝Ｃ (8)
(8)は(3)と同じ形をしている。つまりi→i+1としたものである。
同様の操作を繰り返して行くと(5)は最大公約数gcdを求めるユークリッドの互除法と同じなので
いずれNg-1をNgで割った剰余Ng+1が０になり、その時のNgが最大公約数gcd(N0,N1)となる。
Ng+1＝Ng-1ーKg＊Ng (9)
Ng+1＝０ (10)
Ng＝gcd(N0,N1) (11)
この時(8)式は(12)となり、(12)式に(10)(11)を用いればXg+1が求まる。
Ng+1＊Xg＋Ng＊Xg+1＝Ｃ (12)
Xg+1＝Ｃ／gcd(N0,N1) (13)
(13)のXg+1が整数にならなければ不定方程式(1)に整数解は無い
(12)式でXgの係数Ng+1は０なので、Xgは任意の整数でよいからとりあえず
Xg＝０ (14)
とする
◆漸化式による計算
(7)を変形すると(15)が得られる
Xi-1＝(Xi+1−Ki＊Xi) i＝g,g-1,..,1 (15)
(15)と初期条件(13)(14)からi＝g,g-1,..,1の順にX0(式(1)のＸ)を計算することができる。
Kiはgcd(Ａ,Ｂ)の計算過程で(4)により決まる。
このままのループ計算ではKi(i=g,g-1,..,1)の記憶域が必要であり、
最大公約数を求めるユークリッドの互除法とは逆方向のループの計算をすることになる。
本アルゴリズムでは計算グラフを導入し計算方法を工夫して、Kiの記憶を不要にすると共に
最大公約数を求めるループで同時にＸを計算する方法を提案している。
詳細はダウンロードファイル内の説明と下記サンプルソースを参照してください。
ＡＸ＋ＢＹ＝Ｃ (1)
ＡＸ＝ＢＹ＋Ｃ (2)
(1)(2)の解のＸは同じ値である。(2)を書き直して
ＡＸ＋Ｂ(-Ｙ)＝Ｃ
とすれば、解のＹの符号が反転するだけであることがわかる。
どちらのタイプでも本アルゴリズムでＸは計算できる。
(1)(2)のＹは計算式だけ変えれば簡単に求まる。例えば(2)の場合は以下となる。
Ｙ＝(ＡＸーＣ)／Ｂ
◆ユークリッドの互除法による漸化式
(1)でN1＝Ａ, N0＝Ｂ, X0＝Ｘ, X1＝Ｙと書き直すと
Ni＊Xi-1＋Ni-1＊Xi＝Ｃ (i＝1) (3)
となる。Ni-1をNiで割った商をKi、剰余をNi+1とする。すなわち
Ki＝[Ni-1／Ni] 商 []は切り捨て (4)
Ni+1＝Ni-1−Ki＊Ni 剰余 |Ni+1|＜|Ni| (5)
(5)を使って(3)からNi-1を消去して整理すると(6)式を得る。
Ni+1＊Xi＋Ni＊(Xi-1＋Ki＊Xi)＝Ｃ (6)
ここでXi+1を次式(7)とすると、(6)は(8)式になる。
Xi+1＝(Xi-1＋Ki＊Xi) (7)
Ni+1＊Xi＋Ni＊Xi+1＝Ｃ (8)
(8)は(3)と同じ形をしている。つまりi→i+1としたものである。
同様の操作を繰り返して行くと(5)は最大公約数gcdを求めるユークリッドの互除法と同じなので
いずれNg-1をNgで割った剰余Ng+1が０になり、その時のNgが最大公約数gcd(N0,N1)となる。
Ng+1＝Ng-1ーKg＊Ng (9)
Ng+1＝０ (10)
Ng＝gcd(N0,N1) (11)
この時(8)式は(12)となり、(12)式に(10)(11)を用いればXg+1が求まる。
Ng+1＊Xg＋Ng＊Xg+1＝Ｃ (12)
Xg+1＝Ｃ／gcd(N0,N1) (13)
(13)のXg+1が整数にならなければ不定方程式(1)に整数解は無い
(12)式でXgの係数Ng+1は０なので、Xgは任意の整数でよいからとりあえず
Xg＝０ (14)
とする
◆漸化式による計算
(7)を変形すると(15)が得られる
Xi-1＝(Xi+1−Ki＊Xi) i＝g,g-1,..,1 (15)
(15)と初期条件(13)(14)からi＝g,g-1,..,1の順にX0(式(1)のＸ)を計算することができる。
Kiはgcd(Ａ,Ｂ)の計算過程で(4)により決まる。
このままのループ計算ではKi(i=g,g-1,..,1)の記憶域が必要であり、
最大公約数を求めるユークリッドの互除法とは逆方向のループの計算をすることになる。
本アルゴリズムでは計算グラフを導入し計算方法を工夫して、Kiの記憶を不要にすると共に
最大公約数を求めるループで同時にＸを計算する方法を提案している。
詳細はダウンロードファイル内の説明と下記サンプルソースを参照してください。
３．サンプルソース
このソースは1987年にLSIメモリのテストで使うスキャン方式の評価の際に開発したものです。
FORTRANからＣ言語に書き換えましたが、外部仕様は当時のままになっています。
/* ID_huteiEqu LSIメモリスキャン回数 不定方程式s + p * k = q * n + e を解く
****************************************************************************/
int huteiEqu( /* 戻り値 0:正常 -1:引数異常 1:整数解なし */
int n, /* i メモリサイズ0 < n */
int k, /* i スキップサイズ */
int s, /* i 開始位置 */
int e, /* i 終端位置 */
int *p, /* o 移動回数 0＜*p＜|n/gcd| */
int *q, /* o スライド回数 */
int *gcd) /* o 最大公約数(n, k)。 負の場合がある */
{
int c1, c2, n1, n2, x, y, z;
if( n == 0 || k == 0 ) {*p = *q = *gcd = -1; return -1;}
/* 初期化 */
c1 = 0; c2 = e-s;
n1 = n; n2 = k;
while( n2 != 0 ) { // ユークリッドの互除法のループ
x = n1 / n2;
y = n1 - x * n2; n1 = n2; n2 = y;
z = c1 - x * c2; c1 = c2; c2 = z;
}
*gcd = n1;
if( ((e - s) % n1) != 0 ) {*p = *q = -1; return 1;}
*p = (c1 / n1) % (n / n1);
if( *p < 0) *p += abs(n / n1); // *p＞0を保証する必要が無いなら不要
*q = (s - e + k * (*p)) / n;
return(0);
}
FORTRANからＣ言語に書き換えましたが、外部仕様は当時のままになっています。
/* ID_huteiEqu LSIメモリスキャン回数 不定方程式s + p * k = q * n + e を解く
****************************************************************************/
int huteiEqu( /* 戻り値 0:正常 -1:引数異常 1:整数解なし */
int n, /* i メモリサイズ0 < n */
int k, /* i スキップサイズ */
int s, /* i 開始位置 */
int e, /* i 終端位置 */
int *p, /* o 移動回数 0＜*p＜|n/gcd| */
int *q, /* o スライド回数 */
int *gcd) /* o 最大公約数(n, k)。 負の場合がある */
{
int c1, c2, n1, n2, x, y, z;
if( n == 0 || k == 0 ) {*p = *q = *gcd = -1; return -1;}
/* 初期化 */
c1 = 0; c2 = e-s;
n1 = n; n2 = k;
while( n2 != 0 ) { // ユークリッドの互除法のループ
x = n1 / n2;
y = n1 - x * n2; n1 = n2; n2 = y;
z = c1 - x * c2; c1 = c2; c2 = z;
}
*gcd = n1;
if( ((e - s) % n1) != 0 ) {*p = *q = -1; return 1;}
*p = (c1 / n1) % (n / n1);
if( *p < 0) *p += abs(n / n1); // *p＞0を保証する必要が無いなら不要
*q = (s - e + k * (*p)) / n;
return(0);
}
４．使用方法
◆ダウンロード（ダウンロードのページからもダウンロードできます）
sample04.zip 5 KB (4,456 バイト) ソース
４．１ インストール
ダウンロードしたファイルを、任意のディレクトリに解凍します。
テスト用main()とhuteiEqu()のソースとアルゴリズム説明書のテキストファイルみです。
プロジェクトファイルはありません
４．２ アンインストール
インストール時に作成したディレクトリごとファイルを削除します。
４．３ 使用方法
テスト用main()を無効にしてhuteiEqu()を呼び出してください
sample04.zip 5 KB (4,456 バイト) ソース
４．１ インストール
ダウンロードしたファイルを、任意のディレクトリに解凍します。
テスト用main()とhuteiEqu()のソースとアルゴリズム説明書のテキストファイルみです。
プロジェクトファイルはありません
４．２ アンインストール
インストール時に作成したディレクトリごとファイルを削除します。
４．３ 使用方法
テスト用main()を無効にしてhuteiEqu()を呼び出してください
５．開発環境
ANSI C++