私はこの質問に完全に行き詰まっているので、助けを探しています。
バイナリ GCD やユークリッド GCD などの基本的な GCD 計算アルゴリズムについては、誰もが知っていると思います。このようなメソッドを実装して 2 つの単精度数を計算することは問題ではありません。実際には、それはほんの数ストロークです。
このメソッドを (C 言語で) 多倍精度数 (10^5 ビット以上) 用に実装する必要があります。利用可能な GNU ライブラリ (GNU MP、MPFR、MPIR) がいくつかあり、それらには多倍精度数を定義し、それらに対してアクションを実行する手段があります。これは、「手足」とも呼ばれる単精度部分のカップルとしてメモリに格納された 1 つの多倍精度数のように見えます。
gcd(a, b) を見つけるためにいくつかのメソッドが実装されていますが、実際には、私のニーズに合わせて使用するのは困難です。a と b に正確に 2 つのリムが含まれる場合にのみ使用される GCD 計算のバイナリ メソッド。min(a,b) に 630 以上のリムが含まれる場合などに使用される HGCD メソッド。a と b の任意の長さで使用するためにこれらのメソッドをどのように拡張できるかを理解するのは難しいと思います。また、GNU ライブラリの異なるバージョンには、異なるバージョンと GCD アルゴリズムのメソッドが含まれていることもわかりました。
質問:バイナリ GCD アルゴリズムを「リム」に関して任意の長さの多倍精度整数で動作させることが可能かどうかを調べたいのですが、可能であれば、C でそれを実装する方法やアイデアを得るために.誰かがそれを実装する方法やコード部分を持っていますか?
その問題を解決するためのアドバイスやその他の解決策を検討したいと思います。
誰かが見てみるなら、これは (a = b = 2 limbs) の GNU MP バイナリ GCD メソッドの一部です。
/* Use binary algorithm to compute G <-- GCD (U, V) for usize, vsize == 2.
Both U and V must be odd. */
static inline mp_size_t
gcd_2 (mp_ptr gp, mp_srcptr up, mp_srcptr vp)
{
printf("gcd_2 invoked\n");
mp_limb_t u0, u1, v0, v1;
mp_size_t gn;
u0 = up[0];
u1 = up[1];
v0 = vp[0];
v1 = vp[1];
ASSERT (u0 & 1);
ASSERT (v0 & 1);
/* Check for u0 != v0 needed to ensure that argument to
* count_trailing_zeros is non-zero. */
while (u1 != v1 && u0 != v0)
{
unsigned long int r;
if (u1 > v1)
{
sub_ddmmss (u1, u0, u1, u0, v1, v0);
count_trailing_zeros (r, u0);
u0 = ((u1 << (GMP_NUMB_BITS - r)) & GMP_NUMB_MASK) | (u0 >> r);
u1 >>= r;
}
else /* u1 < v1. */
{
sub_ddmmss (v1, v0, v1, v0, u1, u0);
count_trailing_zeros (r, v0);
v0 = ((v1 << (GMP_NUMB_BITS - r)) & GMP_NUMB_MASK) | (v0 >> r);
v1 >>= r;
}
}
gp[0] = u0, gp[1] = u1, gn = 1 + (u1 != 0);
/* If U == V == GCD, done. Otherwise, compute GCD (V, |U - V|). */
if (u1 == v1 && u0 == v0)
return gn;
v0 = (u0 == v0) ? ((u1 > v1) ? u1-v1 : v1-u1) : ((u0 > v0) ? u0-v0 : v0-u0);
gp[0] = mpn_gcd_1 (gp, gn, v0);
return 1;
}