草庐IT

c++ - 在 C++ 中计算 10 的整数幂比 pow() 更快吗？

coder 2023-05-02 原文

我知道 2 的幂可以使用 < 运算符来实现。="" 10的幂呢？像="" 10^5？有没有比="" c++="" 中的="" pow(10,5)="" 更快的方法？这是一个非常简单的手动计算。但是由于数字的二进制表示，计算机似乎并不容易......让我们假设我只对整数幂="" 10^n="" 感兴趣，其中="" n="" 是整数。="">

最佳答案

类似这样的:

int quick_pow10(int n)
{
    static int pow10[10] = {
        1, 10, 100, 1000, 10000, 
        100000, 1000000, 10000000, 100000000, 1000000000
    };

    return pow10[n]; 
}

显然，对于 long long 可以做同样的事情。

这应该比任何竞争方法快几倍。然而，如果你有很多基数，它是非常有限的(尽管随着基数的增加值的数量会急剧下降)，所以如果没有大量的组合，它仍然是可行的。

作为比较:

#include <iostream>
#include <cstdlib>
#include <cmath>

static int quick_pow10(int n)
{
    static int pow10[10] = {
        1, 10, 100, 1000, 10000, 
        100000, 1000000, 10000000, 100000000, 1000000000
    };

    return pow10[n]; 
}

static int integer_pow(int x, int n)
{
    int r = 1;
    while (n--)
       r *= x;

    return r; 
}

static int opt_int_pow(int n)
{
    int r = 1;
    const int x = 10;
    while (n)
    {
        if (n & 1) 
        {
           r *= x;
           n--;
        }
        else
        {
            r *= x * x;
            n -= 2;
        }
    }

    return r; 
}


int main(int argc, char **argv)
{
    long long sum = 0;
    int n = strtol(argv[1], 0, 0);
    const long outer_loops = 1000000000;

    if (argv[2][0] == 'a')
    {
        for(long i = 0; i < outer_loops / n; i++)
        {
            for(int j = 1; j < n+1; j++)
            {
                sum += quick_pow10(n);
            }
        }
    }
    if (argv[2][0] == 'b')
    {
        for(long i = 0; i < outer_loops / n; i++)
        {
            for(int j = 1; j < n+1; j++)
            {
                sum += integer_pow(10,n);
            }
        }
    }

    if (argv[2][0] == 'c')
    {
        for(long i = 0; i < outer_loops / n; i++)
        {
            for(int j = 1; j < n+1; j++)
            {
                sum += opt_int_pow(n);
            }
        }
    }

    std::cout << "sum=" << sum << std::endl;
    return 0;
}

用g++ 4.6.3编译，使用-Wall -O2 -std=c++0x，得到如下结果:

$ g++ -Wall -O2 -std=c++0x pow.cpp
$ time ./a.out 8 a
sum=100000000000000000

real    0m0.124s
user    0m0.119s
sys 0m0.004s
$ time ./a.out 8 b
sum=100000000000000000

real    0m7.502s
user    0m7.482s
sys 0m0.003s

$ time ./a.out 8 c
sum=100000000000000000

real    0m6.098s
user    0m6.077s
sys 0m0.002s

(我也有一个使用 pow 的选项，但是我第一次尝试时花了 1m22.56s，所以当我决定优化循环变体时我删除了它)

关于c++ - 在 C++ 中计算 10 的整数幂比 pow() 更快吗？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/18581560/

amp中计intcodepowc++numerical

有关c++ - 在 C++ 中计算 10 的整数幂比 pow() 更快吗？的更多相关文章

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

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

  2. 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服务器更新战俘

  3. 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.你能做的最好的事情是:

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

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

  5. ruby - 在 Ruby 中将整数格式化为固定长度的字符串 - 2

    有没有一种简单的方法可以将给定的整数格式化为具有固定长度和前导零的字符串？#convertnumberstostringsoffixedlength3[1,12,123,1234].map{|e|???}=>["001","012","123","234"]我找到了解决方案，但也许还有更聪明的方法。format('%03d',e)[-3..-1] 最佳答案 如何使用%1000而不是进行字符串操作来获取最后三位数字？[1,12,123,1234].map{|e|format('%03d',e%1000)}更新:根据theTinMan的

  6. ruby - 如何搜索、递增和替换 Ruby 字符串中的整数子字符串？ - 2

    我有很多这样的文档:foo_1foo_2foo_3bar_1foo_4...我想通过获取foo_[X]的所有实例并将它们中的每一个替换为foo_[X+1]来转换它们。在这个例子中:foo_2foo_3foo_4bar_1foo_5...我可以用gsub和一个block来做到这一点吗？如果不是，最干净的方法是什么？我真的在寻找一个优雅的解决方案，因为我总是可以暴力破解它，但我觉得有一些正则表达式技巧值得学习。 最佳答案 我(完全)不懂Ruby，但类似这样的东西应该可以工作:"foo_1foo_2".gsub(/(foo_)(\d+)/

  7. 由于 libgmp.10.dylib 的问题，Ruby 2.2.0 无法运行 - 2

    我刚刚安装了带有RVM的Ruby2.2.0，并尝试使用它得到了这个:$rvmuse2.2.0--defaultUsing/Users/brandon/.rvm/gems/ruby-2.2.0dyld:Librarynotloaded:/usr/local/lib/libgmp.10.dylibReferencedfrom:/Users/brandon/.rvm/rubies/ruby-2.2.0/bin/rubyReason:Incompatiblelibraryversion:rubyrequiresversion13.0.0orlater,butlibgmp.10.dylibpro

  8. ruby - 如何在 Ruby 中将负整数转换为二进制 - 2

    问题1:我无法通过以下方式找到将负整数转换为二进制的方法。我应该像这样转换它。-3=>"11111111111111111111111111111101"我在下面试过:sprintf('%b',-3)=>"..101"#..appearsanddoesnotshow111111bit.-3.to_s(2)=>"-11"#Thisjustadds-tothebinaryofthepositiveinteger3.问题2:有趣的是，如果我使用在线转换器，它告诉我-3的二进制是“0010110100110011”。"11111111111111111111111111111101"和"001

  9. arrays - Ruby 数组 += vs 推送 - 2

    我有一个数组数组，想将元素附加到子数组。+=做我想做的，但我想了解为什么push不做。我期望的行为(并与+=一起工作):b=Array.new(3,[])b[0]+=["apple"]b[1]+=["orange"]b[2]+=["frog"]b=>[["苹果"],["橙子"],["Frog"]]通过推送，我将推送的元素附加到每个子数组(为什么？):a=Array.new(3,[])a[0].push("apple")a[1].push("orange")a[2].push("frog")a=>[[“苹果”、“橙子”、“Frog”]、[“苹果”、“橙子”、“Frog”]、[“苹果”、“

  10. ruby - 如何更快地解决 project euler #21？ - 2

    原始问题Letd(n)bedefinedasthesumofproperdivisorsofn(numberslessthannwhichdivideevenlyinton).Ifd(a)=bandd(b)=a,whereab,thenaandbareanamicablepairandeachofaandbarecalledamicablenumbers.Forexample,theproperdivisorsof220are1,2,4,5,10,11,20,22,44,55and110;therefored(220)=284.Theproperdivisorsof284are1,2,

随机推荐