我寫了這個代碼生成平方根N.
的連分數但是，當N = 139
輸出應該{11,1,3,1,3,7,1,1,2,11,2,1,1,7,3,1,3,1,22}
雖然我的代碼給我的序列失敗394條款...其中前幾個條款是正確的，但當它達到22時，它給出12！生成連分數的平方根
有人可以幫助我嗎？
vector <int> f;
int B;double A;
A = sqrt(N*1.0);
B = floor(A);
f.push_back(B);
while (B != 2 * f[0])) {
A = 1.0/(A - B);
B =floor(A);
f.push_back(B);
}
f.push_back(B);
根本問題是，您無法準確地將非方形的平方根表示爲浮點數。
如果ξ被精確值和x近似（其被認爲是仍然相當好，從而尤其floor(ξ) = a = floor(x)仍然成立），則連分數算法的下一步驟之後的差是
ξ' - x' = 1/(ξ - a) - 1/(x - a) = (x - ξ)/((ξ - a)*(x - a)) ≈ (x - ξ)/(ξ - a)^2
因此我們看到，在每一步中，近似值和實際值之間的差值的絕對值增加，因爲0 < ξ - a < 1。每當發生大的部分商（ξ - a接近於0）時，差異增加很大的因數。一旦（差異的絕對值）等於或大於1，下一個計算得到的部分商被保證是錯誤的，但很可能第一個錯誤的部分商出現得更早。
Charlesmentioned近似與原始逼近n正確的數字，你可以計算連續分數約n部分商。這是一個很好的經驗法則，但正如我們所看到的，任何大的部分商都會花費更多的精度，從而減少可獲得的部分商的數量，並且偶爾會在更早的時候得到錯誤的部分商。
√139的情況是一個相對較長的週期和一些大的部分商，所以在這個週期完成之前出現第一個錯誤計算的部分商並不奇怪（我很驚訝它沒有' t更早發生）。
使用浮點運算，沒有辦法阻止這種情況。
但是對於二次感應的情況，我們可以通過僅使用整數算術來避免這個問題。假設你要計算的
ξ = (√D + P)/Q
其中Q分D - P²和D > 1是不是一個完美的正方形（如果整除條件不滿足，你可以用P*Q和Q代之以D與D*Q²，P連分數擴展Q²;你的情況是P = 0, Q = 1，在那裏它平凡滿意）。將完整商品寫爲
ξ_k = (√D + P_k)/Q_k (with ξ_0 = ξ, P_0 = P, Q_0 = Q)
並且表示部分商a_k。然後
ξ_k - a_k = (√D - (a_k*Q_k - P_k))/Q_k
，並與P_{k+1} = a_k*Q_k - P_k，
ξ_{k+1} = 1/(ξ_k - a_k) = Q_k/(√D - P_{k+1}) = (√D + P_{k+1})/[(D - P_{k+1}^2)/Q_k],
所以Q_{k+1} = (D - P_{k+1}^2)/Q_k —因爲P_{k+1}^2 - P_k^2是Q_k的倍數，通過感應Q_{k+1}是整數，並且Q_{k+1}劃分D - P_{k+1}^2。
的實數ξ的持續分數展開是週期性的，當且僅當ξ是二次清音，並且期間結束時在上述算法中，第一對(P_k, Q_k)重複。純平方根的情況特別簡單，當k > 0的第一個Q_k = 1和P_k, Q_k總是非負時，該時段完成。
隨着R = floor(√D)，部分商可以如
a_k = floor((R + P_k)/Q_k)
被計算，以便對上述算法的代碼變得
std::vector<unsigned long> sqrtCF(unsigned long D) {
// sqrt(D) may be slightly off for large D.
// If large D are expected, a correction for R is needed.
unsigned long R = floor(sqrt(D));
std::vector<unsigned long> f;
f.push_back(R);
if (R*R == D) {
// Oops, a square
return f;
}
unsigned long a = R, P = 0, Q = 1;
do {
P = a*Q - P;
Q = (D - P*P)/Q;
a = (R + P)/Q;
f.push_back(a);
}while(Q != 1);
return f;
}
這就容易計算的（例如）√7981持續餾分具有周期長度爲182.
非常感謝。這真的很有幫助。但是你能否給我提供一個紙質鏈接或者一些描述CF算法的內容，並加以深入的解釋 –
這些描述（不同深度）在或多或少與「數論導論」足夠相似的書中都有描述。根據我自己的經驗，我可以推薦經典的Hardy/Wright，Hua Loo Keng的書，還有一個告誡 - Don Redmond的書。 （需要注意的是，至少在我閱讀的版本中，雷蒙德的書中有很多排版錯誤，例如「13·27」出現爲「1327」，10平方等於102等，這經常令人不快，除此之外，這是一本非常不錯的書，並且比其他兩本更加廣泛。） –
偉大的解決方案。你能解釋一下爲什麼a =（R + P）/ Q？我不太明白。 – Confuse
我用你的電子表格算法中，我得到12爲好，我想你一定在你的算法中犯了一個錯誤，我嘗試了253倍的值，和B沒有達到它的最終值。
你可以嘗試解釋一下算法應該做什麼以及它如何工作？
我想我得到了你的算法，你在你的問題中犯了一個錯誤，應該是12.爲了將來的參考，算法可以在這個頁面找到http://en.wikipedia.org/wiki/Continued_fraction，它很容易出現十進制/數值計算問題如果反向值非常接近你試圖圍繞的整數。
在Excel下執行原型時，我無法重現3.245的wiki頁面示例，因爲在某些時候Floor（）將數字設置爲3而不是4，因此需要進行一些邊界檢查以檢查準確性...
在這種情況下，你可能要添加迭代的最大數，用於檢查退出條件的公差（退出條件應該是A等於BTW B）
罪魁禍首」不是個t floor。罪魁禍首是計算A= 1.0/(A - B);挖掘更深入，罪魁禍首是您的計算機用來表示實數的IEEE浮點機制。減法和加法失去精度。反覆減法，因爲你的算法反覆做了失去精度。
當你計算連續分數項{11,1,3,1,3,7,1,1,2,11,2}時，你的IEEE的浮點值A只有6而不是十五分之一或十六分之一。當你到達{11,1,3,1,3,7,1,1,2,11,2,1,1,7,3,1,3,1}你的A值是純垃圾。它失去了所有的精確度。
對於n個連續分數項，可以從一個具有n位精度的數字中提取出一個良好的第一個近似值（僅適用於基數爲10的巧合）。正如你所指出的那樣，如果你試圖採取更多措施，你會得到垃圾。 – Charles
數學中的sqrt函數並不精確。您可以使用sympy而不是任意高精度。這是一個非常簡單的代碼來計算連分數爲包含在sympy任何平方根或號碼：
from __future__ import division #only needed when working in Python 2.x
import sympy as sp
p=sp.N(sp.sqrt(139), 5000)
n=2000
x=range(n+1)
a=range(n)
x[0]=p
for i in xrange(n):
a[i] = int(x[i])
x[i+1]=1/(x[i]-a[i])
print a[i],
我你的電話號碼的精度設置爲5000，然後計算出2000連分數係數在此示例代碼。
是的，這個算法適用於一般情況，但正如Daniel Fischer的答案所顯示的那樣，可以確定二次數的精確週期性連續分數，而不需要採用任意的精確算術。當然，如果你想評估持續分數到高精度，那麼你確實需要比標準雙精度更好的東西。順便說一句，對於標記爲C++的問題，可能沒有太多意見，因爲你的代碼不使用任何Python「技巧」，所以任何閱讀此頁面的人都應該相當清楚。 –
如果有人試圖解決這個問題，這是一個沒有整數的語言，這裏是從JavaScript適應接受的答案代碼。
注意兩個~~（樓層操作員）已被添加。
export const squareRootContinuedFraction = D =>{
let R = ~~Math.sqrt(D);
let f = [];
f.push(R);
if (R*R === D) {
return f;
}
let a = R, P = 0, Q = 1;
do {
P = a*Q - P;
Q = ~~((D - P *P)/Q);
a = ~~((R + P)/Q);
f.push(a);
} while (Q != 1);
return f;
};
A和B的類型是什麼？ –
@PaulR A是雙B是int –
我的答案在這裏可能會有所幫助。它生成並打印出任意「double」的連續分數。 – Mysticial