Оглавление
- 1 Машинная формула
- 1.1 Машинные формулы для π
- 1.2 Вывод машинных формул
- 1.3 Использование комплексных чисел
- 1.4 Мера Лемера
- 1.5 Двухчленные формулы
- 1.6 Рекорды и усовершенствования
- 1.7 Современные формулы
- 1.8 Ручной расчет π
- 1.9 Методы получения машинных формул для π
- 1.10 Эффективность алгоритма двоичного расщепления
- 1.11 Разработка метрики для сравнения алгоритмов
- 1.12 Время выполнения алгоритма
- 1.13 Модель времени выполнения
- 1.14 Пример расчета времени
- 1.15 Полный текст статьи:
- 2 Машиноподобная формула
Машинная формула
-
Машинные формулы для π
- Машинные формулы используются для вычисления числа π с большим количеством цифр.
- Они обобщают формулу Джона Мэчина, сформулированную в 1706 году.
- Формулы имеют вид:
-
Вывод машинных формул
- Вывод формул основан на формуле сложения углов для арктангенса.
- Пример вывода: 4 арктангенса 1/5 = 1/239.
-
Использование комплексных чисел
- Комплексные числа могут быть использованы для получения машинных формул.
- Пример: 4 арктангенса 1/5 – арктангенс 1/239 = π/4.
-
Мера Лемера
- Мера Лемера характеризует вычислительную эффективность машинной формулы.
- Наименьшая известная мера Лемера: λ ≈ 1.51244.
-
Двухчленные формулы
- В случае, когда числитель a_n = 1, существует четыре двухчленных решения.
- Примеры: работа Эйлера 1737 года, “1706 год Германа”, “Хаттон” или “Вега”, и 1706 год Мачина.
-
Рекорды и усовершенствования
- Рекорд 2002 года: 1 241 100 000 000 цифр π.
- Усовершенствования включают использование “процесса Тодда” и поиск чисел с простыми разложениями.
-
Современные формулы
- Наиболее эффективная формула:
- Формула с использованием “процесса Тодда”:
-
Ручной расчет π
- В 2024 году Мэтт Паркер и 400 добровольцев использовали формулу для ручного расчета π.
- Это был самый крупный ручной расчет за всю историю π через столетие.
-
Методы получения машинных формул для π
- Существуют другие методы получения машинных формул для π с обратными числами.
- Один из методов задается формулой, где и рекурсивно.
-
Эффективность алгоритма двоичного расщепления
- Для больших вычислений π алгоритм двоичного расщепления может быть быстрее, чем простое добавление членов ряда Тейлора.
- В практических реализациях, таких как y-cruncher, каждый термин требует постоянной нагрузки и времени, пропорционального 1/log bn.
-
Разработка метрики для сравнения алгоритмов
- Цель раздела — разработать относительную метрику для сравнения алгоритмов.
- Пусть Nd — число цифр, до которых должно быть вычислено число π.
- Пусть Nt — число членов в ряде Тейлора.
- Пусть un — количество времени, затраченное на каждую цифру.
-
Время выполнения алгоритма
- Ряд Тейлора сойдется, когда Nt = Nd.
- В первом семестре обрабатываются все Nd цифр, в последнем — только одна.
- Общая сумма определяется по формуле, включающей линейную интерполяцию.
- Время выполнения задается формулой, включающей константу k.
-
Модель времени выполнения
- Программное обеспечение тратит большую часть времени на вычисление ряда Тейлора.
- Основной цикл может быть описан псевдокодом, где каждый этап занимает примерно одинаковое время.
- Единица времени определяется как один шаг псевдокода.
-
Пример расчета времени
- Уравнение 6 работает немного быстрее, чем уравнение 5, несмотря на большее количество членов.
- Доминирующим фактором является соотношение между an и bn.
- Для высокого коэффициента необходимо добавить дополнительные условия, что часто приводит к чистой экономии времени.