对一个非常大的 BigInteger 求平方非常慢

Question

我正在努力完成 2022 年的代码降临，我在 第 11 天第 2 部分。

我有这个解决方案：

(ns advent-of-code-2022.day11
  (:require [taoensso.timbre :as log]))

(declare give-monkey-item)
(defrecord Monkey [items operation throw-item num-inspections])

(defn create-monkey [items operation divisor monkey-true monkey-false]
  (->Monkey
    items
    operation
    (fn [item monkeys]
      (if (= (mod item divisor) 0)
        (give-monkey-item item monkeys monkey-true)
        (give-monkey-item item monkeys monkey-false)))
    0))

(defn give-monkey-item [item monkeys catcher]
  (update-in monkeys [catcher :items] #(conj % item)))

(defn throw-items [monkeys current-monkey]
  (reduce (fn [monkeys item]
            (-> item
                (biginteger)
                ((.operation current-monkey))
                ((.-throw_item current-monkey) monkeys)))
      monkeys
      (.items current-monkey)))

(defn adjust-current-monkeys-inspections [monkeys current-monkey-index]
  (let [current-monkey (get monkeys current-monkey-index)
        num-items (count (.items current-monkey))]
    (update-in monkeys [current-monkey-index :num-inspections] #(+ % num-items))))

(defn clear-current-monkeys-items [monkeys current-monkey-index]
  (let [current-monkey (get monkeys current-monkey-index)
        itemless-monkey (assoc current-monkey :items [])]
    (assoc monkeys current-monkey-index itemless-monkey)))

(defn play-turn [monkeys current-monkey-index]
  (let [current-monkey (get monkeys current-monkey-index)]
    (-> monkeys
        (throw-items current-monkey)
        (adjust-current-monkeys-inspections current-monkey-index)
        (clear-current-monkeys-items current-monkey-index))))

(defn play-round [monkeys]
  (reduce (fn [monkeys monkey-index]
            (play-turn monkeys monkey-index))
          monkeys
          (range (count monkeys))))

(defn play-rounds [monkeys num-rounds]
  (reduce (fn [rounds round-number]
            (log/info round-number)
            (let [latest-monkeys (last rounds)]
              (conj rounds (play-round latest-monkeys))))
          [monkeys]
          (range num-rounds)))

(defn calculate-monkey-business [monkeys num-rounds]
  (let [rounds (play-rounds monkeys num-rounds)]
    (->> (last rounds)
         (map #(.-num_inspections %))
         (sort)
         (reverse)
         (take 2)
         (reduce *))))

我正在使用此代码对其进行测试：

(ns advent-of-code-2022.day11-test
  (:require [clojure.test :refer :all]
            [advent-of-code-2022.day11 :refer :all]))

(def monkeys
  [(create-monkey
     [54 98 50 94 69 62 53 85]
     (fn [old] (* old 13))
     3 2 1)
   (create-monkey
     [71 55 82]
     (fn [old] (+ old 2))
     13 7 2)
   (create-monkey
     [77 73 86 72 87]
     (fn [old] (+ old 8))
     19 4 7)
   (create-monkey
     [97 91]
     (fn [old] (+ old 1))
     17 6 5)
   (create-monkey
     [78 97 51 85 66 63 62]
     (fn [old] (* old 17))
     5 6 3)
   (create-monkey
     [88]
     (fn [old] (+ old 3))
     7 1 0)
   (create-monkey
     [87 57 63 86 87 53]
     (fn [old] (.pow old 2)) ; this is slow for big numbers
     11 5 0)
   (create-monkey
     [73 59 82 65]
     (fn [old] (+ old 6))
     2 4 3)
   ])

(deftest day11-full-test-part2
  (testing "day11-full-test-part2"
    (is (= (calculate-monkey-business monkeys 10000) 10605))))

这尝试运行 10000 次迭代，但在第 200 次迭代左右，测试代码中标记的函数

(fn [old] (.pow old 2))

开始对非常大的 BigIntegers 求平方并且变得非常慢。它太慢了，程序可能需要几天才能完成。如果我将

.pow

替换为简单的

+

，程序将在几秒钟内完成。

.pow

是我试过的最新功能；我从一个简单的

(* old old)

开始，也尝试了

clojure.math.numeric-tower/expt

，但是三个都有这个问题。

有没有办法在 Clojure 中有效地对这些大的 BigIntegers 求平方？