Esponenziazione numero intero in OCaml

Question

Esiste una funzione per l'esponenziazione di interi in OCaml? ** è solo per i galleggianti. Anche se sembra essere per lo più accurato, non c'è una possibilità di errori di precisione, qualcosa come 2. ** 3. = 8. restituendo false a volte? Esiste una funzione di libreria per l'esponenziazione di interi? Potrei scrivere il mio, ma le preoccupazioni sull'efficienza arrivano a questo, e sarei sorpreso se non ci fosse già una funzione del genere.

Answer 1

Per quanto riguarda la parte in virgola mobile della tua domanda: OCaml chiama la funzione pow() del sistema sottostante. L'esponenziazione a virgola mobile è una funzione difficile da implementare, ma deve essere solo fedele (ovvero, esatta a uno Unit in the Last Place) per rendere 2. ** 3. = 8. valutare su true, perché 8.0 è l'unico float all'interno di un ULP del risultato matematicamente corretto 8.

Tutte le librerie matematiche devono (*) essere fedele, quindi non dovresti preoccuparti di questo particolare esempio. Ma not all of them actually are, quindi hai ragione di preoccuparti.

---

una ragione migliore per preoccuparsi sarebbe, se si utilizza 63-bit interi o più ampi, che gli argomenti o il risultato della esponenziazione non possono essere rappresentati esattamente come OCaml galleggia (in realtà IEEE 754 numeri a precisione doppia che non può rappresentare 9_007_199_254_740_993 o 2 + 1). In questo caso, l'esponenziazione in virgola mobile è un cattivo sostituto per l'esponenziazione di interi, non a causa di un punto debole in un'implementazione particolare, ma perché non è progettato per rappresentare esattamente interi così grandi.

---

(*) Un altro riferimento divertente leggere su questo argomento è “A Logarithm Too Clever by Half” di William Kahan.

Answer 2

Non nella libreria standard. Ma puoi facilmente scriverne uno da solo (usando exponentiation by squaring per essere veloce), o riutilizzare una libreria estesa che fornisce questo. In Batteries, è Int.pow.

Qui di seguito è una proposta di attuazione:

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) 

Se v'è un rischio di troppo pieno, perché si sta manipolando numeri molto grandi, probabilmente si dovrebbe utilizzare una libreria grande intero tale da Zarith, che fornisce tutti i tipi delle funzioni di esponenziazione.

(potrebbe essere necessario il "elevamento a potenza modulare", calcolando (a^n) mod p; questo può essere fatto in modo tale da evitare overflow applicando il mod nei calcoli intermedi, ad esempio nella funzione pow sopra.)

Answer 3

Ecco un'altra applicazione che utilizza exponentiation elevando al quadrato (come quello fornito da @gasche), ma questo è ricorsiva in coda

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