Baking-Pi Challenge — понимание и совершенствование

Вчера я потратил некоторое время на написание решения для этого задания, опубликованного на Reddit. , и смог пройти его без читерства, но у меня осталась пара вопросов. Справочные материалы здесь.

Это мой код.

(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 вопроса.

  1. #P4# <блочная цитата> #P5#
  2. #P6# <блочная цитата> #P7#

EDIT: изменено с 3 вопросов на 2. Мне удалось самостоятельно ответить на первый вопрос.


clojure reddit math clojurescript pi
person crinklywrappr    schedule 10.03.2014    source источник

Ответы (1)


arrow_upward
2
arrow_downward

  1. если вы хотите, чтобы при каждом вызове bpp вычислялось больше битов

    тогда вам нужно изменить уравнение с 1/(16^k) основания на большее. Вы можете сделать это, просуммировав 2 итераций (k и k+1), чтобы у вас было что-то вроде

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

    но в этом случае вам нужны более точные int операции. Обычно быстрее использовать менее точные итерации.

  2. если вы посмотрите на основное уравнение, то увидите, что вам вообще не нужно bigint для вычислений

    поэтому используются эти итерации, но выходной номер, конечно, bigint. Таким образом, вам не нужно вычислять модульную арифметику на bigint.

    Я не знаю, насколько оптимизированы те, которые вы использовали ... но вот мои:

  3. если вам нужна только скорость, а не бесконечная точность, используйте другие уравнения PSLQ

    Мое понимание PSLQ состоит в том, что это алгоритм для нахождения связи между действительными числами и целочисленными итерациями.

вот мой любимый до 800 цифр алгоритма Пи и вот извлеченный из него код на случай, если ссылка сломалась:

//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);}
person Spektre    schedule 10.03.2014
comment
Суммирование двух операций приводит к общему знаменателю 16^(k+1)=16*16^k, а не 32^k=(2^k)*(16^k). - person Lutz Lehmann; 10.03.2014
comment
Сила связывает сильнее, чем умножение, 16*16^k равно 16*(16^k), а не (16*16)^k. Конечно, если сложить члены от k или k+1 до 2k, то общий знаменатель будет 16^(2k)=256^k. - person Lutz Lehmann; 10.03.2014
comment
16^(2*k) = 256^k и 16^(2*k+1) = 16*(256^k) хотя. Таким образом, используя нечетность/четность последовательных терминов, вы можете получить выражение со знаменателем 256^n. - person omiel; 16.03.2014
comment
Насколько я знаю, приложенный вами код на C вообще не является алгоритмом PSLQ. В исходной статье говорилось о разных методах, а короткая программа на C была прикреплена в конце просто потому, что это крутая программа, а не потому, что это PSLQ. Я могу быть уверен, так как ">Я только что переделал его. Код использует старомодный ряд arctan() в 32-битной арифметике с фиксированной точкой и вычисляет 4 десятичных знака за итерацию, см. crypto.stanford.edu/pbc/notes/pi/code.html. - person 比尔盖子; 08.05.2019