Exponentiation d'entier dans OCaml

Question

Existe-t-il une fonction d'exponentiation d'entier dans OCaml? ** est seulement pour les flotteurs. Bien qu'il semble être la plupart du temps précis, n'y at-il pas une possibilité d'erreurs de précision, quelque chose comme 2. ** 3. = 8. retour faux parfois? Existe-t-il une fonction de bibliothèque pour l'exponentiation d'entier? Je pourrais écrire le mien, mais les soucis d'efficacité entrent dans cela, et aussi je serais surpris s'il n'y a pas déjà une telle fonction.

Answer 1

En ce qui concerne la partie à virgule flottante de votre question: OCaml appelle la fonction pow() du système sous-jacent. L'exponentiation à virgule flottante est une fonction difficile à implémenter, mais elle doit seulement être fidèle (c'est-à-dire exacte à Unit in the Last Place) pour que 2. ** 3. = 8. évalue à true, car 8.0 est le seul à l'intérieur d'une ULP du résultat 8 mathématiquement correct.

Toutes les bibliothèques mathématiques doivent (*) être fidèles, vous ne devriez donc pas avoir à vous soucier de cet exemple particulier. Mais not all of them actually are, donc vous avez raison de vous inquiéter.

---

Une meilleure raison de s'inquiéter serait, si vous utilisez des entiers ou plus larges de 63 bits, que les arguments ou le résultat de l'exponentiation ne peuvent pas être représentés exactement comme flotte OCaml (en fait IEEE 754 numéros à double précision cela ne peut pas représenter 9_007_199_254_740_993 ou 2 + 1). Dans ce cas, l'exponentiation à virgule flottante est un mauvais substitut à l'exponentiation d'un entier, non pas à cause d'une faiblesse dans une implémentation particulière, mais parce qu'elle n'est pas conçue pour représenter exactement des entiers aussi grands.

---

(*) Une autre référence amusant à lire à ce sujet est « A Logarithm Too Clever by Half » par William Kahan.

Answer 2

Pas dans la bibliothèque standard. Mais vous pouvez facilement en écrire un vous-même (en utilisant exponentiation by squaring pour être rapide), ou réutiliser une bibliothèque étendue qui fournit ceci. En Batteries, il s'agit de Int.pow.

Voici une mise en œuvre proposée:

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) 

S'il y a un risque de débordement parce que vous manipulez de très grands nombres, vous devriez probablement utiliser une bibliothèque grand entier tel que Zarith, qui fournit toutes sortes des fonctions d'exponentiation.

(Vous pouvez avoir besoin du « exponentiation modulaire », calcul (a^n) mod p, ce qui peut être fait d'une manière qui évite les débordements en appliquant le mod dans les calculs intermédiaires, par exemple dans la fonction pow ci-dessus.)

Answer 3

Voici une autre application qui utilise exponentiation par élévation au carré (comme celui fourni par @gasche), mais celui-ci est récursive

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