c++ - 通过修改的exp最快的pow()替换。当已经计算出较低的幂时，通过平方

coder 2024-02-05 原文

编辑:

目标 :
通过重用公共(public)变量的功效计算中预先计算/缓存的功效，生成一种无处不在的方法来推导自定义功效函数，其性能优于内置pow(double, uint)。

已经完成的工作:
我已经派生了一个比内置函数快40％的函数，但这是一个蛮力的手工派生函数-我想要一种为任意uint幂自动生成这样的幂函数块的方法。

知道

要获得最佳的自定义pow(double, uint)，您需要了解一些信息。对于这个问题，已知(澄清)是:

幂将是一个整数。

可以知道的最大功率(N_MAX)。

可以(重新)使用的预先计算的功效是已知的
在编译时(例如，在我的示例中r2，r4和r6)。

可以假定平方r2始终被计算出来，无论
其他预先计算的功效。

解决方案要求

最佳解决方案是可以接受的，该解决方案需要一个单独的程序来编写case查找表或预处理器逻辑以生成此类表，但是，使用手握的权力手动生成(即，从蛮力派生)查找表的非最佳解决方案将是 Not Acceptable 。接受(因为我已经拥有了，并在我的示例中展示……想法是逃避这一点)。

可能的解决方案路线

作为建议，您知道N_MAX和一组预先计算的B(在我的示例中为B={2,4,6})的幂。您可以在单独的程序中或在预处理器中生成Sq(Bi, x的所有平方的表)<= n_max="">. You can use this to form a basis set

, which you then search somehow to determine the least number of terms that can be summed to produce an arbitrary exponent of

n >> 1 , where n <=>

理论背景

我正式相信下面的方法是通过平方的幂的修改版本:

http://en.wikipedia.org/wiki/Exponentiation_by_squaring

....这利用了一定的低阶幂已经被预先计算的事实，因此它通过平方使最佳乘法集从 Vanilla 指数移到平方(我假设是pow(double, int)使用)。

但是，通过使用存储的小功率中间体而不是简单的exp，可以节省大量资金。在r2上按正方形。

理论性能

例如，在这种情况下，对于一组对象n=14....。通过权力给予

double r4 = Sq(r2), r14=Sq(r4)*r4*r2; //4 op.

...这需要 4个FP乘积 .....但使用r2和r6我们有

double r14=Sq(r6)*r2; //2 op.

.... 2个FP乘法 ....换句话说，从平方的“哑”指数到修改后的exp。使用常见的指数预缓存逐个平方，我已经将乘法的计算成本降低了50％... ...至少直到考虑到内存成本为止。

REAL PERFORMANCE

使用我当前的方法(与gcc -O3一起编译)，我得到 35.1秒。 可以运行我的程序一百万个周期，而(没有其他修改) 56.6 s 使用内置的int pow(double, int) ....因此几乎是理论上的加速。

在这一点上，您可能正在摸索着如何将一条指令行上的乘法减少50％可以实现约40％的加速。但基本上，每行此代码行被称为1,000次以上，是迄今为止整个程序中评估最多/最昂贵的代码行。因此，该程序对于此块中的少量优化/改进显得非常敏感。

原始帖子和示例代码

我需要替换pow(double, int)函数，因为我已经计算出了6阶幂项，并保存了2、4阶幂中间体，所有这些都可以用于减少第二个pow调用中的乘法，该调用使用相同的double基数。

更具体地说，在我的C++代码中，我有一段性能关键的计算代码段，其中我将3D点之间的距离的倒数提高到了6阶和n阶。例如。:

double distSq = CalcDist(p1,p2), r2 = a/distSq, r6 = r2 * r2 * r2;
results += m*(pow(sqrt(r2), n) - r6);

其中m和a是与拟合方程式相关的常数，而n是任意幂。

效率略高的形式是:

double distSq = CalcDist(p1,p2), r2 = a/distSq, r6 = r2 * r2 * r2;
results += m*(pow(r2, n)*(n&0x1?sqrt(r2):1.0) - r6);

但是，这也不是最佳的。我发现要快得多的是拥有一个自定义pow函数，该函数使用r2，r4和r6的倍数，无论如何我都必须对第二项进行计算。

例如。:

double distSq = CalcDist(p1,p2), r2 = a/distSq, r4 = r2 * r2, r6 = r4 * r2;
results += m*(POW(r2, r4, r6 n) - r6);

函数内部:

double POW(double r2, double r4, double r6, uint n)
{
   double results = (n&0x1 : sqrt(r2) : 1.0);
   n >>= 1;
   switch (n)
   {
     case 1:
     ....
     case 12:
        Sq(Sq(r6));

   }
   return result;
}

好在我的功能在初步测试中很快出现。坏消息是它不是很普遍，而且很长，因为我需要从case到int左右的8权力的50语句(将来可能甚至更高)。此外，每种情况下，我都必须检查并尝试不同的组合以通过蛮力推导找到r2，r4和r6的组合产生的乘积最少

是否有人对于pow(double, int)替换有更普遍的解决方案，该解决方案使用基数的预先计算出的幂来减少必要的乘法运算的数量，和/或是否具有普遍的理论，即如何确定理想组合来为任意n产生最少的乘法和一些预先计算的倍数？

最佳答案

这是一种有点类似于DP的算法，它将为您提供给定n和可用功率x^i的最小乘法数，以及通过回溯的最佳策略。对于每个可能的指数n，将一对(minimum number of multiplications to get here, type of multiplication that gets you there)关联在一起，对于第二个数字，只需编写i或特殊符号S进行平方。

您显然从1 -> (0, /)开始。

给定n -> (m_n, Action_m)，如果n+i ->小于以前计算得出的(m_n + 1, i)的最小移动次数，则将m_n + 1设置为n+i。同样，如果比以前可能的解决方案更好，请设置2n -> (m_n + 1, S)。

该算法以O(n_max * #available powers)大致为您提供了最佳策略。我并不是说算法本身是最佳效率的，但是“动态”使用它当然没有任何意义。仅当您具有合理的n_max(在您的情况下，肯定为100)并且是存储策略的有效方法时，此功能才有用。

要考虑的两个想法:

(1)在进行基准测试之前，我不相信通过平方(当然，这在很大程度上取决于可用功率)是否可以大大提高标准exp的性能。

(2)这种策略的数值错误行为(以及平方的exp)与pow(double, double)完全不同。

关于c++ - 通过修改的exp最快的pow()替换。当已经计算出较低的幂时，通过平方，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/18945317/

amp 最快 code br strong c++math optimization pow

有关c++ - 通过修改的exp最快的pow()替换。当已经计算出较低的幂时，通过平方的更多相关文章

ruby - 通过 rvm 升级 rubygems 的问题 - 2
尝试通过RVM将RubyGems升级到版本1.8.10并出现此错误:$rvmrubygemslatestRemovingoldRubygemsfiles...Installingrubygems-1.8.10forruby-1.9.2-p180...ERROR:Errorrunning'GEM_PATH="/Users/foo/.rvm/gems/ruby-1.9.2-p180:/Users/foo/.rvm/gems/ruby-1.9.2-p180@global:/Users/foo/.rvm/gems/ruby-1.9.2-p180:/Users/foo/.rvm/gems/rub
ruby-on-rails - 如何优雅地重启 thin + nginx？ - 2
我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server
ruby - 通过 erb 模板输出 ruby 数组 - 2
我正在使用puppet为ruby程序提供一组常量。我需要提供一组主机名，我的程序将对其进行迭代。在我之前使用的bash脚本中，我只是将它作为一个puppet变量hosts=>"host1,host2"我将其提供给bash脚本作为HOSTS=显然这对ruby不太适用——我需要它的格式hosts=["host1","host2"]自从phosts和putsmy_array.inspect提供输出["host1","host2"]我希望使用其中之一。不幸的是，我终其一生都无法弄清楚如何让它发挥作用。我尝试了以下各项:我发现某处他们指出我需要在函数调用前放置“function_”……这
ruby 正则表达式 - 如何替换字符串中匹配项的第 n 个实例 - 2
在我的应用程序中，我需要能够找到所有数字子字符串，然后扫描每个子字符串，找到第一个匹配范围(例如5到15之间)的子字符串，并将该实例替换为另一个字符串“X”。我的测试字符串s="1foo100bar10gee1"我的初始模式是1个或多个数字的任何字符串，例如，re=Regexp.new(/\d+/)matches=s.scan(re)给出["1","100","10","1"]如果我想用“X”替换第N个匹配项，并且只替换第N个匹配项，我该怎么做？例如，如果我想替换第三个匹配项“10”(匹配项[2])，我不能只说s[matches[2]]="X"因为它做了两次替换“1fooX0barXg
ruby - 通过 ruby 进程共享变量 - 2
我正在编写一个gem，我必须在其中fork两个启动两个webrick服务器的进程。我想通过基类的类方法启动这个服务器，因为应该只有这两个服务器在运行，而不是多个。在运行时，我想调用这两个服务器上的一些方法来更改变量。我的问题是，我无法通过基类的类方法访问fork的实例变量。此外，我不能在我的基类中使用线程，因为在幕后我正在使用另一个不是线程安全的库。所以我必须将每个服务器派生到它自己的进程。我用类变量试过了，比如@@server。但是当我试图通过基类访问这个变量时，它是nil。我读到在Ruby中不可能在分支之间共享类变量，对吗？那么，还有其他解决办法吗？我考虑过使用单例，但我不确定这是
ruby - 通过 RVM (OSX Mountain Lion) 安装 Ruby 2.0.0-p247 时遇到问题 - 2
我的最终目标是安装当前版本的RubyonRails。我在OSXMountainLion上运行。到目前为止，这是我的过程:已安装的RVM$\curl-Lhttps://get.rvm.io|bash-sstable检查已知(我假设已批准)安装$rvmlistknown我看到当前的稳定版本可用[ruby-]2.0.0[-p247]输入命令安装$rvminstall2.0.0-p247注意:我也试过这些安装命令$rvminstallruby-2.0.0-p247$rvminstallruby=2.0.0-p247我很快就无处可去了。结果:$rvminstall2.0.0-p247Search
ruby-on-rails - 项目升级后 Pow 不会更改 ruby 版本 - 2
我在我的Rails项目中使用Pow和powifygem。现在我尝试升级我的ruby版本(从1.9.3到2.0.0，我使用RVM)当我切换ruby版本、安装所有gem依赖项时，我通过运行railss并访问localhost:3000确保该应用程序正常运行以前，我通过使用pow访问http://my_app.dev来浏览我的应用程序。升级后，由于错误Bundler::RubyVersionMismatch:YourRubyversionis1.9.3,butyourGemfilespecified2.0.0，此url不起作用我尝试过的:重新创建pow应用程序重启pow服务器更新战俘
ruby-on-rails - Enumerator.new 如何处理已通过的 block ？ - 2
我在理解Enumerator.new方法的工作原理时遇到了一些困难。假设文档中的示例:fib=Enumerator.newdo|y|a=b=1loopdoy[1,1,2,3,5,8,13,21,34,55]循环中断条件在哪里，它如何知道循环应该迭代多少次(因为它没有任何明确的中断条件并且看起来像无限循环)？最佳答案 Enumerator使用Fibers在内部。您的示例等效于:require'fiber'fiber=Fiber.newdoa=b=1loopdoFiber.yieldaa,b=b,a+bendend10.times.m
ruby-on-rails - 在 ruby 中使用 gsub 函数替换单词 - 2
我正在尝试用ruby中的gsub函数替换字符串中的某些单词，但有时效果很好，在某些情况下会出现此错误？这种格式有什么问题吗NoMethodError(undefinedmethod`gsub!'fornil:NilClass):模型.rbclassTest"replacethisID1",WAY=>"replacethisID2andID3",DELTA=>"replacethisID4"}end另一个模型.rbclassCheck 最佳答案啊，我找到了!gsub!是一个非常奇怪的方法。首先，它替换了字符串，所以它实际上修改了
ruby - 寻找通过阅读代码确定编程语言的ruby gem？ - 2
几个月前，我读了一篇关于rubygem的博客文章，它可以通过阅读代码本身来确定编程语言。对于我的生活，我不记得博客或gem的名称。谷歌搜索“ruby编程语言猜测”及其变体也无济于事。有人碰巧知道相关gem的名称吗？最佳答案是这个吗:http://github.com/chrislo/sourceclassifier/tree/master 关于ruby-寻找通过阅读代码确定编程语言的rubygem？，我们在StackOverflow上找到一个类似的问题：

c++ - 通过修改的exp最快的pow()替换。当已经计算出较低的幂时，通过平方

有关c++ - 通过修改的exp最快的pow()替换。当已经计算出较低的幂时，通过平方的更多相关文章

随机推荐