Необходимая рабочая точность для алгоритма BBP?
Я надеюсь вычислять энную цифру Pi в среде низкой памяти. Поскольку я не имею десятичные числа в наличии для меня, этот алгоритм BBP только для целого числа в Python был большой начальной точкой. Я только должен вычислить одну цифру Pi за один раз. Как я могу определить самое низкое, я могу установить D, "количество цифр рабочей точности"?
D=4 дает мне много корректных цифр, но несколько цифр будут выключены одной. Например, вычислительная цифра 393 с точностью 4 дает мне 0xafda, из которого я извлекаю цифру 0xa. Однако корректная цифра является 0xb.
Неважно, как высоко я установил D, кажется, что тестирование достаточного числа цифр находит ту, где формула возвращает неправильное значение.
Я попытался повысить точность, когда цифра "близка" к другому, например, 0x3fff или 0x1000, но не может найти хорошее определение "завершения"; например, вычисление в цифре 9798 дает мне 0xcde6, который не является очень близко к 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]) )
1 ответ
Независимо от того, насколько высоко я установил D, кажется что тестирует достаточное количество digits находит тот, в котором формула возвращает неверное значение.
Вы всегда будете получать ошибку, если проверяете достаточное количество цифр - алгоритм не использует произвольную точность, поэтому со временем будут обнаружены ошибки округления.
Неограниченная итерация с разрывом, когда цифра не меняется, будет затруднять определение минимальной точности, необходимой для данного количества цифр.
Лучше всего определить его эмпирически, в идеале путем сравнения с известным правильным источником и увеличения точности числа цифр до тех пор, пока не будет найдено совпадение, или, если правильный источник недоступен, начните с максимальной точности (которую я предположение равно 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).