math - Baking-Pi Challenge - Understanding & Improving -

i spent time yesterday writing solution this challenge published on reddit, , able through without cheating, left couple of questions. reference material here.

this 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.

1. the wiki makes following statement. since calculation accurate 34 digits after decimal, how can leverage produce more hexadecimal digits of pi per bbp call?

   in theory, next few digits accuracy of calculations used accurate

2. my algorithm relied on biginteger's modpow modular exponentiation (based on following quote), , bigdecimals everywhere else. slow. bearing in mind don't want lose meaningful accuracy per question #1, best way speed program , make valid clojurescript clojure?

   to calculate 16 n − k mod (8k + 1) , efficiently, use modular exponentiation algorithm.

edit: changed 3 questions 2. managed answer first question on own.

1. if want more bits computed per bpp call

   then have change equation 1/(16^k) base bigger one. can summing 2 iterations (k , k+1) have like

   (...)/16^k  + (...)/16^(k+1) (...)/256^k 

   but in case need more precise int operations. faster use less precise iterations

2. if @ basic equation see not need bigint computation @ all

   that why iterations used output number bigint of course. not need compute modular arithmetics on bigint.

   i not know how optimized 1 used ... here mine:

   • modular arithmetics , finite field ntt optimizations

3. if want speed , not infinite precision use other pslq equations

   my understanding of pslq is algorithm find relation between real number , integer iterations.

   • here favourite pslq 800 digits of pi

   and here extracted code in case link broke down

   //the following 160 character c program, written dik t. winter @ cwi, computes pi  800 decimal digits.  int a=10000,b,c=2800,d,e,f[2801],g;main(){for(;b-c;)f[b++]=a/5; for(;d=0,g=c*2;c-=14,printf("%.4d",e+d/a),e=d%a)for(b=c;d+=f[b]*a,f[b]=d%--g,d/=g--,--b;d*=b);}