Integer-Exponentiation in OCaml

Question

Gibt es eine Funktion für Integer-Potenzierung in OCaml? ** ist nur für Schwimmer. Obwohl es meistens genau zu sein scheint, gibt es keine Möglichkeit für Präzisionsfehler, etwa 2. ** 3. = 8. manchmal falsch? Gibt es eine Bibliotheksfunktion für die Integer-Potenzierung? Ich könnte mein eigenes schreiben, aber da drängen sich Effizienzprobleme auf, und auch ich würde mich wundern, wenn es nicht schon eine solche Funktion gibt.

Answer 1

Bezüglich Der Fließkommateil Ihrer Frage: OCaml ruft die pow() Funktion des zugrunde liegenden Systems auf. Floating-Point-Exponentiation ist eine schwierige Funktion zu implementieren, aber es muss nur treu sein (das heißt, genau zu Unit in the Last Place), 2. ** 3. = 8. zu true bewerten, weil 8.0 der einzige float innerhalb einer ULP der mathematisch korrekte Ergebnis 8 ist.

Alle mathematischen Bibliotheken sollten (*) treu sein, also sollten Sie sich über dieses spezielle Beispiel keine Gedanken machen. Aber not all of them actually are, so dass Sie sich Sorgen machen müssen.

---

Ein besserer Grund wäre, sich Sorgen zu machen, wenn Sie mit 63-Bit-Integer oder breiter, dass die Argumente oder das Ergebnis der Potenzierung nicht exakt dargestellt werden, wie OCaml schwimmt (eigentlich IEEE 754 mit doppelter Genauigkeit Zahlen das kann 9_007_199_254_740_993 oder 2 + 1) nicht darstellen. In diesem Fall ist die Fließkomma-Potenzierung ein schlechter Ersatz für die Potenzierung von Ganzzahlen, nicht wegen einer Schwäche in einer bestimmten Implementierung, sondern weil sie nicht dafür ausgelegt ist, genau so große Ganzzahlen darzustellen.

---

(*) Ein weiterer Spaß Bezug zu diesem Thema zu lesen ist „A Logarithm Too Clever by Half“ von William Kahan.

Answer 2

Nicht in der Standardbibliothek. Aber Sie können auch einfach selbst einen schreiben (mit exponentiation by squaring, um schnell zu sein) oder eine erweiterte Bibliothek, die dies bietet, wiederverwenden. In Batteries ist es Int.pow.

Nachfolgend finden Sie eine vorgeschlagene Umsetzung:

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) 

Wenn die Gefahr von Überlauf ist, weil Sie sehr große Zahlen sind manipuliert, werden Sie wahrscheinlich eine große ganzzahlige Bibliothek wie Zarith, die alle Arten bietet verwenden sollten von Potenzierungsfunktionen.

(Sie können die „modulare Potenzierung“ benötigen, Rechen (a^n) mod p, dies kann in einer Weise geschehen, die pow oben überläuft, indem die Mod in den dazwischen liegenden Berechnungen, zum Beispiel in der Funktion vermeidet.)

Answer 3

Hier ist eine andere Implementierung, die Potenzierung verwendet durch Quadrierung (wie die von @gasche zur Verfügung gestellt), aber dieses ist Schwanz-rekursive

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