Integer potęgowanie w OCaml

Question

Czy istnieje funkcja dla całkowitej potęgowania w OCaml? ** jest tylko dla pływaków. Chociaż wydaje się, że jest on w większości dokładny, czy nie ma możliwości błędów precyzji, coś w rodzaju 2. ** 3. = 8. czasami zwraca false? Czy istnieje funkcja biblioteki dla całkowitej potęgowania? Mógłbym napisać własne, ale problemy z wydajnością do tego dochodzą, a także byłbym zaskoczony, gdyby nie istniała już taka funkcja.

Answer 1

chodzi część zmiennoprzecinkowa twojego pytania: OCaml wywołuje funkcję podstawowego systemu pow(). Zmiennoprzecinkową potęgowanie jest trudna funkcja do wykonania, ale to dopiero musi być wierny (czyli z dokładnością do jednego Unit in the Last Place), aby 2. ** 3. = 8. ocenić na true, ponieważ 8.0 jest jedynym float ciągu ULP z matematycznie poprawny wynik 8.

Wszystkie biblioteki matematyczne powinny (*) być wierne, więc nie powinieneś martwić się tym konkretnym przykładem. Ale not all of them actually are, więc masz rację martwić.

---

lepszego powodu martwić się będzie, jeśli używasz 63-bitowe liczby całkowite lub szersze, że argumenty i wynik potęgowania nie można dokładnie reprezentowane OCaml pływaki (właściwie IEEE 754 podwójnej precyzji liczb które nie mogą reprezentować wartości 9_007_199_254_740_993 lub 2 + 1). W tym przypadku, potęgowanie zmiennoprzecinkowe jest złym substytutem dla potęgowania liczby całkowitej, nie z powodu słabości w konkretnej implementacji, ale dlatego, że nie jest zaprojektowane do reprezentowania dokładnie liczb całkowitych, które są duże.

---

(*) Inna zabawa odniesienie czytać na ten temat jest „A Logarithm Too Clever by Half” William Kahan.

Answer 2

Nie w standardowej bibliotece. Ale możesz łatwo napisać samemu (przy użyciu szybkiego dostępu), lub użyć ponownie rozszerzonej biblioteki, która to zapewnia. W Batteries jest to Int.pow.

Poniżej znajduje się proponowana realizacja:

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) 

Jeśli istnieje ryzyko przelania, ponieważ jesteś manipulowania bardzo dużych liczb, powinieneś korzystać z biblioteki dużym całkowitą takie jak Zarith, która zawiera wszystkie rodzaje funkcji potęgowania.

(może być potrzebny „modularne potęgowanie” Komputery (a^n) mod p; można to zrobić w sposób, który pozwala uniknąć przepełnienia stosując mod w obliczeniach pośredniczących, na przykład w funkcji pow powyżej).

Answer 3

Oto kolejna realizacja, który wykorzystuje algorytm szybkiego potęgowania (jak to dostarczane przez @gasche), ale ten jest ogon rekurencyjnej

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