Loop function takes too long

Question

I am trying to execute a function that implements the sum of n cubes:

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

My function should receive sumand return, nor -1if it ndoes not exist.

Some examples:

(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

After some work, I did the following two functions:

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

These functions work fine, but take too long to evaluate operations using BigNumbers, for example:

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

I am asking this question to raise some tips on how to make this feature faster.

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

, , .

---

Caveat

, ( ) - . , , , .

---

Java double 52 , 15.6 . , , , , , , , .

31- . ( !) .

---

, () [limit cube-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])

, .

Answer 2

apply ( CLJ) 4- :

(defn exp-3 [base]
  (*' base base base))

10%:

(defn find-n [m]
  (loop [sum 0
         actual-base 0]
    (if (>= sum m)
      (if (= sum m) actual-base -1)
      (let [nb (inc actual-base)]
        (recur (+' sum (*' nb nb nb)) nb)))))

Answer 3

, , N : (N*(N+1)/2)^2

(defn sum-of-cube
  "(n*(n+1)/2)^2"
  [n]
  (let [n' (/ (*' n (inc n)) 2)]
    (*' n' n')))

(defn find-nth-cube
  [n]
  ((fn [start end prev]
     (let [avg (bigint (/ (+' start end) 2))
           cube (sum-of-cube avg)]
       (cond (== cube n) avg
             (== cube prev) -1
             (> cube n) (recur start avg cube)
             (< cube n) (recur avg end cube))))
    1 n -1))

(time (find-nth-cube 1025247423603083074023000250000N))
"Elapsed time: 0.355177 msecs"
=> 45001000N

N , 1..N X. , , , ., X. , , , , f(n), , , n, f(n), , , n.

(, , ) 0 X. , , , , X. , , , , , .

logN 1 1E100 (1 googol), .

Answer 4

.

(a-k)^3 + (a+k)^3 = 2a^3+(6k^2)a

, :

(a-4)^3+(a-3)^3+(a-2)^3+(a-1)^3+a^3+(a+1)^3+(a+2)^3+(a+3)^3+(a+4)^3 
= 9a^3+180a

(, ).

Using this equation, instead of increasing by 1 each time, you can jump by 9 (or any 2 k + 1 you like). You can check the exact number when you press a larger number than n.

Another way to improve is to have a table ns and sums, having done a batch of calculations once and using this table later in the find-n function.