草庐IT

c++ - 有理函数级数展开的最佳算法

coder 2024-02-10 原文

我需要用 C++ 编写函数代码，它可以有效地找到给定有理函数 (P(x)/Q(x)) 的泰勒级数系数。

函数参数将是多项式的幂(分母和分母相等)，两个具有多项式系数和展开项数的数组。

我的想法如下。 考虑身份

P(x) / Q(x) = R(x) + ...

其中 R(x) 是一个多项式，其项数等于我需要找到的系数数。然后我可以将两边与 Q(x) 相乘并得到

P(x) = R(x) * Q(x)

R(x) * Q(x) - P(x) = 0

因此，所有系数都应为零。这是用 O(n^3) 算法求解的方程组。 O(n^3) 没有我想要的那么快。

有没有更快的算法？

我知道级数的系数满足线性递推关系。 这让我觉得 O(n) 算法是可能的。

最佳答案

我将要描述的算法在数学上由 formal power series 证明是合理的.每个具有泰勒级数的函数都有一个正式的幂级数。反之则不然，但如果我们用泰勒级数对函数进行运算并得到一个具有泰勒级数的函数，那么我们可以对形式幂级数进行相同的运算并得到相同的答案。

形式幂级数的长除法算法如long division您可能在学校学到的算法。我将在示例 (1 + 2 x)/(1 - x - x^2) 中对其进行演示，其系数等于 Lucas numbers .

分母必须有一个非零常数项。我们从写分子开始，它是第一个残差。

             --------
1 - x - x^2 ) 1 + 2 x

[ 我们将残差的最低阶项 (1) 除以分母的常数项 (1)，并将商放在最上面。

              1
             --------
1 - x - x^2 ) 1 + 2 x

现在我们将 1 - x - x^2 乘以 1 并从当前残差中减去它。

              1
             --------
1 - x - x^2 ) 1 + 2 x
              1 -   x - x^2
              -------------
                  3 x + x^2

再做一次。

              1 + 3 x
             --------
1 - x - x^2 ) 1 + 2 x
              1 -   x -   x^2
              ---------------
                  3 x +   x^2
                  3 x - 3 x^2 - 3 x^3
                  -------------------
                        4 x^2 + 3 x^3

再一次。

              1 + 3 x + 4 x^2
             ----------------
1 - x - x^2 ) 1 + 2 x
              1 -   x -   x^2
              ---------------
                  3 x +   x^2
                  3 x - 3 x^2 - 3 x^3
                  -------------------
                        4 x^2 + 3 x^3
                        4 x^2 - 4 x^3 - 4 x^4
                        ---------------------
                                7 x^3 + 4 x^4

再一次。

              1 + 3 x + 4 x^2 + 7 x^3
             ------------------------
1 - x - x^2 ) 1 + 2 x
              1 -   x -   x^2
              ---------------
                  3 x +   x^2
                  3 x - 3 x^2 - 3 x^3
                  -------------------
                        4 x^2 + 3 x^3
                        4 x^2 - 4 x^3 - 4 x^4
                        ---------------------
                                7 x^3 + 4 x^4
                                7 x^3 - 7 x^4 - 7 x^4
                                ---------------------
                                       11 x^4 + 7 x^5

单独的除法有点无聊，因为我使用了一个带前导 1 的除数，但是如果我使用了，比方说，2 - 2 x - 2 x^2，则商中的所有系数将除以 2。

关于c++ - 有理函数级数展开的最佳算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/23092541/

有理ampcodepresectionc++algorithmtaylor-series

有关c++ - 有理函数级数展开的最佳算法的更多相关文章

  1. ruby-on-rails - 使用 Ruby on Rails 进行自动化测试 - 最佳实践 - 2

    很好奇，就使用ruby​​onrails自动化单元测试而言，你们正在做什么？您是否创建了一个脚本来在cron中运行rake作业并将结果邮寄给您？git中的预提交Hook？只是手动调用？我完全理解测试，但想知道在错误发生之前捕获错误的最佳实践是什么。让我们理所当然地认为测试本身是完美无缺的，并且可以正常工作。下一步是什么以确保他们在正确的时间将可能有害的结果传达给您？ 最佳答案 不确定您到底想听什么，但是有几个级别的自动代码库控制:在处理某项功能时，您可以使用类似autotest的内容获得关于哪些有效，哪些无效的即时反馈。要确保您的提

  2. ruby - 解析 RDFa、微数据等的最佳方式是什么，使用统一的模式/词汇(例如 schema.org)存储和显示信息 - 2

    我主要使用Ruby来执行此操作，但到目前为止我的攻击计划如下:使用gemsrdf、rdf-rdfa和rdf-microdata或mida来解析给定任何URI的数据。我认为最好映射到像schema.org这样的统一模式，例如使用这个yaml文件，它试图描述数据词汇表和opengraph到schema.org之间的转换:#SchemaXtoschema.orgconversion#data-vocabularyDV:name:namestreet-address:streetAddressregion:addressRegionlocality:addressLocalityphoto:i

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

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

  4. ruby - 在没有 sass 引擎的情况下使用 sass 颜色函数 - 2

    我想在一个没有Sass引擎的类中使用Sass颜色函数。我已经在项目中使用了sassgem，所以我认为搭载会像以下一样简单:classRectangleincludeSass::Script::FunctionsdefcolorSass::Script::Color.new([0x82,0x39,0x06])enddefrender#hamlengineexecutedwithcontextofself#sothatwithintemlateicouldcall#%stop{offset:'0%',stop:{color:lighten(color)}}endend更新:参见上面的#re

  5. ruby-on-rails - 在 ruby​​ 中使用 gsub 函数替换单词 - 2

    我正在尝试用ruby​​中的gsub函数替换字符串中的某些单词，但有时效果很好，在某些情况下会出现此错误？这种格式有什么问题吗NoMethodError(undefinedmethod`gsub!'fornil:NilClass):模型.rbclassTest"replacethisID1",WAY=>"replacethisID2andID3",DELTA=>"replacethisID4"}end另一个模型.rbclassCheck 最佳答案 啊，我找到了!gsub!是一个非常奇怪的方法。首先，它替换了字符串，所以它实际上修改了

  6. ruby - 在 Ruby 中有条件地定义函数 - 2

    我有一些代码在几个不同的位置之一运行:作为具有调试输出的命令行工具，作为不接受任何输出的更大程序的一部分，以及在Rails环境中。有时我需要根据代码的位置对代码进行细微的更改，我意识到以下样式似乎可行:print"Testingnestedfunctionsdefined\n"CLI=trueifCLIdeftest_printprint"CommandLineVersion\n"endelsedeftest_printprint"ReleaseVersion\n"endendtest_print()这导致:TestingnestedfunctionsdefinedCommandLin

  7. 区块链之加解密算法&数字证书 - 2

    目录一.加解密算法数字签名对称加密DES(DataEncryptionStandard)3DES(TripleDES)AES(AdvancedEncryptionStandard)RSA加密法DSA(DigitalSignatureAlgorithm)ECC(EllipticCurvesCryptography)非对称加密签名与加密过程非对称加密的应用对称加密与非对称加密的结合二.数字证书图解一.加解密算法加密简单而言就是通过一种算法将明文信息转换成密文信息，信息的的接收方能够通过密钥对密文信息进行解密获得明文信息的过程。根据加解密的密钥是否相同，算法可以分为对称加密、非对称加密、对称加密和非

  8. ruby - 在 Ruby 中按名称传递函数 - 2

    如何在Ruby中按名称传递函数？(我使用Ruby才几个小时，所以我还在想办法。)nums=[1,2,3,4]#Thisworks,butismoreverbosethanI'dlikenums.eachdo|i|putsiend#InJS,Icouldjustdosomethinglike:#nums.forEach(console.log)#InF#,itwouldbesomethinglike:#List.iternums(printf"%A")#InRuby,IwishIcoulddosomethinglike:nums.eachputs在Ruby中能不能做到类似的简洁？我可以只

  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. C51单片机——实现用独立按键控制LED亮灭（调用函数篇） - 2

    说在前面这部分我本来是合为一篇来写的，因为目的是一样的，都是通过独立按键来控制LED闪灭本质上是起到开关的作用，即调用函数和中断函数。但是写一篇太累了，我还是决定分为两篇写，这篇是调用函数篇。在本篇中你主要看到这些东西！！！1.调用函数的方法（主要讲语法和格式）2.独立按键如何控制LED亮灭3.程序中的一些细节（软件消抖等）1.调用函数的方法思路还是比较清晰地，就是通过按下按键来控制LED闪灭，即每按下一次，LED取反一次。重要的是，把按键与LED联系在一起。我打算用K1来作为开关，看了一下开发板原理图，K1连接的是单片机的P31口，当按下K1时，P31是与GND相连的，也就是说，当我按下去时

随机推荐