我昨天花了一些时间写 this challenge published on Reddit 的解决方案,并且能够在没有作弊的情况下完成它,但我留下了几个问题。 Reference material here .
这是我的代码。
(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)))))
我有 2 个问题。
维基百科做出以下声明。由于我的计算精确到小数点后 34 位,我如何利用它为每个 bbp 调用生成更多十六进制数字的 PI?
in theory, the next few digits up to the accuracy of the calculations used would also be accurate
我的算法依赖于 BigInteger 的 modPow 进行模幂运算(基于以下引用),以及其他任何地方的 BigDecimals。它也很慢。请记住,我不想失去每个问题 #1 的有意义的准确性,加速该程序并使其有效的 clojurescript 和 clojure 的最佳方法是什么?
To calculate 16 n − k mod (8k + 1) quickly and efficiently, use the modular exponentiation algorithm.
编辑:从 3 个问题改为 2 个问题。我自己设法回答了第一个问题。
最佳答案
如果您希望每次 bpp 调用计算更多位数
那么你必须将方程从
1/(16^k)
基数更改为更大的基数。您可以通过对2
次迭代(k
和k+1
)求和来实现,这样您就可以得到类似(...)/16^k + (...)/16^(k+1) (...)/256^k
但在这种情况下,您需要更精确的
int
运算。使用不太精确的迭代通常会更快如果您查看基本方程,您会发现根本不需要
bigint
进行计算这就是使用此迭代的原因,但输出数字当然是
bigint
。因此,您不需要在bigint
上计算模算术。我不知道你使用的优化程度如何......但这是我的:
如果您只想要速度而不是无限精度,请使用其他 PSLQ 方程
我对PSLQ的理解是一种寻找实数和整数迭代之间关系的算法。
这是我最喜欢的800 digits of Pi algorithm这里是从中提取的代码,以防链接中断:
//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);}
关于math - Baking-Pi 挑战 - 理解和改进,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/22291515/