Comment faire l'exponentiation en clojure?

106

Comment puis-je faire de l'exponentiation en clojure? Pour l'instant, je n'ai besoin que d'exponentiation entière, mais la question vaut aussi pour les fractions.

Peter
la source
18
En tant que personne qui ne connaît pas le clojure, mais qui est prédisposée à l'aimer (étant fan de lisps, de programmation fonctionnelle et d'avoir beaucoup de bibliothèques pratiques), je suis déçu que cette simple question ait autant de réponses - ou qu'elle devait être demandé du tout. J'aurais pensé que l'exponentiation ne serait qu'une des fonctions de base fournies sans avoir à faire quoi que ce soit de spécial. Je suis content que cela ait été demandé, cependant.
Mars
1
eh bien oui probablement une version de celui-ci devrait être dans le noyau ... mais je pense que de nombreuses réponses sont toujours un bon signe. les "chemins multiples vers l'implémentation" semblent être la raison pour laquelle beaucoup de ces choses ne sont pas fournies - l'utilisateur doit connaître les détails de la fonction qu'il utilise pour des raisons d'efficacité. par exemple (comme cela est souligné dans la réponse choisie) certaines façons peuvent potentiellement faire exploser la pile, d'autres moins susceptibles de le faire. peut-être que certains sont paresseux, d'autres impatients ... tous les détails qui nécessitent une certaine attention dans Clojure, c'est pourquoi je pense que la plupart des
bibliothèques
3
Je pense que la raison pour laquelle il n'y a pas qu'une fonction exp dans le noyau est que la tour numérique de clojure est gravement cassée pour des raisons d'efficacité. Il y a donc toutes sortes de choses différentes que vous pourriez entendre par exponentiation. Que devrait être (exp 2 (exp 2 200))? Une erreur ou un énorme entier qui prend un âge à calculer? Si vous voulez juste la virgule flottante habituelle, alors la java est intégrée. Si vous voulez un langage où les nombres font de leur mieux pour agir comme les réels et accrocher le coût, utilisez le schéma au lieu de clojure.
John Lawrence Aspden

Réponses:

141

récursion classique (regardez ça, ça souffle pile)

(defn exp [x n]
     (if (zero? n) 1
         (* x (exp x (dec n)))))

récursion de queue

(defn exp [x n]
  (loop [acc 1 n n]
    (if (zero? n) acc
        (recur (* x acc) (dec n)))))

fonctionnel

(defn exp [x n]
  (reduce * (repeat n x)))

sournois (souffle également la pile, mais pas si facilement)

(defn exp-s [x n]
  (let [square (fn[x] (* x x))]
    (cond (zero? n) 1
          (even? n) (square (exp-s x (/ n 2)))
          :else (* x (exp-s x (dec n))))))

bibliothèque

(require 'clojure.contrib.math)
John Lawrence Aspden
la source
11
Réponse amusante!
Matt Fenwick
voir la version entièrement itérative de la solution sournoise ci-dessous stackoverflow.com/a/22977674/231589
Karl Rosaen
5
Clojure.contrib.math est maintenant obsolète, voir Math.Numeric-Tower
alvaro g
La deuxième suggestion (queue récursive) a un débordement d'entier pour n <0.
Pointo Senshi
1
Réponse fantastique. Voici comment faire avec une macro: (defmacro exp [xn] `(* ~ @ (take n (repeat x))))
Daniel Szmulewicz
78

Clojure a une fonction d'alimentation qui fonctionne bien: je recommanderais de l'utiliser plutôt que de passer par l'interopérabilité Java car il gère correctement tous les types de nombres à précision arbitraire Clojure. Il se trouve dans l'espace de noms clojure.math.numeric-tower .

C'est appelé exptà l' exponentiation plutôt que powerou powce qui explique peut-être pourquoi c'est un peu difficile à trouver ... en tout cas voici un petit exemple (note qui usefonctionne mais mieux utiliser require):

(require '[clojure.math.numeric-tower :as math :refer [expt]])  ; as of Clojure 1.3
;; (use 'clojure.contrib.math)     ; before Clojure 1.3
(expt 2 200)
=> 1606938044258990275541962092341162602522202993782792835301376

Rappel sur l'installation du package

Vous devez d'abord installer le package Java org.clojure.math.numeric-towerpour rendre l'espace de noms Clojure clojure.math.numeric-toweraccessible!

Sur la ligne de commande:

$ lein new my-example-project
$ cd lein new my-example-project

Puis éditez project.cljet ajoutez [org.clojure/math.numeric-tower "0.0.4"]au vecteur de dépendances.

Démarrer un lein REPL (pas un clojure REPL)

$ lein repl

Maintenant:

(require '[clojure.math.numeric-tower :as math])
(math/expt 4 2)
;=> 16

ou

(require '[clojure.math.numeric-tower :as math :refer [expt]])
(expt 4 2)
;=> 16
Mikera
la source
1
Probablement inconnu car il ne semble pas faire partie de Clojure standard. 1.3.0 jette des erreurs sur l'impossibilité de localiser le math.clj lorsque j'essaye de le faire de cette façon.
Brian Knoblauch
9
Je pense que c'est maintenant dans "clojure.math.numeric-tower" à partir de la 1.3 (depuis que clojure.contrib a été divisé en bibliothèques individuelles)
mikera
Ajout d'un "rappel sur l'installation du paquet" pour apaiser la frustration des utilisateurs.
David Tonhofer le
60

Vous pouvez utiliser les méthodes Math.powou Java BigInteger.pow:

(Math/pow base exponent)

(.pow (bigint base) exponent)
sepp2k
la source
+1, bien que je sache que vous pouvez interopérer avec les bibliothèques java; cependant, 1) Math.pow fonctionne avec des doubles, j'ai besoin de nombres entiers, pouvez-vous donner un exemple? 2) Devez-vous vraiment utiliser l'interopérabilité pour qc. simples comme des pouvoirs?
Peter
Clojure est construit autour des bibliothèques java, il ne tente pas de réparer ce qui n'est pas cassé et Math / pow fonctionne très bien. Pourquoi avez-vous besoin de vous soucier des doubles ou des entiers? Vous pouvez également utiliser ce richhickey.github.com/clojure-contrib/…
DaVinci
1
@Peter: 1) À moins que vos pouvoirs ne soient si grands qu'ils ne peuvent plus être représentés avec précision par des doubles, il n'y a vraiment aucun problème à simplement lancer le résultat en int. 2) Je ne vois pas en quoi l'écriture Math/powest plus compliquée math-powou quel que soit le nom s'il y avait un équivalent clojure. S'il existe déjà une méthode java simple qui fait ce que vous voulez, il n'y a aucune raison de recréer la fonctionnalité dans clojure. L'interopérabilité Java n'est pas intrinsèquement nuisible.
sepp2k
3
@Da vinci: remarque étrange, c'est un langage qui lui est propre et a beaucoup de fonctions qui sont en Java (comme stringreverse)
Peter
4
Je pense que vous feriez mieux d'utiliser clojure.contrib.math / expt de Clojure si vous voulez des puissances plus précises. Fait probablement la même chose sous le capot, mais beaucoup plus agréable que de passer via Java Interop .....
mikera
13

Lorsque cette question a été posée à l'origine, clojure.contrib.math / expt était la fonction officielle de la bibliothèque pour ce faire. Depuis, il est passé à clojure.math.numeric-tower

amalloy
la source
+1 pour cette réponse car il gère correctement toute l'arithmétique exacte de Clojure (c'est-à-dire BigDecimal / BigInteger).
mikera
"Remarque - les bibliothèques contrib ont été déplacées vers des dépôts individuels sous Clojure org" ; cette réponse de lien seulement est maintenant trompeuse.
Brad Koch
8
user=> (.pow (BigInteger. "2") 10)
1024
user=> (.pow (BigInteger. "2") 100)
1267650600228229401496703205376
KIM Taegyoon
la source
6
vous pouvez également utiliser la notation littérale pour cela:(.pow 2M 100)
noisesmith
1
Leurs types sont différents. user => (type 2M) java.math.BigDecimal user => (type (BigInteger. "2")) java.math.BigInteger
KIM Taegyoon
imo meilleure solution, showr, utilisant les bibliothèques existantes, et incluant la gestion de bigint. +1
Daniel Gruszczyk
Pour moi (Math/pow Math/E x)fait l'affaire (en remplaçant Math/Epar la base de votre choix).
Zaz
6

Si vous avez vraiment besoin d'une fonction et non d'une méthode, vous pouvez simplement l'envelopper:

 (defn pow [b e] (Math/pow b e))

Et dans cette fonction, vous pouvez le lancer intou similaire. Les fonctions sont souvent plus utiles que les méthodes car vous pouvez les passer en tant que paramètres à d'autres fonctions - dans ce cas, cela mapme vient à l'esprit.

Si vous avez vraiment besoin d'éviter l'interopérabilité Java, vous pouvez écrire votre propre fonction d'alimentation. Par exemple, c'est une fonction simple:

 (defn pow [n p] (let [result (apply * (take (abs p) (cycle [n])))]
   (if (neg? p) (/ 1 result) result)))

Cela calcule la puissance pour l'exposant entier (c'est-à-dire pas de racines).

De plus, si vous avez affaire à de grands nombres, vous pouvez utiliser à la BigIntegerplace de int.

Et si vous avez affaire à de très grands nombres, vous voudrez peut-être les exprimer sous forme de listes de chiffres et écrire vos propres fonctions arithmétiques pour les parcourir au fur et à mesure qu'ils calculent le résultat et envoient le résultat vers un autre flux.

Goran Jovic
la source
4

Je pense que cela fonctionnerait aussi:

(defn expt [x pow] (apply * (repeat pow x)))
TJ Trapp
la source
mais semble au maximum à 2 ^ 63 ... def pas capable de 2 ^ 200
TJ Trapp
4

SICP a inspiré la version rapide itérative complète de l'implémentation «sournoise» ci-dessus.

(defn fast-expt-iter [b n]
  (let [inner (fn [a b n]
                (cond
                  (= n 0) a
                  (even? n) (recur a (* b b) (/ n 2))
                  :else (recur (* a b) b (- n 1))))
        ]
    (inner 1 b n)))
Karl Rosaen
la source
2

Implémentation de la méthode "sournoise" avec récursion de queue et supportant l'exposant négatif:

(defn exp
  "exponent of x^n (int n only), with tail recursion and O(logn)"
   [x n]
   (if (< n 0)
     (/ 1 (exp x (- n)))
     (loop [acc 1
            base x
            pow n]
       (if (= pow 0)
         acc                           
         (if (even? pow)
           (recur acc (* base base) (/ pow 2))
           (recur  (* acc base) base (dec pow)))))))
Tolstoïevsky
la source
2

Un simple one-liner utilisant réduire:

(defn pow [a b] (reduce * 1 (repeat b a)))
Alan R. Soares
la source
1

Essayer

(defn pow [x n]
  (loop [x x n n r 1]
    (cond
      (= n 0) r
      (even? n) (recur (* x x) (/ n 2) r)
      :else (recur x (dec n) (* r x)))))

pour une solution O (log n) récursive à la fin, si vous souhaitez l'implémenter vous-même (ne prend en charge que les entiers positifs). De toute évidence, la meilleure solution est d'utiliser les fonctions de bibliothèque que d'autres ont indiquées.

Retief
la source
0

Que diriez-vous de clojure.contrib.genric.math-functions

Il existe une fonction pow dans la bibliothèque clojure.contrib.generic.math-functions. C'est juste une macro de Math.pow et c'est plus une façon "clojureish" d'appeler la fonction mathématique Java.

http://clojure.github.com/clojure-contrib/generic.math-functions-api.html#clojure.contrib.generic.math-functions/pow

fido
la source