Jak potęgować w clojure?

106

Jak mogę potęgować w clojure? Na razie potrzebuję tylko potęgowania liczb całkowitych, ale pytanie dotyczy również ułamków.

Piotr
źródło
18
Jako ktoś, kto nie zna clojure, ale ma predyspozycje do polubienia go (bycie fanem seplenienia, programowania funkcjonalnego i posiadania wielu podręcznych bibliotek), jestem rozczarowany, że to proste pytanie ma tak wiele odpowiedzi - lub że w ogóle trzeba było zapytać. Pomyślałbym, że potęgowanie byłoby po prostu jedną z podstawowych funkcji bez konieczności robienia czegokolwiek specjalnego. Cieszę się jednak, że o to zapytano.
Mars
1
no tak, pewnie jakaś wersja powinna być w rdzeniu ... ale myślę, że wiele odpowiedzi to nadal dobry znak. Wydaje się, że „wiele ścieżek do implementacji” jest powodem, dla którego wiele z tych rzeczy nie jest dostarczanych - użytkownik powinien znać szczegóły funkcji, której używa, ze względu na wydajność. na przykład (jak wskazano w wybranej odpowiedzi) niektóre sposoby mogą potencjalnie zniszczyć stos, a inne rzadziej. może niektórzy są leniwi, inni chętni ... wszystkie szczegóły, na które należy zwrócić uwagę w Clojure, dlatego uważam, że większość nietrywialnych bibliotek nie jest dostarczana z powodu filozofii
jm0
3
Myślę, że powodem, dla którego nie ma tylko funkcji exp w rdzeniu, jest to, że wieża numeryczna Clojure jest poważnie zepsuta ze względu na wydajność. Jest więc wiele różnych rzeczy, które można rozumieć przez potęgowanie. Czym powinno być (exp 2 (exp 2 200))? Błąd lub duża liczba całkowita, której obliczenie wymaga wieku? Jeśli chcesz tylko zwykłego expa zmiennoprzecinkowego, to java jest wbudowany. Jeśli chcesz, aby język, w którym liczby starały się zachowywać jak liczby rzeczywiste i zawieszał koszt, użyj schematu zamiast clojure.
John Lawrence Aspden,

Odpowiedzi:

141

klasyczna rekurencja (patrz, wysadza stos)

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

rekurencja ogona

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

funkcjonalny

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

podstępny (również ciosy stosu, ale nie tak łatwo)

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

biblioteka

(require 'clojure.contrib.math)
John Lawrence Aspden
źródło
11
Zabawna odpowiedź!
Matt Fenwick
zobacz w pełni iteracyjną wersję podstępnego rozwiązania poniżej stackoverflow.com/a/22977674/231589
Karl Rosaen
5
Clojure.contrib.math jest teraz przestarzały, zobacz Math.Numeric-Tower
alvaro g
Druga sugestia (rekurencyjny ogon) ma przepełnienie liczb całkowitych dla n <0
Pointo Senshi
1
Fantastyczna odpowiedź. Oto jak to zrobić za pomocą makra: (defmacro exp [xn] `(* ~ @ (take n (repeat x))))
Daniel Szmulewicz
78

Clojure ma funkcję power, która działa dobrze: zalecam używanie tego zamiast przechodzenia przez interop w Javie, ponieważ poprawnie obsługuje wszystkie typy liczb Clojure o arbitralnej precyzji. Znajduje się w przestrzeni nazw clojure.math.numeric-tower .

To się nazywa exptdla potęgowania zamiast powerlub powktóre być może wyjaśnia, dlaczego jest to trochę trudne do znalezienia ... i tak oto mały przykład (uwaga, że useprace, ale lepsze wykorzystanie 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

Przypomnienie o instalacji pakietu

Musisz najpierw zainstalować pakiet Java, org.clojure.math.numeric-toweraby udostępnić przestrzeń nazw Clojure clojure.math.numeric-tower!

W linii poleceń:

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

Następnie edytuj project.clji dodaj [org.clojure/math.numeric-tower "0.0.4"]do wektora zależności.

Rozpocznij lein REPL (nie clojure REPL)

$ lein repl

Teraz:

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

lub

(require '[clojure.math.numeric-tower :as math :refer [expt]])
(expt 4 2)
;=> 16
mikera
źródło
1
Prawdopodobnie nieznane, ponieważ nie wydaje się być częścią standardowego Clojure. 1.3.0 wyświetla błędy dotyczące niemożności zlokalizowania pliku math.clj, gdy próbuję to zrobić w ten sposób.
Brian Knoblauch
9
Myślę, że jest teraz w "clojure.math.numeric-tower" od 1.3 (ponieważ clojure.contrib został podzielony na poszczególne biblioteki)
mikera
Dodano „przypomnienie o instalacji pakietu”, aby złagodzić frustrację użytkowników.
David Tonhofer
60

Możesz użyć java Math.powlub BigInteger.powmetod:

(Math/pow base exponent)

(.pow (bigint base) exponent)
sepp2k
źródło
+1, chociaż wiem, że możesz współpracować z bibliotekami java; jednak 1) Math.pow działa z wersjami podwójnymi, potrzebuję liczb całkowitych, czy możesz podać przykład? 2) Czy naprawdę musisz używać interop dla czegoś? proste jak uprawnienia?
Peter,
Clojure jest zbudowany wokół bibliotek java, nie próbuje naprawiać tego, co nie jest zepsute, a Math / pow działa dobrze. Dlaczego musisz dbać o pary lub liczby całkowite? Możesz również użyć tego richhickey.github.com/clojure-contrib/…
DaVinci,
1
@Peter: 1) Jeśli twoje moce nie są tak duże, że nie mogą być już dokładnie reprezentowane przez dublety, naprawdę nie ma problemu z rzuceniem wyniku na int. 2) Nie rozumiem, jak pisanie Math/powjest bardziej skomplikowane niż math-powczy jakakolwiek byłaby nazwa, gdyby istniał odpowiednik clojure. Jeśli istnieje już prosta metoda java, która robi to, co chcesz, nie ma powodu, aby odtwarzać tę funkcjonalność w clojure. Współpraca w języku Java nie jest z natury szkodliwa.
wrzesień
3
@Da vinci: dziwna uwaga, to własny język i ma wiele funkcji, które są w Javie (takie jak stringreverse)
Peter,
4
Myślę, że lepiej jest używać Clojure.contrib.math / expt, jeśli chcesz uzyskać dokładne moce biginteger. Prawdopodobnie robi to samo pod maską, ale znacznie przyjemniej niż przechodzenie przez interop w Javie .....
mikera
13

Kiedy pierwotnie zadano to pytanie, clojure.contrib.math / expt był oficjalną funkcją biblioteki, która to zrobiła. Od tego czasu przeniósł się do clojure.math.numeric-tower

amaloy
źródło
+1 dla tej odpowiedzi, ponieważ poprawnie obsługuje wszystkie dokładne arytmetyki Clojure (tj. BigDecimal / BigInteger).
mikera
8
user=> (.pow (BigInteger. "2") 10)
1024
user=> (.pow (BigInteger. "2") 100)
1267650600228229401496703205376
KIM Taegyoon
źródło
6
możesz również użyć do tego dosłownej notacji:(.pow 2M 100)
noisesmith
1
Ich typy są różne. user => (type 2M) java.math.BigDecimal user => (type (BigInteger. "2")) java.math.BigInteger
KIM Taegyoon
najlepsze rozwiązanie imo, showr, korzystanie z istniejących bibliotek, w tym obsługa biginta. +1
Daniel Gruszczyk
U mnie (Math/pow Math/E x)załatwia sprawę (wymiana Math/Ena wybraną przez Ciebie podstawę).
Zaz,
6

Jeśli naprawdę potrzebujesz funkcji, a nie metody, możesz ją po prostu opakować:

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

W tej funkcji możesz przesłać go do intlub podobnego. Funkcje są często bardziej przydatne niż metody, ponieważ można je przekazywać jako parametry do innych funkcji - w tym przypadku mapprzychodzi mi na myśl.

Jeśli naprawdę chcesz uniknąć współdziałania Java, możesz napisać własną funkcję Power. Na przykład jest to prosta funkcja:

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

To oblicza moc dla wykładnika będącego liczbą całkowitą (tj. Bez pierwiastków).

Ponadto, jeśli masz do czynienia z dużymi liczbami, możesz użyć BigIntegerzamiast int.

A jeśli masz do czynienia bardzo dużymi liczbami, możesz chcieć wyrazić je jako listy cyfr i napisać własne funkcje arytmetyczne, aby przesyłać je strumieniowo podczas obliczania wyniku i wyprowadzania wyniku do innego strumienia.

Goran Jovic
źródło
4

Myślę, że to też by działało:

(defn expt [x pow] (apply * (repeat pow x)))
TJ Trapp
źródło
ale wydaje się, że osiąga maksimum przy 2 ^ 63 ... zdecydowanie nie jest w stanie 2 ^ 200
TJ Trapp
4

SICP zainspirował pełną iteracyjną szybką wersję „podstępnej” implementacji powyżej.

(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
źródło
2

Implementacja metody „podstępnej” z rekurencją ogonową i obsługą wykładnika ujemnego:

(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)))))))
Tołstoyevsky
źródło
2

Prosta jedna linijka wykorzystująca redukuje:

(defn pow [a b] (reduce * 1 (repeat b a)))
Alan R. Soares
źródło
1

Próbować

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

dla rozwiązania ogonowo-rekurencyjnego O (log n), jeśli chcesz je zaimplementować samodzielnie (obsługuje tylko dodatnie liczby całkowite). Oczywiście lepszym rozwiązaniem jest użycie funkcji biblioteki, które wskazali inni.

Retief
źródło
0

A co z clojure.contrib.genric.math-functions

W bibliotece clojure.contrib.generic.math-functions znajduje się funkcja pow. Jest to po prostu makro dla Math.pow i bardziej "clojureish" sposób wywoływania funkcji matematycznej Java.

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

fido
źródło