15

OCaml 中是否有整数求幂函数？** 仅适用于花车。虽然它似乎大部分是准确的，但是否存在精度错误的可能性，例如 2. ** 3. = 8. 有时返回 false ？是否有用于整数幂运算的库函数？我可以自己编写，但会涉及到效率问题，如果还没有这样的功能，我会感到惊讶。

4

3 回答 3

29

不在标准库中。但是您可以轻松地自己编写一个（使用平方求幂以加快速度），或者重用提供此功能的扩展库。在电池中，它是Int.pow。

下面是一个建议的实现：

let rec pow a = function
  | 0 -> 1
  | 1 -> a
  | n -> 
    let b = pow a (n / 2) in
    b * b * (if n mod 2 = 0 then 1 else a)

如果由于您正在处理非常大的数字而存在溢出风险，则您可能应该使用诸如Zarith 之类的大整数库，它提供了各种求幂函数。

（您可能需要“模幂”计算(a^n) mod p；这可以通过在中间计算中应用 mod 来避免溢出，例如在上面的函数中pow。）

于 2013-06-05T22:07:54.417 回答
14

关于您问题的浮点部分：OCaml 调用底层系统的pow()函数。浮点求幂是一个难以实现的函数，但它只需要忠实（即精确到最后一个 Unit 中的一个Unit in the Last Place）即可2. ** 3. = 8.计算为true，因为8.0它是唯一float在数学上正确的结果 8 的一个 ULP 内。

所有的数学库都应该（*）是忠实的，所以你不必担心这个特定的例子。但并非所有这些实际上都是，所以你担心是对的。

一个更好的担心理由是，如果您使用 63 位整数或更宽的整数，则参数或求幂结果不能完全表示为 OCaml 浮点数（实际上 IEEE 754 双精度数不能表示9_007_199_254_740_993或 2 53 + 1）。在这种情况下，浮点取幂不能很好地替代整数取幂，这不是因为特定实现的弱点，而是因为它的设计目的不是精确地表示那么大的整数。

(*) 关于这个主题的另一个有趣的参考资料是 William Kahan 的“<a href="http://www.cs.berkeley.edu/~wkahan/LOG10HAF.TXT">A Logarithm Too Clever by Half”。

于 2013-06-06T11:37:24.550 回答
7

这是另一种使用平方求幂的实现（就像@gasche提供的那个），但是这个是尾递归的

let is_even n = 
  n mod 2 = 0

(* https://en.wikipedia.org/wiki/Exponentiation_by_squaring *)
let pow base exponent =
  if exponent < 0 then invalid_arg "exponent can not be negative" else
  let rec aux accumulator base = function
    | 0 -> accumulator
    | 1 -> base * accumulator
    | e when is_even e -> aux accumulator (base * base) (e / 2)
    | e -> aux (base * accumulator) (base * base) ((e - 1) / 2) in
  aux 1 base exponent
于 2016-05-12T10:33:06.450 回答