Подтвердить что ты не робот

Как сделать экспоненциацию в clojure?

Как я могу сделать экспоненцию в clojure? На данный момент мне нужно только целочисленное возведение в степень, но вопрос идет и о фракциях.

4b9b3361

ОТВЕТЫ

Ответ 1

классическая рекурсия (смотри, это ударяет стек)

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

sneaky (также ударяет стек, но не так легко)

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

Ответ 2

У Clojure есть мощная функция, которая работает хорошо: я бы рекомендовал использовать ее вместо взаимодействия с Java, поскольку он правильно обрабатывает все числовые типы Clojure с произвольной точностью.

Он вызвал expt для возведения в степень, а не power или pow что, возможно, объясняет, почему его немного трудно найти... в любом случае, вот небольшой пример:

(use 'clojure.math.numeric-tower)  ; as of Clojure 1.3
;; (use 'clojure.contrib.math)     ; before Clojure 1.3

(expt 2 200)
=> 1606938044258990275541962092341162602522202993782792835301376

Ответ 3

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

(Math/pow base exponent)

(.pow (bigint base) exponent)

Ответ 4

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

Ответ 5

user=> (.pow (BigInteger. "2") 10)
1024
user=> (.pow (BigInteger. "2") 100)
1267650600228229401496703205376

Ответ 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.

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

Ответ 7

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

(defn expt [x pow] (apply * (repeat pow x)))

Ответ 8

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

Ответ 10

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

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

Ответ 11

Простой однострочник, использующий уменьшение:

(defn pow [a b] (reduce * 1 (repeat b a)))

Ответ 12

Try

(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), если вы хотите реализовать его самостоятельно (поддерживает только положительные целые числа). Очевидно, лучшее решение - использовать библиотечные функции, которые другие указали.