高速指数関数を作成する

Question

OCamlでより速いバージョンの指数関数を見つけるのが難しいです。ここで私は従うことをしようとしているいくつかの注意事項は次のとおりです。

1. ではなくexpt b n ==> b * (b * (b ...)の典型的な再帰的な指数のバージョンは、この機能は、B二つの引数を受け取り、nおよび基本的に分割統治スタンスを取ります。
2. nが偶数の場合、nが、その後fastexpt b n => b * (b^(n - 1))

奇数の場合は、その後、他のfastexpt b n => (b^(n/2))^2は、ここで私はこれまでに書いたコードです：

let fastexpt : int -> int -> int 
= fun b n -> 
    if n = 0 then 1 
    else if ((n mod 2) = 0) then (expt b (n/2)) * (expt b (n/2)) 
    else b * (expt b (n - 1));; 

は、私の質問は：書き込みする方法はありますが、 expt機能を使用しないでこの機能を使用できますか？ （私たちは、あなたがすでにexptを宣言したことを考慮すれば）何がここでやっていることは除算を使用して方法を最初に征服した後、残りの計算のための通常のものを使用している

Answer 1

もう一つは、ということですnが奇数の場合、高速累乗の目的はb * b^((n-1)/2) * b^((n-1)/2)です。

あなただけの再帰としてfastexptを定義し、それをすべての方法を使用されて何をすべき：fastexpt`代わり

let rec fastexpt : int -> int -> int 
= fun b n -> 
    if n = 0 then 1 
    else 
     let b2 = fastexpt b (n/2) in 
     if n mod 2 = 0 then b2 * b2 
     else b * b2 * b2;;