OCaml中的整数取幂 [英] Integer exponentiation in OCaml

问题描述

OCaml中是否存在整数取幂的函数？ **仅适用于花车。虽然看起来大部分都是准确的，但是不存在精确错误的可能性，例如2. ** 3. = 8.有时会返回错误？是否有用于整数求幂的库函数？我可以写自己的，但效率问题就出现了，如果没有这样的功能我也会感到惊讶。

Is there a function for integer exponentiation in OCaml? ** is only for floats. Although it seems to be mostly accurate, isn't there a possibility of precision errors, something like 2. ** 3. = 8. returning false sometimes? Is there a library function for integer exponentiation? I could write my own, but efficiency concerns come into that, and also I'd be surprised if there isn't such a function already.

推荐答案

关于问题的浮点部分：OCaml调用底层系统的 pow（）函数。浮点取幂是一项难以实现的功能，但它只需要忠实（即，准确到一个最后一位的单位） ）使 2。 ** 3. = 8。评估为 true ，因为 8.0 是唯一 float 在数学上正确结果的一个ULP内8。

Regarding the floating-point part of your question: OCaml calls the underlying system's pow() function. Floating-point exponentiation is a difficult function to implement, but it only needs to be faithful (that is, accurate to one Unit in the Last Place) to make 2. ** 3. = 8. evaluate to true, because 8.0 is the only float within one ULP of the mathematically correct result 8.

所有数学库都应该（*）忠实，所以你不应该担心这个特殊的例子。但并非全部他们实际上是，所以你担心。

All math libraries should(*) be faithful, so you should not have to worry about this particular example. But not all of them actually are, so you are right to worry.

更值得担心的是，如果您使用的是63位整数或更宽，表示参数或取幂的结果不能完全表示为OCaml浮点数（实际上是IEEE 754双精度数，不能代表 9_007_199_254_740_993 或2 ⁵³ + 1）。在这种情况下，浮点取幂是整数取幂的不良替代，不是因为特定实现中的弱点，而是因为它不是为了表示那么大的整数。

A better reason to worry would be, if you are using 63-bit integers or wider, that the arguments or the result of the exponentiation cannot be represented exactly as OCaml floats (actually IEEE 754 double-precision numbers that cannot represent 9_007_199_254_740_993 or 2⁵³ + 1). In this case, floating-point exponentiation is a bad substitute for integer exponentiation, not because of a weakness in a particular implementation, but because it is not designed to represent exactly integers that big.

（*）另一个有关此主题的有趣参考是对数太聪明了一半作者William Kahan。

(*) Another fun reference to read on this subject is "A Logarithm Too Clever by Half" by William Kahan.

这篇关于OCaml中的整数取幂的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！