Baking-Pi挑战 - 了解&改进 [英] Baking-Pi Challenge - Understanding & Improving

问题描述

我花了一段时间，昨天写了这个挑战发布在Reddit ，并能够通过它没有作弊，但我留下了几个问题。 此处的参考资料。

这是我的代码。

 （ns baking-pi.core 
 （：import java.math.MathContext））
 
（defn modpow [nem] 
（.modPow（biginteger n）（biginteger e）（biginteger m）））
 b $ b（defn div [top bot] 
（with-precision 34：rounding HALF_EVEN 
（/ bigdec top）（bigdec bot））））
 
 [ne] 
（.pow（bigdec n）（bigdec e）MathContext / DECIMAL128））
 
（defn round 
（[n] / DECIMAL128））
（[n& args]（ - >> [n args]（flatten）（map round））））
 
（defn left [nd] b $ b（letfn [（calc [k]（let [bot（+'（*'8 k）d）
 top（modpow 16（ - 'nk）bot）] 
 ）））] 
（ - >>（inc'n）
（范围0）
（map calc）
（reduce +'））））
 
（defn right [nd] 
（letfn [（calc [[sum''sum'k]] 
（let [sum' sum'）0M sum'）
 top（pow 16（ - 'nk））
 bot（+'（*'k 8）d）
 delta $ b [sum'（+'sum'delta）（inc'k）]））
（pred [[sum''sum'k]] 
 ）（nil？sum'））true 
（apply ==（round sum''sum'））false 
：else true））] 
（ - > （inc'n）] 
（iterate calc）
（drop-while pred）
（first）
（second））））
 
 defn bbp [n] 
（let [ - （第4部分） 1）（part 2 4）（part 1 5）（part 1 6））] 
（ - > sum 
（ - '（long sum））
（*'16）
（mod 16）
（Long / toHexString）））））
  

有2个问题。

1. 维基作如下声明。由于我的计算精确到十进制之后的34位数，我如何利用它来生成每个bbp调用更多的PI的十六进制数字？

   
   

   我的算法依赖于BigInteger的modPow进行模幂运算（基于以下引用），BigDecimals在其他地方。它也很慢。记住，我不想失去有意义的精度每个问题＃1，什么是加速这个程序，使有效的clojurescript和clojure有效的方法？

   
   

   要快速有效地计算16 n-k mod（8k + 1），请使用
   模幂运算。

   
   

   li>
   

编辑：从3个问题更改为2.自行管理以回答第一个问题。

解决方案

1. 如果您希望每次bpp调用计算更多位

   >
   
   

   那么你必须将你的方程式从 1 /（16 ^ k）更改为更大的。你可以通过 2 迭代（ k 和 k + 1 $ c>），所以你有类似

    （...）/ 16 ^ k + ^（k + 1）
   （...）/ 256 ^ k 
     

   这种情况下你需要更精确的 int 操作。使用不太精确的迭代通常会更快。




2. 如果您查看基本方程，则可以看到不需要 bigint 用于所有计算

   
   
   

   这就是为什么使用此迭代，但输出数字 bigint 当然。所以你不需要在 bigint 上计算模算术。

   
   
   

   我不知道如何优化你的使用...但这里是我的：

   
   
   
   
   
   • 
     


如果你想要速度而不是无限精度，那么使用其他PSLQ方程




我理解 PSLQ 是算法来找到实数和整数迭代之间的关系。






• 这里是我最喜欢的PSLQ上到800个Pi的数字






，这里是从中提取的代码，以防链接崩溃

  //以下160个字符的C程序由CWI的Dik T.Winter写，计算pi到800个十进制数。 
 int a = 10000，b，c = 2800，d，e，f，g; main（）{for（; b-c;）f [b ++] 
 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）;} 
  pre>  
 




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.

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

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

解决方案

1. if you want more bits computed per bpp call

   then you have to change your equation from 1/(16^k) base to bigger one. You can do it by summing 2 iterations (k and k+1) so you have something like

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

   but in this case you need more precise int operations. It is usually faster to use the less precise iterations

2. if you look at the basic equation then you see you do not need bigint for computation at all

   that is why this iterations are used but the output number is bigint of course. So you do not need to compute modular arithmetics on bigint.

   I do not know how optimized are the one you used ... but here are mine:

   • Modular arithmetics and finite field NTT optimizations

3. if you want just speed and not infinite precision then use other PSLQ equations

   My understanding of PSLQ is that it is algorithm to find relation between real number and integer iterations.

   • here is my favourite PSLQ up to 800 digits of Pi

   and here is extracted code from it in case the link broke down

   //The following 160 character C program, written by Dik T. Winter at CWI, computes pi  to 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);}
   

这篇关于Baking-Pi挑战 - 了解&改进的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！