I spent some time yesterday writing the solution for this challenge published on Reddit, and was able to get through it without cheating, but I was left with a couple of questions. Reference material here.
This is my code.
(ns baking-pi.core
(:import java.math.MathContext))
(defn modpow [n e m]
(.modPow (biginteger n) (biginteger e) (biginteger m)))
(defn div [top bot]
(with-precision 34 :rounding HALF_EVEN
(/ (bigdec top) (bigdec bot))))
(defn pow [n e]
(.pow (bigdec n) (bigdec e) MathContext/DECIMAL128))
(defn round
([n] (.round (bigdec n) MathContext/DECIMAL128))
([n & args] (->> [n args] (flatten) (map round))))
(defn left [n d]
(letfn [(calc [k] (let [bot (+' (*' 8 k) d)
top (modpow 16 (-' n k) bot)]
(div top bot)))]
(->> (inc' n)
(range 0)
(map calc)
(reduce +'))))
(defn right [n d]
(letfn [(calc [[sum'' sum' k]]
(let [sum' (if (nil? sum') 0M sum')
top (pow 16 (-' n k))
bot (+' (*' k 8) d)
delta (div top bot)]
[sum' (+' sum' delta) (inc' k)]))
(pred [[sum'' sum' k]]
(cond (or (nil? sum'') (nil? sum')) true
(apply == (round sum'' sum')) false
:else true))]
(->> [nil nil (inc' n)]
(iterate calc)
(drop-while pred)
(first)
(second))))
(defn bbp [n]
(letfn [(part [m d] (*' m (+' (left n d) (right n d))))]
(let [sum (-' (part 4 1) (part 2 4) (part 1 5) (part 1 6))]
(-> sum
(-' (long sum))
(*' 16)
(mod 16)
(Long/toHexString)))))
I have 2 questions.
The wiki makes the following statement. Since my calculation is accurate up to 34 digits after the decimal, how can I leverage it to produce more hexadecimal digits of PI per bbp call?
in theory, the next few digits up to the accuracy of the calculations used would also be accurate
My algorithm relied on BigInteger's modPow for modular exponentiation (based on the following quote), and BigDecimals everywhere else. It is also slow. Bearing in mind that I don't want to lose meaningful accuracy per question #1, what is the best way to speed this program up and make it valid clojurescript as well as clojure?
To calculate 16 n − k mod (8k + 1) quickly and efficiently, use the modular exponentiation algorithm.
EDIT: Changed from 3 questions to 2. Managed to answer first question on my own.