optimization - 循环函数花费的时间太长

Question

我正在尝试实现一个实现n 个立方体之和的函数:

1^3 + 2^3 + 3^3 + ... + n^3 = sum

我的函数应该接收一个 sum 并返回一个 n 或 -1(如果 n 不存在) .

一些例子:

(find-n 9)   ; should return 2 because 1^3 + 2^3 = 9
(find-n 100) ; should return 4 because 1^3 + 2^3 + 3^3 + 4^3 = 100
(find-n 10)  ; should return -1

经过一些工作，我制作了这两个函数:

; aux function
(defn exp-3 [base] (apply *' (take 3 (repeat base))))

; main function
(defn find-n [m]
  (loop [sum 0
         actual-base 0]
       (if (= sum m) 
           actual-base
           (if (> sum m)
               -1
               (recur (+' sum (exp-3 (inc actual-base))) (inc actual-base))))))

这些函数工作正常，但使用 BigNumbers 评估操作花费的时间太长，例如:

(def sum 1025247423603083074023000250000N)
(time (find-n sum))
; => "Elapsed time: 42655.138544 msecs"
; => 45001000

我问这个问题是为了提出一些关于如何使这个功能更快的建议。

Answer 1

这都是关于代数的，与 Clojure 或编程无关。由于这个网站不支持数学排版，所以我们用 Clojure 来表达它。

定义

(defn sigma [coll] (reduce + coll))

和

(defn sigma-1-to-n [f n]
  (sigma (map f (rest (range (inc n))))))

(或

(defn sigma-1-to-n [f n]
  (->> n inc range rest (map f) sigma))

)

那么问题是，给定 n，找到 i 使得 (= (sigma-1-to-n #(* % % %) i) n)。

快速完成此操作的关键是 Faulhaber's formula对于立方体。它告诉我们，对于任何自然数 i，以下内容都是相等的:

(#(*' % %) (sigma-1-to-n identity i))

(sigma-1-to-n #(* % % %) i)

(#(*' % %) (/ (*' i (inc i)) 2))

所以，作为立方之和，数字

• 必须是完全正方形
• 其平方根是前这么多数字的总和。

为了确定一个整数是否是完全平方数，我们取其近似的浮点平方根，然后看看对最接近的整数进行平方是否可以恢复我们的整数:

(defn perfect-square-root [n]
  (let [candidate (-> n double Math/sqrt Math/round)]
    (when (= (*' candidate candidate) n)
      candidate)))

如果参数不是完全平方数，则返回nil。

现在我们有了平方根，我们必须确定它是否是一系列自然数的和:在普通代数中，是(j (j + 1))/2 ，对于某个自然数j。

我们可以使用类似的技巧来直接回答这个问题。

j (j + 1) = (j + 1/2)^2 + 1/4

因此，以下函数返回与参数相加的连续数字的数量(如果有):

(defn perfect-sum-of [n]
  (let [j (-> n (*' 2)
                (- 1/4)
                double
                Math/sqrt
                (- 0.5)
                Math/round)]
    (when (= (/ (*' j (inc j)) 2) n)
      j)))

我们可以结合这些来完成您想要的操作:

(defn find-n [big-i]
  {:pre [(integer? big-i) ((complement neg?) big-i)]}
  (let [sqrt (perfect-square-root big-i)]
    (and sqrt (perfect-sum-of sqrt))))

(def sum 1025247423603083074023000250000N)

(time (find-n sum))
"Elapsed time: 0.043095 msecs"
=> 45001000

(请注意，时间比以前快了大约二十倍，可能是因为 HotSpot 必须在 find-n 上工作，该功能已通过附加测试进行了彻底的测试)

这显然比原来快很多。

<小时/>

警告

由于浮点精度有限，我担心上述过程可能会产生误报(它永远不会产生误报)。然而，测试表明，对于问题所使用的数字类型，该过程是牢不可破的。

<小时/>

Java double 具有 52 位精度，大约为 15.6 位小数。令人担忧的是，对于比这大得多的数字，该过程可能会错过精确的整数解，因为舍入只能与它开始的 float 一样准确。

但是，该过程可以正确求解 31 位整数的示例。并且用许多(一千万!)相似的数字进行测试不会产生任何失败。

<小时/>

为了测试解决方案，我们生成一个(惰性)[limitcube-sum] 对序列:

(defn generator [limit cube-sum]
  (iterate
    (fn [[l cs]]
      (let [l (inc l)
            cs (+' cs (*' l l l))]
        [limit cs]))
    [limit cube-sum]))

例如，

(take 10 (generator 0 0))
=> ([0 0] [1 1] [2 9] [3 36] [4 100] [5 225] [6 441] [7 784] [8 1296] [9 2025])

现在我们

• 从给定的示例开始，
• 尝试接下来的一千万个案例
• 删除那些有效的。

所以

(remove (fn [[l cs]] (= (find-n cs) l)) (take 10000000 (generator 45001000 1025247423603083074023000250000N)))
=> () 

它们都有效。没有失败。只是为了确保我们的测试有效:

(remove (fn [[l cs]] (= (find-n cs) l)) (take 10 (generator 45001001 1025247423603083074023000250000N)))
=>
([45001001 1025247423603083074023000250000N]
 [45001002 1025247514734170359564546262008N]
 [45001003 1025247605865263720376770289035N]
 [45001004 1025247696996363156459942337099N]
 [45001005 1025247788127468667814332412224N]
 [45001006 1025247879258580254440210520440N]
 [45001007 1025247970389697916337846667783N]
 [45001008 1025248061520821653507510860295N]
 [45001009 1025248152651951465949473104024N]
 [45001010 1025248243783087353664003405024N])

一切都应该失败，他们也确实失败了。