浮動小数点数のリストがあるとします。約共通の量の倍数、例えば
2.468、3.700、6.1699
これらはすべて 1.234 の倍数です。この「近似 GCD」をどのように特徴づけ、どのように計算または推定しますか?
私の回答と厳密に関連してこの質問。
ベストアンサー1
ユークリッドの gcd アルゴリズムは、0.01 より小さい数値 (または任意の小さな数値) を擬似 0 として実行できます。数値は次のようになります。
3.700 = 1 * 2.468 + 1.232,
2.468 = 2 * 1.232 + 0.004.
したがって、最初の 2 つの数値の疑似最大公約数は 1.232 です。次に、最後の数値とのこの最大公約数を計算します。
6.1699 = 5 * 1.232 + 0.0099.
したがって、1.232 は疑似最大公約数であり、倍数は 2、3、5 です。この結果を改善するには、データ ポイントに対して線形回帰を実行します。
(2,2.468), (3,3.7), (5,6.1699).
傾きは改良された疑似最大公約数です。
注意: このアルゴリズムの最初の部分は数値的に不安定です。非常に汚れたデータから始めると、問題が発生します。