Вычисление цифр числа пи
Я использовал библиотеку GMP и C ++ для кодирования реализации алгоритма Гаусса-Лежандра для вычисления цифр числа пи.
Он имеет правильный вывод, но проблема в том, что я не знаю, в какой момент вывод «становится плохим», так как я должен указать точность в коде.
Вот вывод с использованием 64-битной точности: 3.141592653589793238 *35* последние две цифры неверны.
Мой вопрос, если я хочу N цифры пи, сколько бит точности б, и сколько итераций алгоритма я будут необходимы?
Благодарю вас
Решение
Алгоритм Гаусса-Лежандра (он же алгоритм AGM) требует полной точности на всем протяжении.
В отличие от итераций метода Ньютона, итерации AGM не являются самокорректирующимися. Таким образом, вам нужна полная точность с самого начала. Кроме того, вам нужны дополнительные защитные цифры.
Мой вопрос, если я хочу
nцифры пи, сколько бит точностиbбудут необходимы?
Сначала вам нужно преобразовать n (десятичные) цифры в b двоичные биты. Так что это будет:
log(10)
b = n ---------- + epsilon
log(2)
куда epsilon количество защитных цифр Сколько вам нужно, зависит от реализации и поведения округления, но обычно 100 битов более чем достаточно для любого количества итераций.
Что касается того, сколько итераций вам нужно. Это можно найти по эмпирическим данным.
Вот вывод небольшого написанного мною приложения, которое вычисляет число Пи до 100 миллионов цифр с использованием алгоритма Гаусса-Лежандра:
================================================================
Computing pi to 100000000 digits:
Threads: 8
Starting AGM... 1.394965 seconds
Starting Iteration 0... -3 (error in decimal digits)
Starting Iteration 1... -9
Starting Iteration 2... -20
Starting Iteration 3... -42
Starting Iteration 4... -85
Starting Iteration 5... -173
Starting Iteration 6... -347
Starting Iteration 7... -696
Starting Iteration 8... -1395
Starting Iteration 9... -2792
Starting Iteration 10... -5586
Starting Iteration 11... -11175
Starting Iteration 12... -22352
Starting Iteration 13... -44706
Starting Iteration 14... -89414
Starting Iteration 15... -178829
Starting Iteration 16... -357661
Starting Iteration 17... -715324
Starting Iteration 18... -1430650
Starting Iteration 19... -2861302
Starting Iteration 20... -5722607
Starting Iteration 21... -11445216
Starting Iteration 22... -22890435
Starting Iteration 23... -45780871
Starting Iteration 24... -91561745
Starting Iteration 25... -183123492
AGM: 118.796792 seconds
Finishing... 3.033239 seconds
Radix Conversion... 2.924844 seconds
Total Wall Time: 126.151086 seconds
CPU Utilization: 495.871%
CPU Efficiency: 61.984%
Writing to "pi.txt"... Done
Таким образом, 25 итераций достаточно для 183 миллионов цифр. Кроме того, он удваивается с каждой итерацией, поэтому вы можете выполнить некоторую базовую математическую процедуру логарифма, чтобы выяснить, сколько итераций вам нужно.
Другие решения
Других решений пока нет …
detector