「近似」最大公約數

Question

假設你有一個是一個共同的數量大約倍數浮點數的列表，例如

2.468，3.700，6.1699

這是大約的倍數1.234。你如何描述這個「近似gcd」，你將如何繼續計算或估計它？

與我回答this question嚴格相關。

Answer 1

將您的測量值顯示爲最小值的倍數。因此你的清單變成1.00000,1.49919,2.49996。這些值的小數部分將非常接近1/N，因爲N的某個值取決於最低值與基頻的接近程度。我建議循環增加N直到找到足夠精確的匹配。在這種情況下，對於N = 1（即假設X = 2.468是您的基本頻率），您會發現0.3333的標準偏差（三個值中的兩個是0.5 * X * 1），這是不可接受的高。對於N = 2（即假設2.468/2是您的基本頻率），您會發現幾乎爲零的標準偏差（所有三個值都在X/2倍數的.001內），因此2.468/2是您的近似值GCD。

我的計劃中存在的主要缺陷是，當最低的測量結果是最準確的時候效果最好，但情況可能並非如此。這可以通過多次執行整個操作來減輕，每次丟棄測量列表中的最低值，然後使用每次通過的結果列表來確定更精確的結果。改進結果的另一種方法是調整GCD以最小化GCD的整數倍與測量值之間的標準偏差。

Answer 2

有趣的問題...不容易。

我想我會看的樣本值的比率：

• 3.700/2.468 = 1.499 ...
• 6.1699/2.468 = 2.4999 ...
• 6.1699/3.700 = 1.6675 ...

然後我會在這些結果中尋找一個簡單的整數比例。

• 1.499〜= 3/2
• 2.4999〜= 5/2
• 1.6675〜= 5/3

我沒有追事情的經過，但某處沿線，你決定1：1000或者其他東西的誤差足夠好，並且你回溯到基本的近似GCD。

Answer 3

我假設你所有的數字都是整數值的倍數。對於我的其餘解釋，A將表示您正在嘗試查找的「根」頻率，B將是您必須開始使用的數字的數組。

你要做的是表面上類似於linear regression。您正試圖找到一個線性模型y = mx + b，該模型使線性模型與一組數據之間的平均距離最小化。在你的情況下，b = 0，m是根頻率，y代表給定的值。最大的問題是自變量X沒有明確給出。我們唯一知道的X是它的所有成員必須是整數。

你的第一個任務是試圖確定這些獨立變量。目前我能想到的最好的方法是假定給定的頻率具有幾乎連續的索引（x_1=x_0+n）。所以B_0/B_1=(x_0)/(x_0+n)給予（希望）小整數n。然後，您可以利用事實x_0 = n/(B_1-B_0)，從n = 1開始，並持續調整它，直到k-rnd（k）在特定閾值內。在有了x_0（初始索引）之後，可以近似根音頻率（A = B_0/x_0）。然後您可以通過查找x_n = rnd(B_n/A)來近似其他索引。這種方法不是很健壯，如果數據錯誤很大，可能會失敗。

如果您想要更好地逼近根頻率A，那麼可以使用線性迴歸將線性模型的誤差減至最小，此時您已具有相應的因變量。最簡單的方法是使用最小二乘法擬合。 Wolfram's Mathworld對此問題有深入的數學處理，但fairly simple explanation可以用一些Google搜索找到。

Answer 4

你可以用更小的東西，然後0.01（或少數您選擇的）運行歐幾里得的GCD算法是一個僞0。您的號碼：

3.700 = 1 * 2.468 + 1.232, 
2.468 = 2 * 1.232 + 0.004. 

所以前兩個數字的僞公因數1.232。現在你拿你的最後一個號碼的這個gcd：

6.1699 = 5 * 1.232 + 0.0099. 

所以1.232是僞gcd，而多重點是2,3,5。爲了改善這一結果，您可以對數據點進行線性迴歸：

(2,2.468), (3,3.7), (5,6.1699). 

斜率是改進的僞gcd。注意：第一部分是算法在數值上不穩定 - 如果你從非常髒的數據開始，那麼你遇到了麻煩。

Answer 5

這讓我想起尋找實數有理數的近似值的問題。該標準的技術是一個持續的分式展開：

def rationalizations(x): 
    assert 0 <= x 
    ix = int(x) 
    yield ix, 1 
    if x == ix: return 
    for numer, denom in rationalizations(1.0/(x-ix)): 
     yield denom + ix * numer, numer 

我們可以直接將此喬納森萊弗勒的和SPARR的做法：

>>> a, b, c = 2.468, 3.700, 6.1699 
>>> b/a, c/a 
(1.4991896272285252, 2.4999594813614263) 
>>> list(itertools.islice(rationalizations(b/a), 3)) 
[(1, 1), (3, 2), (925, 617)] 
>>> list(itertools.islice(rationalizations(c/a), 3)) 
[(2, 1), (5, 2), (30847, 12339)] 

摘每個序列的第一個足夠好的近似。 （這裏是3/2和5/2）或者直接比較3.0/2.0到1.499189 ...，你會注意到比925/617使用大得多的整數比3/2，使得3/2成爲一個很好的地方停止。

它應該沒有太大關係，你劃分的數字。 （例如，使用a/b和c/b可以得到2/3和5/3。）一旦有了整數比率，就可以使用shsmurfy的線性迴歸來優化隱含的基本估計。每個人都贏了！

Answer 6

我見過並使用過自己的解決方案是選擇一些常數，比如1000，用這個常數乘以所有數字，將它們四捨五入到整數，使用標準算法找到這些整數的GCD，然後將結果乘以所述常數（1000）。常數越大，精度越高。

Answer 7

這是shsmurfy的解決方案的reformulaiton當你先驗選擇3個正公差（E1，E2，E3）
的問題是再尋找最小的正整數（N1，N2，N3），從而最大根頻率f這樣的：

f1 = n1*f +/- e1 
f2 = n2*f +/- e2 
f3 = n3*f +/- e3 

我們假設0 < = F1 < = F2 < = F3
如果我們解決N1，那麼我們得到這些關係：

f is in interval I1=[(f1-e1)/n1 , (f1+e1)/n1] 
n2 is in interval I2=[n1*(f2-e2)/(f1+e1) , n1*(f2+e2)/(f1-e1)] 
n3 is in interval I3=[n1*(f3-e3)/(f1+e1) , n1*(f3+e3)/(f1-e1)] 

我們從n1 = 1開始，然後遞增n1直到間隔I2和I3包含一個整數 - 即floor(I2min) different from floor(I2max)與I3相同
然後我們選擇區間I2中的最小整數n2和區間I3中的最小整數n3。

假設浮點錯誤的正態分佈，根頻率f的最可能的估計是一個最小化

J = (f1/n1 - f)^2 + (f2/n2 - f)^2 + (f3/n3 - f)^2 

即

f = (f1/n1 + f2/n2 + f3/n3)/3 

如果有幾個整數N2，N3中的間隔I2，I3我們也可以選擇使殘基最小化的對

min(J)*3/2=(f1/n1)^2+(f2/n2)^2+(f3/n3)^2-(f1/n1)*(f2/n2)-(f1/n1)*(f3/n3)-(f2/n2)*(f3/n3) 

另一個變體可能是繼續迭代並嘗試最小化另一個標準，如min（J（n1））* n1，直到f降到某個頻率以下（n1達到上限）...

Answer 8

我發現此問題在MathStackExchange（here和here）中尋找我的答案。

我只管理（但）如果你有選擇的數量減少來衡量給出諧波頻率（以下聲音/音樂術語）列表的根本frequecy，這可能是有用的吸引力和是可行的計算每個人的吸引力，然後選擇最合適的。從我在MSE問題

Ç& P（有格式更漂亮）：

• 是訴列表{V_1，V_2，...，v_n}，從低階到更高
• mean_sin（v，x）= sum（sin（2 * pi * v_i/x），其中i in {1，...，n}）/ n
• mean_cos（v，x）= sum （v，x）= 1 - sqrt（mean_sin（v，x）^ 2）+（mean_cos（v，x）^ 2） （v，x）-1）^ 2）/ 2，其產生nu mber在[0,1]區間內。

目標是找到最大化上訴012的x，即。以下是您的示例[2.468,3.700，6.1699]的（gcd_appeal）圖表，其中您發現最佳GCD爲x = 1。2337899957639993