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

Question

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

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

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

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

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

Спасибо,

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

Точность (d) первая неправильная цифра -------------- -------------------- 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-я цифра почти всегда всегда содержит ошибку округления.)

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

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

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

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

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

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