OCamlで整数累乗

Question

OCamlに整数累乗の関数がありますか？ **は浮動小数点のみです。ほとんど正確であるように見えますが、精密エラーの可能性はありませんか？** 3. = 8. 8.時々falseを返しますか？整数累乗のためのライブラリ関数はありますか？私は自分自身を書くことができましたが、効率の問題がそこに入っています。また、そのような機能がまだなければ私は驚くでしょう。

Answer 1

についてあなたの質問の浮動小数点部分：OCamlは、基礎となるシステムのpow()関数を呼び出します。浮動小数点累乗は実装するのは難しい関数ですが、8.0は数学的に正しい結果の1つのULP内の唯一のものであるため、2. ** 3. = 8.をtrueとすることは忠実である必要があります（つまり、Unit in the Last Placeに正確です）。

すべての数学ライブラリは忠実である必要がありますので、この特定の例について心配する必要はありません。しかし、not all of them actually are、あなたは心配する権利です。あなたはOCamlは（実際にはIEEE 754倍精度数を浮動した引数または累乗の結果が正確に表現できないことを、63ビット整数またはより広いを使用している場合は心配する

---

より良い理由は、だろう9_007_199_254_740_993または2 +1を表すことはできません）。この場合、浮動小数点指数演算は整数の指数演算に代わるものであり、特定の実装の弱点ではありませんが、その整数を正確に表すように設計されていないためです。このテーマに読んで

---

（*）もう一つの楽しみの参照は、ウィリアム・カハンで「A Logarithm Too Clever by Half」です。

Answer 2

標準ライブラリにはありません。しかし、自分で簡単に書くことができます（速くなるようにexponentiation by squaringを使用）、またはこれを提供する拡張ライブラリを再利用します。 Batteriesには、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を計算する、「べき乗剰余」を必要とすることができ、これは、上記機能pow、例えば、中間計算にMODを適用することにより、オーバーフローを回避する方法で行うことができる。）

Answer 3

ここで（@gascheが提供するもののような）乗で累乗を使用しますが、この1つは末尾再帰

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