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

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

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

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

Я пробовал повысить точность, когда цифра "близка" к другой, например 0x3fff или 0x1000, но не могу найти подходящего определения слова «закрыть»; например, вычисление по цифре 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]) )

python algorithm precision math pi
person tba    schedule 24.05.2010    source источник

Ответы (1)


arrow_upward
3
arrow_downward

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

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

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

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

РЕДАКТИРОВАТЬ: Чтобы быть более точным, алгоритм включает цикл - от 0 до n, где n - это цифра для вычисления. Каждая итерация цикла вносит определенное количество ошибок. После выполнения цикла достаточное количество раз ошибка перейдет в самую значащую цифру, которую вы вычисляете, и поэтому результат будет неправильным.

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

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

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

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

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

person mdma    schedule 29.05.2010
comment
Хотя я тестирую много цифр, я вычисляю каждую цифру по одной. Вы хотите сказать, что нет способа узнать, какая точность требуется, чтобы получить одну правильную цифру в заданном месте? - person tba; 30.05.2010
comment
@brainfsck: вы, безусловно, можете использовать экстраполяцию данных, которые у вас уже есть ... это может быть непросто. - person ANeves thinks SE is evil; 31.05.2010
comment
Я сейчас просто изучаю это, чтобы посмотреть, могу ли я объяснить, где происходит ошибка округления. Но имейте в виду, что используемый вами скрипт не предназначен для создания последовательных цифр - он зацикливается с 0..n - поэтому вычисление n-й цифры требует времени, пропорционального n, что далеко от идеала. На странице википедии есть еще один алгоритм истинного крана для генерации цифр одну за другой - вы можете его использовать? - person mdma; 03.06.2010
comment
Спасибо за вашу помощь ... Я выбрал алгоритм BBP, потому что время было не проблемой, а только памятью. - person tba; 04.06.2010
comment
Вы по-прежнему можете использовать формулу BBP - просто другую реализацию, не зависящую от итераций. Код Python, расположенный ниже по странице википедии, не использует итерацию, поэтому не будет страдать от ошибок округления. - person mdma; 04.06.2010