草庐IT

c++ - 生成平方根的连分数

coder 2023-11-14 原文

我编写了这段代码来生成平方根 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);

最佳答案

根本问题是您不能将非平方的平方根精确地表示为 float 。

如果ξ是精确值，x近似值(这应该还是相当不错的，所以特别是 floor(ξ) = a = floor(x) 仍然成立)，那么在下一步连分式算法之后的差异是

ξ' - x' = 1/(ξ - a) - 1/(x - a) = (x - ξ) / ((ξ - a)*(x - a)) ≈ (x - ξ) / (ξ - a)^2

因此我们看到，在每一步中，近似值与实际值之间的差值的绝对值都会增加，因为 0 < ξ - a < 1 .每次出现较大的偏商(ξ - a 接近于 0)时，差值都会增加一个很大的因子。一旦差(的绝对值)为 1 或更大，下一个计算的偏商肯定是错误的，但很可能第一个错误的偏商出现得更早。

Charles mentioned与 n 的原始近似值的近似值正确的数字，你可以计算大约n连分数的偏商。这是一个很好的经验法则，但正如我们所见，任何大的偏商都需要更高的精度，从而减少可获得的偏商的数量，有时您会更早地得到错误的偏商。

案例√139是一个相对较长的周期，有几个大的偏商，所以第一个错误计算的偏商出现在周期完成之前就不足为奇了(我很惊讶它没有出现得更早)。

使用浮点运算，无法避免这种情况。

但是对于二次方的情况，我们可以通过仅使用整数运算来避免该问题。假设您要计算的连分式展开

ξ = (√D + P) / Q

哪里Q划分 D - P²和 D > 1不是一个完美的正方形(如果不满足整除条件，您可以将 D 替换为 D*Q² ，将 P 替换为 P*Q 并将 Q 替换为 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 .

实数的连分数展开ξ是周期性的当且仅当ξ是二次surd，当上述算法中第一对(P_k, Q_k)时，周期结束重复。纯平方根的情况特别简单，第一个Q_k = 1时结束对于 k > 0 , 和 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。

关于c++ - 生成平方根的连分数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/12182701/

amp43codepresectionc++mathsquare-root

有关c++ - 生成平方根的连分数的更多相关文章

  1. ruby - 使用 RubyZip 生成 ZIP 文件时设置压缩级别 - 2

    我有一个Ruby程序，它使用rubyzip压缩XML文件的目录树。gem。我的问题是文件开始变得很重，我想提高压缩级别，因为压缩时间不是问题。我在rubyzipdocumentation中找不到一种为创建的ZIP文件指定压缩级别的方法。有人知道如何更改此设置吗？是否有另一个允许指定压缩级别的Ruby库？ 最佳答案 这是我通过查看ruby​​zip内部创建的代码。level=Zlib::BEST_COMPRESSIONZip::ZipOutputStream.open(zip_file)do|zip|Dir.glob("**/*")d

  2. ruby-on-rails - 如何优雅地重启 thin + nginx？ - 2

    我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？ 最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server

  3. ruby - 在 jRuby 中使用 'fork' 生成进程的替代方案？ - 2

    在MRIRuby中我可以这样做:deftransferinternal_server=self.init_serverpid=forkdointernal_server.runend#Maketheserverprocessrunindependently.Process.detach(pid)internal_client=self.init_client#Dootherstuffwithconnectingtointernal_server...internal_client.post('somedata')ensure#KillserverProcess.kill('KILL',

  4. ruby - 如何使用 Ruby aws/s3 Gem 生成安全 URL 以从 s3 下载文件 - 2

    我正在编写一个小脚本来定位aws存储桶中的特定文件，并创建一个临时验证的url以发送给同事。(理想情况下，这将创建类似于在控制台上右键单击存储桶中的文件并复制链接地址的结果)。我研究过回形针，它似乎不符合这个标准，但我可能只是不知道它的全部功能。我尝试了以下方法:defauthenticated_url(file_name,bucket)AWS::S3::S3Object.url_for(file_name,bucket,:secure=>true,:expires=>20*60)end产生这种类型的结果:...-1.amazonaws.com/file_path/file.zip.A

  5. ruby-on-rails - Ruby on Rails - 为文本区域和图片生成列 - 2

    我是Rails的新手，所以请原谅简单的问题。我正在为一家公司创建一个网站。那家公司想在网站上展示它的客户。我想让客户自己管理这个。我正在为“客户”生成一个表格，我想要的三列是:公司名称、公司描述和Logo。对于名称，我使用的是name:string但不确定如何在脚本/生成脚手架终端命令中最好地创建描述列(因为我打算将其设置为文本区域)和图片。我怀疑描述(我想成为一个文本区域)应该仍然是描述:字符串，然后以实际形式进行调整。不确定如何处理图片字段。那么……说来话长:我在脚手架命令中输入什么来生成描述和图片列？ 最佳答案 对于“文本”数

  6. ruby-on-rails - 如何生成传递一些自定义参数的 `link_to` URL？ - 2

    我正在使用RubyonRails3.0.9，我想生成一个传递一些自定义参数的link_toURL。也就是说，有一个articles_path(www.my_web_site_name.com/articles)我想生成如下内容:link_to'Samplelinktitle',...#HereIshouldimplementthecode#=>'http://www.my_web_site_name.com/articles?param1=value1¶m2=value2&...我如何编写link_to语句“alàRubyonRailsWay”以实现该目的？如果我想通过传递一些

  7. ruby-on-rails - 如何在 Rails 3 中创建自定义脚手架生成器？ - 2

    有这些railscast。http://railscasts.com/episodes/218-making-generators-in-rails-3有了这个，你就会知道如何创建样式表和脚手架生成器。http://railscasts.com/episodes/216-generators-in-rails-3通过这个，您可以了解如何添加一些文件来修改脚手架View。我想把两者结合起来。我想创建一个生成器，它也可以创建脚手架View。有点像RyanBates漂亮的生成器或web_app_themegem(https://github.com/pilu/web-app-theme)。我

  8. 报告回顾丨模型进化狂飙，DetectGPT能否识别最新模型生成结果？ - 2

    导读语言模型给我们的生产生活带来了极大便利，但同时不少人也利用他们从事作弊工作。如何规避这些难辨真伪的文字所产生的负面影响也成为一大难题。在3月9日智源Live第33期活动「DetectGPT：判断文本是否为机器生成的工具」中，主讲人Eric为我们讲解了DetectGPT工作背后的思路——一种基于概率曲率检测的用于检测模型生成文本的工具，它可以帮助我们更好地分辨文章的来源和可信度，对保护信息真实、防止欺诈等方面具有重要意义。本次报告主要围绕其功能，实现和效果等展开。（文末点击“阅读原文”，查看活动回放。）Ericmitchell斯坦福大学计算机系四年级博士生，由ChelseaFinn和Chri

  9. ruby - 使用 `+=` 和 `send` 方法 - 2

    如何将send与+=一起使用？a=20;a.send"+=",10undefinedmethod`+='for20:Fixnuma=20;a+=10=>30 最佳答案 恐怕你不能。+=不是方法，而是语法糖。参见http://www.ruby-doc.org/docs/ProgrammingRuby/html/tut_expressions.html它说Incommonwithmanyotherlanguages,Rubyhasasyntacticshortcut:a=a+2maybewrittenasa+=2.你能做的最好的事情是:

  10. ruby - 如何计算 Liquid 中的变量 +1 - 2

    我对如何计算通过{%assignvar=0%}赋值的变量加一完全感到困惑。这应该是最简单的任务。到目前为止，这是我尝试过的:{%assignamount=0%}{%forvariantinproduct.variants%}{%assignamount=amount+1%}{%endfor%}Amount:{{amount}}结果总是0。也许我忽略了一些明显的东西。也许有更好的方法。我想要存档的只是获取运行的迭代次数。 最佳答案 因为{{incrementamount}}将输出您的变量值并且不会影响{%assign%}定义的变量，我

随机推荐