为什么标准C++库中没有int int(int base,int exponent)？

Question

我觉得我必须无法找到它.有什么理由说c ++ pow函数没有为浮点数和双精度数以外的任何东西实现"幂"函数吗？

我知道实现是微不足道的,我只是觉得我正在做一个应该在标准库中的工作.强大的幂函数(即以某种一致,明确的方式处理溢出)编写起来并不好玩.

Answer 1

截止日期C++11,特殊情况被添加到电源功能套件(和其他功能)中.C++11 [c.math] /11在列出所有float/double/long double重载之后(我的重点和释义):

此外,还有额外的重载足以确保,如果对应于double参数的任何参数具有类型double或整数类型,则对应于double参数的所有参数都被有效地转换为double.

因此,基本上,整数参数将升级为双精度以执行操作.

在C++11(在询问您的问题之前)之前,不存在整数重载.

因为我既没有密切的关联创造者C,也不C++在他们创造的日(虽然我是比较旧的),也不是创建标准ANSI/ISO委员会的组成部分,这必然是我的一部分意见.我想认为这是明智的意见,但是,正如我的妻子会告诉你的那样(经常而且不需要太多的鼓励),我以前错了:-)

假设值得遵循.

我怀疑原来的ANSI C之前没有这个功能的原因是因为它完全没必要.首先,已经有一种非常好的方法来执行整数幂(使用双精度然后简单地转换回整数,在转换之前检查整数溢出和下溢).

其次,你必须要记住的另一件事是,它的原始意图C是作为系统编程语言,并且在该领域中浮点是否可取是值得怀疑的.

由于其初始用例之一是编写UNIX代码,因此浮点数几乎无用.C所基于的BCPL也没有使用权力(它根本没有浮点数,来自内存).

另外,一个完整的幂运算符可能是二元运算符而不是库调用.你不要添加两个整数,x = add (y, z)但要使用x = y + z- 部分语言而不是库.

第三,由于整体能力的实施相对微不足道,几乎可以肯定该语言的开发人员会更好地利用他们的时间提供更多有用的东西(参见下面关于机会成本的评论).

这也与原版有关C++.由于最初的实现实际上只是一个生成C代码的翻译器,因此它承载了许多属性C.它最初的意图是C-with-classes,而不是C-with-classes-plus-a-little-bit-of-math-stuff.

至于为什么以前从未添加到标准中C++11,你必须记住标准制定机构有特定的指导方针.例如,ANSI C专门负责编纂现有实践,而不是创建新语言.否则,他们可能会疯了,给我们阿达:-)

该标准的后续迭代也有具体的指导方针,可以在理论文件中找到(关于委员会为何做出某些决定的理由,而不是语言本身的理由).

例如,C99基本原理文件明确提出了两个C89限制可添加内容的指导原则:

• 保持语言小而简单.
  
• 只提供一种方法来进行操作.

指南(不一定是那些具体的指南)是针对各个工作组制定的,因此也限制了C++委员会(以及所有其他ISO组).

此外,标准制定机构认识到,每一项决策都有机会成本(一个经济术语,意味着你必须放弃做出的决定).例如,购买这台价值10,000美元的超级游戏机的机会成本与你的另一半约为六个月的亲切关系(或可能是所有关系).

Eric Gunnerson用他的-100分解释了这个问题,为什么事情并不总是添加到微软产品中 - 基本上一个功能在漏洞中开始100分,所以它必须增加相当多的价值才能被考虑.

换句话说,您是否愿意拥有一个完整的功率运算符(老实说,任何一半体面的编码器都可以在十分钟内完成)或多线程添加到标准中？对于我自己,我更喜欢使用后者,而不必考虑UNIX和Windows下的不同实现.

我还想看到成千上万的标准库(哈希,btree,红黑树,字典,任意地图等),但是,理论上说:

标准是实施者和程序员之间的条约.

标准组织的实施者数量远远超过程序员(或至少那些不了解机会成本的程序员)的数量.如果添加了所有这些内容,那么下一个标准C++就是C++215x并且可能会在三百年之后由编译器开发人员完全实现.

无论如何,这是我(相当庞大)对此事的想法.如果只根据数量而不是质量进行投票,我很快就会把其他所有人都赶出水面.谢谢收听 :-)

Answer 2

对于任何固定宽度的整数类型,无论如何,几乎所有可能的输入对都会溢出类型.标准化一个函数的用途是什么,它不能为绝大多数可能的输入提供有用的结果？

你几乎需要一个大整数类型才能使函数变得有用,并且大多数大整数库都提供了这个函数.

编辑:在对问题的评论中,static_rtti写道"大多数输入导致它溢出？对于exp和double pow也是如此,我没有看到有人在抱怨." 这是不正确的.

让我们放在一边exp,因为这不是重点(虽然它实际上会让我的情况变得更强),并专注于double pow(double x, double y).对于(x,y)对的哪一部分,此函数是否有用(即,不仅仅是上溢或下溢)？

我实际上只关注一小部分pow有意义的输入对,因为这足以证明我的观点:如果x为正且| y | <= 1,然后pow不上溢或下溢.这几乎占所有浮点对的四分之一(正好一半的非NaN浮点数是正数,只有不到一半的非NaN浮点数的数量小于1).显然,有很多其他输入对可以pow产生有用的结果,但我们已经确定它至少是所有输入的四分之一.

现在让我们看一下固定宽度(即非bignum)整数幂函数.它输入的部分不仅仅是溢出？为了最大化有意义的输入对的数量,应该对基数进行签名,并且指数是无符号的.假设基数和指数都是n位宽.我们可以轻松地获得有意义的输入部分:

• 如果指数为0或1,那么任何基数都是有意义的.
• 如果指数为2或更大,则没有大于2 ^(n/2)的基数产生有意义的结果.

因此,在2 ^(2n)个输入对中,小于2 ^(n + 1)+ 2 ^(3n/2)产生有意义的结果.如果我们看看最常见的用法是什么,32位整数,这意味着大约百分之一的输入对的1/1000的数量不会简单地溢出.

Answer 3

因为无论如何都无法表示int中的所有整数幂:

>>> print 2**-4
0.0625

Answer 4

这实际上是一个有趣的问题.我在讨论中没有找到的一个论点是参数的简单缺乏明显的返回值.让我们计算一下hypthetical int pow_int(int, int)函数可能失败的方式.

1. 溢出
2. 结果未定义 pow_int(0,0)
3. 结果无法表示 pow_int(2,-1)

该功能至少有2种故障模式.整数不能代表这些值,在这些情况下函数的行为需要由标准定义 - 程序员需要知道函数如何处理这些情况.

总体而言,将功能退出似乎是唯一明智的选择.程序员可以使用浮点版本,而不是可用的所有错误报告.

Answer 5

简短回答:

pow(x, n)对于哪里n是自然数的专门化通常对时间性能有用.但是标准库的通用pow()仍然可以很好地(令人惊讶地!)用于此目的,并且在标准C库中尽可能少地包含它是绝对关键的,因此它可以被制作为可移植且易于实现.另一方面,这并不能阻止它进入C++标准库或STL,我很确定没有人计划在某种嵌入式平台上使用它.

现在,为了答案很长.

pow(x, n)通过专注n于自然数,在许多情况下可以更快地制作.对于我编写的几乎每个程序,我都必须使用自己的函数实现(但我在C中编写了很多数学程序).专门的操作可以及时完成O(log(n)),但是当它n很小时,更简单的线性版本可以更快.以下是两者的实现:

    // Computes x^n, where n is a natural number.
    double pown(double x, unsigned n)
    {
        double y = 1;
        // n = 2*d + r. x^n = (x^2)^d * x^r.
        unsigned d = n >> 1;
        unsigned r = n & 1;
        double x_2_d = d == 0? 1 : pown(x*x, d);
        double x_r = r == 0? 1 : x;
        return x_2_d*x_r;
    }
    // The linear implementation.
    double pown_l(double x, unsigned n)
    {
        double y = 1;
        for (unsigned i = 0; i < n; i++)
            y *= x;
        return y;
    }

(我离开x了,返回值变为双倍,因为结果pow(double x, unsigned n)会尽可能多地适合双倍pow(double, double).)

(是的,pown是递归的,但是打破堆栈是绝对不可能的,因为最大堆栈大小将大致相等log_2(n)并且n是一个整数.如果n是64位整数,那么最大堆栈大小约为64. 没有硬件具有这样的极端内存限制,除了一些狡猾的PIC,硬件堆栈只能进行3到8个函数调用.)

至于表现,你会对花园品种pow(double, double)的能力感到惊讶.我在我5岁的IBM Thinkpad上测试了一亿次迭代,x等于迭代次数,n等于10.在这种情况下,pown_l赢了.glibc pow()用户占用12秒,用户时间为pown7.4秒,用户时间pown_l仅为6.5秒.所以这并不太令人惊讶.我们或多或少地期待这一点.

然后,我让它x保持不变(我将它设置为2.5),然后我n从0到19 循环一次.这一次,出乎意料的是,格里布pow赢了,并且发生了山体滑坡!用户只用了2.0秒.我pown花了9.6秒,pown_l花了12.2秒.这里发生了什么？我做了另一个测试来找出答案.

我做了同样的事情只有x相当于一百万.这一次,pown赢了9.6s.pown_l花了12.2秒,glibc pow花了16.3秒.现在,很清楚!glibc pow在x低时表现优于三,但在x高时表现最差.当x为高电平时,pown_l当执行最好n是低的,并且pown当执行最好x是高的.

所以这里有三种不同的算法,每种算法在适当的情况下都能比其他算法表现更好.所以,最终,哪些最有可能取决于您计划如何使用pow,但使用正确的版本是值得的,并且所有版本都很好.实际上,您甚至可以使用以下函数自动选择算法:

double pown_auto(double x, unsigned n, double x_expected, unsigned n_expected) {
    if (x_expected < x_threshold)
        return pow(x, n);
    if (n_expected < n_threshold)
        return pown_l(x, n);
    return pown(x, n);
}

只要x_expected并且n_expected是在编译时决定的常量,以及可能的其他一些注意事项,一个值得盐的优化编译器将自动删除整个pown_auto函数调用,并用适当选择的三种算法替换它.(现在,如果你真的要尝试使用它,你可能不得不玩一点,因为我没有完全尝试编译我上面写的.))

另一方面,glibc pow 确实有效,glibc已经足够大了.C标准应该是可移植的,包括各种嵌入式设备(事实上​​,各地的嵌入式开发人员普遍认为glibc对于他们来说已经太大了),如果每个简单的数学函数需要包含每个简单的数学函数,它就无法移植可能有用的替代算法.所以,这就是它不符合C标准的原因.

脚注:在时间性能测试中,我为我的函数提供了相对慷慨的优化标志(-s -O2),这些标志可能与我的系统(archlinux)上编译glibc的可能性相当,甚至更差,因此结果很可能公平.对于更严格的测试,我不得不编译glibc的自己,我reeeally不喜欢这样做.我曾经使用Gentoo,所以我记得需要多长时间,即使任务是自动化的.结果对我来说足够结论(或相当不确定).你当然欢迎自己这样做.

Bonus round:如果需要精确的整数输出,那么pow(x, n)对所有整数的特化是有用的,这确实发生了.考虑为具有p ^ N个元素的N维数组分配内存.即使用1来关闭p ^ N也会导致可能随机发生的段错误.

Answer 6

C++没有额外重载的一个原因是与C兼容.

C++ 98具有类似的功能double pow(double, int),但这些已在C++ 11中被删除,其中C99不包含它们.

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2011/n3286.html#550

获得稍微更准确的结果也意味着获得稍微不同的结果.

Answer 7

这是 pow() 的一个非常简单的O(log(n))实现，适用于任何数字类型，包括整数：

template<typename T>
static constexpr inline T pown(T x, unsigned p) {
    T result = 1;

    while (p) {
        if (p & 0x1) {
            result *= x;
        }
        x *= x;
        p >>= 1;
    }

    return result;
}

它比 enigmaticPhysicist 的 O(log(n)) 实现更好，因为它不使用递归。

它几乎总是比他的线性实现更快（只要 p > ~3），因为：

• 它不需要任何额外的内存
• 每个循环只多执行约 1.5 倍的操作
• 每个循环仅执行约 1.25 倍的内存更新