Как сделать возведение в степень в Clojure?

106

Как я могу выполнить возведение в степень в Clojure? Пока мне нужно только целочисленное возведение в степень, но вопрос касается и дробей.

Питер
источник
18
Как человек, который не знает clojure, но предрасположен любить его (фанат шепелявости, функционального программирования и наличия множества удобных библиотек), я разочарован тем, что на этот простой вопрос так много ответов - или что он вообще нужно было спросить. Я бы подумал, что возведение в степень будет просто одной из основных предоставляемых функций без необходимости делать что-либо особенное. Но я рад, что об этом спросили.
Марс
1
ну да, наверное, какая-то его версия должна быть в ядре ... но я думаю, что многие ответы по-прежнему являются хорошим знаком. "множественные пути к реализации", кажется, являются причиной того, что многие из этих вещей не предоставляются - пользователь должен знать детали функции, которую он использует, для повышения эффективности. например (как указано в выбранном ответе) одни способы потенциально могут взорвать стек, другие - с меньшей вероятностью. возможно, некоторые ленивы, некоторые нетерпеливы ... все детали, на которые нужно обратить внимание в Clojure, поэтому я считаю, что большинство нетривиальных библиотек не предоставляются из-за философии
jm0
3
Я думаю, что причина, по которой в ядре есть не только функция exp, заключается в том, что числовая башня clojure сильно сломана из соображений эффективности. Таким образом, под возведением в степень вы можете понимать множество разных вещей. Что должно быть (exp 2 (exp 2 200))? Ошибка или огромное целое число, для вычисления которого требуется возраст? Если вам просто нужно обычное выражение с плавающей запятой, тогда встроено java. Если вам нужен язык, в котором числа делают все возможное, чтобы действовать как вещественные числа и зависеть от стоимости, используйте схему вместо clojure.
Джон Лоуренс Аспден

Ответы:

141

классическая рекурсия (смотри, она взрывает стек)

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

хвостовая рекурсия

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

функциональный

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

подлый (тоже сдувает стек, но не так легко)

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

библиотека

(require 'clojure.contrib.math)
Джон Лоуренс Аспден
источник
11
Занимательный ответ!
Мэтт Фенвик
см. полностью итеративную версию скрытого решения ниже stackoverflow.com/a/22977674/231589
Карл Росаен
5
Clojure.contrib.math теперь устарел, см. Math.Numeric-Tower
alvaro g
Второе предложение (хвостовая рекурсивная) имеет целочисленное переполнение для n <0.
Pointo Senshi
1
Фантастический ответ. Вот как это сделать с помощью макроса: (defmacro exp [xn] `(* ~ @ (take n (repeat x))))
Даниэль Шмулевич
78

В Clojure есть функция мощности, которая работает хорошо: я бы рекомендовал использовать ее вместо взаимодействия с Java, поскольку она правильно обрабатывает все числовые типы произвольной точности Clojure. Он находится в пространстве имен clojure.math.numeric-tower .

Это называется exptдля потенцирования , а не powerили , powкоторые , возможно , объясняет , почему это немного трудно найти ... в любом случае , вот небольшой пример (обратите внимание , что useработает , но лучше использовать 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

Напоминание об установке пакета

Вы должны сначала установить пакет Java, org.clojure.math.numeric-towerчтобы сделать пространство имен Clojure clojure.math.numeric-towerдоступным!

В командной строке:

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

Затем отредактируйте project.cljи добавьте [org.clojure/math.numeric-tower "0.0.4"]в вектор зависимостей.

Запустите lein REPL (не закрытый REPL)

$ lein repl

Сейчас:

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

или

(require '[clojure.math.numeric-tower :as math :refer [expt]])
(expt 4 2)
;=> 16
Микера
источник
1
Вероятно, неизвестно, потому что, похоже, он не является частью стандартного Clojure. 1.3.0 выдает ошибки о том, что я не могу найти math.clj, когда я пытаюсь сделать это таким образом.
Брайан Ноблауч
9
Я думаю, что теперь он находится в "clojure.math.numeric-tower" версии 1.3 (поскольку clojure.contrib разбит на отдельные библиотеки)
mikera
Добавлено «напоминание об установке пакета», чтобы развеять недовольство пользователя.
Дэвид Тонхофер
61

Вы можете использовать методы java Math.powили BigInteger.pow:

(Math/pow base exponent)

(.pow (bigint base) exponent)
sepp2k
источник
+1, хотя я знаю, что вы можете взаимодействовать с java libs; однако 1) Math.pow работает с двойными числами, мне нужны целые числа, вы можете привести пример? 2) Вам действительно нужно использовать взаимодействие для чего-то? просто как полномочия?
Питер
Clojure построен на java-библиотеках, он не пытается исправить то, что не сломано, и Math / pow отлично работает. Почему вам нужно заботиться о двойных или целых числах? Вы также можете использовать этот richhickey.github.com/clojure-contrib/…
DaVinci
1
@Peter: 1) Если ваши полномочия не настолько велики, что они больше не могут быть точно представлены двойниками, действительно нет проблем с простым приведением результата к int. 2) Я не понимаю, насколько написание Math/powсложнее, чем имя math-powили какое бы то ни было имя, если бы существовал эквивалент clojure. Если уже существует простой java-метод, который делает то, что вы хотите, нет причин воссоздавать функциональность в clojure. Взаимодействие Java по своей сути не вредно.
sepp2k
3
@Da vinci: странное замечание, это собственный язык и множество функций на Java (например, stringreverse)
Питер,
4
Я думаю, вам лучше использовать Clojure Clojure.contrib.math / expt, если вам нужны точные бигинтегральные полномочия. Вероятно, делает то же самое под капотом, но намного лучше, чем через взаимодействие с Java .....
mikera
13

Когда этот вопрос был первоначально задан, clojure.contrib.math / expt была официальной библиотечной функцией для этого. С тех пор он переехал в clojure.math.numeric-tower.

сплав
источник
+1 за этот ответ, поскольку он правильно обрабатывает всю точную арифметику Clojure (то есть BigDecimal / BigInteger).
mikera
"Примечание - дополнительные библиотеки перемещены в отдельные репозитории в Clojure org" ; эта ссылка только ответ сейчас вводит в заблуждение.
Брэд Кох
8
user=> (.pow (BigInteger. "2") 10)
1024
user=> (.pow (BigInteger. "2") 100)
1267650600228229401496703205376
КИМ Тэгён
источник
6
также вы можете использовать буквальное обозначение для этого:(.pow 2M 100)
noisesmith
1
Типы у них разные. user => (type 2M) java.math.BigDecimal user => (type (BigInteger. "2")) java.math.BigInteger
KIM Taegyoon
Лучшее решение imo, showr, с использованием существующих библиотек, включая обработку bigint. +1
Daniel Gruszczyk
Для меня (Math/pow Math/E x)это главное (замена Math/Eна базу по вашему выбору).
Zaz
6

Если вам действительно нужна функция, а не метод, вы можете просто обернуть ее:

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

И в этой функции вы можете преобразовать его в intили подобное. Функции часто более полезны, чем методы, потому что вы можете передавать их в качестве параметров другим функциям - в этом случае mapмне приходит в голову.

Если вам действительно нужно избегать взаимодействия с Java, вы можете написать свою собственную функцию мощности. Например, это простая функция:

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

Это вычисляет мощность для целой экспоненты (т.е. без корней).

Кроме того, если вы имеете дело с большими числами, вы можете использовать BigIntegerвместо int.

А если вы имеете дело с очень большими числами, вы можете выразить их в виде списков цифр и написать свои собственные арифметические функции для потоковой передачи по ним, когда они вычисляют результат и выводят результат в какой-то другой поток.

Горан Йович
источник
4

Думаю, это тоже сработает:

(defn expt [x pow] (apply * (repeat pow x)))
TJ Trapp
источник
но, кажется, достигает максимума на 2 ^ 63 ... def не способен на 2 ^ 200
TJ Trapp
4

SICP вдохновил на создание полной итеративной быстрой версии «скрытой» реализации, описанной выше.

(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)))
Карл Розаен
источник
2

Реализация "хитрого" метода с хвостовой рекурсией и поддерживающей отрицательной экспонентой:

(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)))))))
Толстоевский
источник
2

Простой однострочник с использованием reduce:

(defn pow [a b] (reduce * 1 (repeat b a)))
Алан Р. Соарес
источник
1

Пытаться

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

для решения с хвостовой рекурсией O (log n), если вы хотите реализовать его самостоятельно (поддерживает только положительные целые числа). Очевидно, что лучшим решением будет использование функций библиотеки, на которые указали другие.

Retief
источник
0

Как насчет clojure.contrib.genric.math-functions

В библиотеке clojure.contrib.generic.math-functions есть функция pow. Это всего лишь макрос для Math.pow и более «банальный» способ вызова математической функции Java.

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

фидо
источник