Erstellen einer schnellen Exponentenfunktion

Question

Ich habe Probleme, eine schnellere Version der typischen Exponentenfunktion in OCaml zu finden. Hier sind einige Richtlinien, die ich zu folgen bin versucht:

1. Anstatt die typische rekursive Exponent Version von expt b n ==> b * (b * (b ...) diese Funktion erhält zwei Argumente b und n und nimmt grundsätzlich eine Kluft und Haltung erobern.
2. Wenn n gerade ist, dann fastexpt b n => (b^(n/2))^2 sonst, wenn n ungerade ist dann fastexpt b n => b * (b^(n - 1))

Hier ist der Code, den ich geschrieben habe, so weit:

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));; 

Meine Frage ist: Gibt es eine Möglichkeit zu schreiben diese Funktion ohne die expt Funktion zu verwenden?

Answer 1

Was Sie hier machen die Kluft verwendet, und Verfahren zum ersten Mal erobern und dann für den Rest der Berechnung der normalen Verwendung (wenn man bedenkt, dass Sie bereits expt erklärt)

Eine andere Sache ist, dass Wenn n ungerade ist, können Sie b * b^((n-1)/2) * b^((n-1)/2) zurückgeben, das ist der Zweck der schnellen Potenzierung.

Was Sie tun sollten, ist nur fastexpt als rekursiv definieren und verwenden Sie es den ganzen Weg:

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;;