Требуемая точность работы для алгоритма BBP?

Question

Я ищу, чтобы вычислить n-я цифра Pi в среде с низкой памятью. Поскольку у меня нет десятичных знаков, это integer-only BBP algorithm in Python было отличной отправной точкой. Мне нужно только вычислить одну цифру Pi за раз. Как определить самый низкий, который я могу установить D, «количество цифр рабочей точности»?

D = 4 дает мне много правильных цифр, но несколько цифр будут отключены одним. Например, вычисление цифры 393 с точностью 4 дает мне 0xafda, из которой я извлекаю цифру 0xa. Однако правильная цифра равна 0xb.

Независимо от того, насколько высок я устанавливаю D, кажется, что тестирование достаточного количества цифр находит тот, где формула возвращает неверное значение.

Я попытался повысить точность, когда цифра «близка» к другой, например. 0x3fff или 0x1000, но не может найти хорошего определения «close»; например, вычисление на цифре 9798 дает мне 0x c de6, который не очень близок к 0xd000, но правильная цифра равна 0xd.

Может ли кто-нибудь помочь мне выяснить, какая рабочая точность необходима для вычисления данной цифры с использованием этого алгоритма?

Спасибо,

редактировать
Для справки:

 
precision (D) first wrong digit 
------------- ------------------ 
3    27 
4    161 
5    733 
6    4329 
7    21139 
8+    ??? 

Обратите внимание, что я вычислительное одну цифру в то время, например:

for i in range(1,n): 
    D = 3 # or whatever precision I'm testing 
    digit = pi(i) # extracts most significant digit from integer-only BBP result 
    if(digit != HARDCODED_PI[i]): 
     print("non matching digit #%d, got %x instead of %x" % (i,digit,HARDCODED_PI[i])) 

Answer 1

Нет вопрос, насколько высокий я устанавливаю D, кажется , что тестирование достаточного количества цифр находит тот, где формула возвращает неверное значение.

Вы всегда получите сообщение об ошибке, если вы тестируете достаточное количество цифр - алгоритм не использует произвольную точность, поэтому в конечном итоге будут отображаться ошибки округления.

Неограниченная итерация с разрывом, когда цифра не изменится, будет трудно определить минимальную точность, необходимую для заданного количества цифр.

Лучше всего определить его эмпирически, в идеале, сравнивая с известным правильным источником и увеличивая точность цифр до тех пор, пока вы не получите совпадение или если правильный источник недоступен, начните с максимальной точности (которая Я думаю, это 14, так как 15-я цифра почти всегда содержит ошибку округления.)

EDIT: Если быть более точным, алгоритм включает в себя цикл - от 0..n, где n - это цифра для вычисления. Каждая итерация цикла приведет к некоторой ошибке. После цикла достаточное количество раз ошибка будет посягать на самую значимую цифру, которую вы вычисляете, и поэтому результат будет неправильным.

В статье в википедии используется 14 цифр точности, и этого достаточно, чтобы правильно вычислить цифру 10 ** 8. Как вы показали, меньшее количество цифр приводит к ошибкам, возникающим ранее, так как есть меньше точности, и ошибка становится видимой с меньшим количеством итераций.Конечным результатом является то, что значение для n, для которого мы можем правильно вычислить цифру, становится ниже с меньшим числом цифр.

Если у вас есть D шестнадцатеричных цифр точности, это D * 4 бит. С каждой итерацией в наименьшем значении бит вводится ошибка 0,5 бит, поэтому при 2 итерациях вероятность того, что LSB ошибочна. Во время суммирования эти ошибки добавляются и накапливаются. Если количество суммируемых ошибок достигает младшего разряда в самой значащей цифре, то одна цифра, которую вы выберете, будет неправильной. Грубо говоря, это когда N> 2 ** (D-0.75). (Исправлено до некоторой логарифмической базы.)

Эмпирически экстраполируя ваши данные, кажется приблизительным, что N = ~ (2 ** (2.05 * D)), хотя имеется несколько данных, поэтому это может быть не точный предиктор ,

Выбранный вами алгоритм BBP является итеративным, поэтому для вычисления цифр в последовательности потребуется более продолжительное время. Чтобы вычислить цифры 0..n, предпримите O(n^2) шагов.

В статье в Википедии приводится формула для вычисления n-й цифры, которая не требует итерации, просто степени возведения в степень и рациональных чисел. Это не приведет к такой же потере точности, как итеративный алгоритм, и вы можете вычислить любую цифру pi по мере необходимости в постоянное время (или, в худшем случае, логарифмический тип, в зависимости от реализации экспоненциации с модулем), поэтому вычисления n цифр будут принимать O(n) возможно, O (n log n).