Wie macht man Potenzierung in Clojure?

106

Wie kann ich in Clojure potenzieren? Im Moment brauche ich nur eine ganzzahlige Potenzierung, aber die Frage gilt auch für Brüche.

Peter
quelle
18
Als jemand, der Clojure nicht kennt, aber dazu neigt, es zu mögen (ein Fan von Lisps, funktionaler Programmierung und vielen praktischen Bibliotheken), bin ich enttäuscht, dass diese einfache Frage so viele Antworten hat - oder dass sie es ist musste überhaupt gefragt werden. Ich hätte gedacht, dass Potenzierung nur eine der Grundfunktionen ist, die bereitgestellt werden, ohne dass etwas Besonderes getan werden muss. Ich bin froh, dass es gefragt wurde.
Mars
1
Nun ja, wahrscheinlich sollte eine Version davon im Kern sein ... aber ich denke, dass viele Antworten immer noch ein gutes Zeichen sind. Die "mehreren Wege zur Implementierung" scheinen der Grund dafür zu sein, dass viele dieser Dinge nicht bereitgestellt werden. Der Benutzer sollte die Details der Funktion kennen, die er aus Effizienzgründen verwendet. Zum Beispiel (wie in der gewählten Antwort ausgeführt) können einige Wege den Stapel möglicherweise sprengen, andere weniger wahrscheinlich. Vielleicht sind einige faul, andere eifrig ... alle Details, die in Clojure beachtet werden müssen, weshalb ich der Meinung bin, dass die meisten nicht trivialen
Bibliotheken aus
3
Ich denke, der Grund, warum es nicht nur eine Exp-Funktion im Kern gibt, ist, dass der numerische Turm von Clojure aus Effizienzgründen stark beschädigt ist. Es gibt also viele verschiedene Dinge, die Sie unter Potenzierung verstehen könnten. Was soll (exp 2 (exp 2 200)) sein? Ein Fehler oder eine große Ganzzahl, deren Berechnung ein Alter erfordert? Wenn Sie nur die übliche Gleitkomma-Exp möchten, ist die Java-Version integriert. Wenn Sie eine Sprache möchten, in der die Zahlen ihr Bestes geben, um sich wie die Real zu verhalten und die Kosten aufzuhängen, verwenden Sie Schema anstelle von Clojure.
John Lawrence Aspden

Antworten:

141

klassische Rekursion (sehen Sie dies, es bläst Stapel)

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

Schwanzrekursion

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

funktional

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

hinterhältig (auch Schläge stapeln, aber nicht so leicht)

(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))))))

Bibliothek

(require 'clojure.contrib.math)
John Lawrence Aspden
quelle
11
Unterhaltsame Antwort!
Matt Fenwick
siehe vollständig iterative Version der hinterhältigen Lösung unter stackoverflow.com/a/22977674/231589
Karl Rosaen
5
Clojure.contrib.math ist jetzt veraltet, siehe Math.Numeric-Tower
alvaro g
Der zweite Vorschlag (Schwanz rekursiv) hat einen ganzzahligen Überlauf für n <0.
Pointo Senshi
1
Fantastische Antwort. So geht's mit einem Makro: (defmacro exp [xn] `(* ~ @ (nimm n (wiederhole x)))
Daniel Szmulewicz
78

Clojure verfügt über eine Power-Funktion, die gut funktioniert: Ich würde empfehlen, diese Funktion zu verwenden, anstatt über Java Interop zu arbeiten, da alle Clojure-Zahlentypen mit beliebiger Genauigkeit korrekt behandelt werden. Es befindet sich im Namespace clojure.math.numeric-Tower .

Es wird eher exptzur Potenzierung aufgerufen als poweroder powwas vielleicht erklärt, warum es ein bisschen schwer zu finden ist ... hier ist ein kleines Beispiel (Hinweis, der usefunktioniert, aber besser genutzt wird 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

Erinnerung zur Paketinstallation

Sie müssen zuerst das Java-Paket installieren org.clojure.math.numeric-tower, um den Clojure-Namespace clojure.math.numeric-towerzugänglich zu machen !

In der Befehlszeile:

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

Bearbeiten project.cljSie [org.clojure/math.numeric-tower "0.0.4"]dann den Abhängigkeitsvektor und fügen Sie ihn hinzu .

Starten Sie eine Lein REPL (keine Clojure REPL)

$ lein repl

Jetzt:

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

oder

(require '[clojure.math.numeric-tower :as math :refer [expt]])
(expt 4 2)
;=> 16
mikera
quelle
1
Wahrscheinlich unbekannt, da es nicht Teil von Standard Clojure zu sein scheint. 1.3.0 wirft Fehler darüber auf, dass die Datei math.clj nicht gefunden werden kann, wenn ich dies auf diese Weise versuche.
Brian Knoblauch
9
Ich denke, es ist jetzt in "clojure.math.numeric-Tower" ab 1.3 (da clojure.contrib in einzelne Bibliotheken aufgeteilt wurde)
mikera
"Erinnerung an die Paketinstallation" hinzugefügt, um die Frustration der Benutzer zu lindern.
David Tonhofer
60

Sie können Java Math.powoder BigInteger.powMethoden verwenden:

(Math/pow base exponent)

(.pow (bigint base) exponent)
sepp2k
quelle
+1, obwohl ich weiß, dass Sie mit Java-Bibliotheken interagieren können; 1) Math.pow arbeitet mit Doppel, ich brauche Ganzzahlen, können Sie ein Beispiel geben? 2) Müssen Sie wirklich interop für etw verwenden? einfach wie Kräfte?
Peter
Clojure wurde um die Java-Bibliotheken herum erstellt, es wird nicht versucht, das zu reparieren, was nicht kaputt ist, und Math / pow funktioniert einwandfrei. Warum müssen Sie sich um Doppel- oder Ganzzahlen kümmern? Sie können auch diesen richhickey.github.com/clojure-contrib/…
DaVinci
1
@Peter: 1) Wenn deine Kräfte nicht so groß sind, dass sie nicht mehr genau durch Doppel dargestellt werden können, ist es wirklich kein Problem, nur das Ergebnis auf int zu setzen. 2) Ich sehe nicht, wie Math/powkomplizierter das Schreiben ist als math-powoder wie auch immer der Name lauten würde, wenn es ein Clojure-Äquivalent gäbe. Wenn es bereits eine einfache Java-Methode gibt, die das tut, was Sie wollen, gibt es keinen Grund, die Funktionalität in clojure neu zu erstellen. Java Interop ist nicht von Natur aus schädlich.
sepp2k
3
@ Da vinci: seltsame Bemerkung, es ist eine eigene Sprache und hat viele Funktionen, die in Java sind (wie Stringreverse)
Peter
4
Ich denke, Sie verwenden Clojures clojure.contrib.math / expt besser, wenn Sie genaue Biginteger-Potenzen wünschen. Wahrscheinlich macht das gleiche unter der Haube, aber viel schöner als über Java Interop zu gehen .....
Mikera
13

Als diese Frage ursprünglich gestellt wurde, war clojure.contrib.math / expt die offizielle Bibliotheksfunktion, um dies zu tun. Seitdem ist es zu clojure.math.numeric-turm umgezogen

Amalloy
quelle
+1 für diese Antwort, da alle exakten Clojure-Arithmetiken (dh BigDecimal / BigInteger) korrekt verarbeitet werden.
Mikera
„Hinweis - die contrib Libs haben zu einzelnen repos unter Clojure org bewegt“ ; Diese Antwort nur auf diesen Link ist jetzt irreführend.
Brad Koch
8
user=> (.pow (BigInteger. "2") 10)
1024
user=> (.pow (BigInteger. "2") 100)
1267650600228229401496703205376
KIM Taegyoon
quelle
6
Sie können auch die wörtliche Notation dafür verwenden:(.pow 2M 100)
Geräuschschmied
1
Ihre Typen sind unterschiedlich. user => (Typ 2M) java.math.BigDecimal user => (Typ (BigInteger. "2")) java.math.BigInteger
KIM Taegyoon
Imo beste Lösung, Showr, unter Verwendung vorhandener Bibliotheken und einschließlich der Handhabung von Bigint. +1
Daniel Gruszczyk
Für mich (Math/pow Math/E x)macht der Trick (durch Math/Edie Basis Ihrer Wahl ersetzen ).
Zaz
6

Wenn Sie wirklich eine Funktion und keine Methode benötigen, können Sie sie einfach umbrechen:

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

Und in dieser Funktion können Sie es auf intoder ähnlich umwandeln. Funktionen sind oft nützlicher als Methoden, weil Sie sie als Parameter an andere Funktionen übergeben können - in diesem Fall mapfällt mir ein.

Wenn Sie Java Interop wirklich vermeiden müssen, können Sie Ihre eigene Power-Funktion schreiben. Dies ist beispielsweise eine einfache Funktion:

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

Das berechnet die Leistung für einen ganzzahligen Exponenten (dh keine Wurzeln).

Wenn Sie mit großen Zahlen arbeiten, möchten Sie möglicherweise BigIntegerstattdessen anstelle von verwenden int.

Wenn Sie mit sehr großen Zahlen arbeiten, möchten Sie diese möglicherweise als Ziffernlisten ausdrücken und Ihre eigenen arithmetischen Funktionen schreiben, um sie zu streamen, während sie das Ergebnis berechnen und das Ergebnis an einen anderen Stream ausgeben.

Goran Jovic
quelle
4

Ich denke das würde auch funktionieren:

(defn expt [x pow] (apply * (repeat pow x)))
TJ Trapp
quelle
aber scheint bei 2 ^ 63 maximal zu sein ... def nicht in der Lage zu 2 ^ 200
TJ Trapp
4

SICP inspirierte die oben beschriebene vollständige iterative schnelle Version der 'hinterhältigen' Implementierung.

(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
quelle
2

Implementierung der "hinterhältigen" Methode mit Schwanzrekursion und unterstützendem negativen Exponenten:

(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)))))))
Tolstoyevsky
quelle
2

Ein einfacher Einzeiler mit Reduce:

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

Versuchen

(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)))))

für eine schwanzrekursive O (log n) -Lösung, wenn Sie sie selbst implementieren möchten (unterstützt nur positive Ganzzahlen). Offensichtlich ist die bessere Lösung, die Bibliotheksfunktionen zu verwenden, auf die andere hingewiesen haben.

Retief
quelle
0

Wie wäre es mit clojure.contrib.genric.math-Funktionen

In der Bibliothek clojure.contrib.generic.math-functions gibt es eine pow-Funktion. Es ist nur ein Makro für Math.pow und eher eine "clojureische" Art, die Java-Mathematikfunktion aufzurufen.

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

Fido
quelle