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

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

7 голосов
/ 24 мая 2010

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

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

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

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

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

Спасибо,

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

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 Ответ

3 голосов
/ 29 мая 2010

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

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

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

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

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

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

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

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

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

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

...