Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Введение
Алгоритм вычисления значения трансцендентального числа. Алгоритм последовательного вычисления (spigot algorithm) — это алгоритм вычисления значения трансцендентального числа (такого как π или e), который генерирует цифры числа последовательно слева направо, обеспечивая возрастающую точность по мере выполнения алгоритма. Алгоритмы последовательного вычисления также стремятся минимизировать объем необходимой промежуточной памяти. Название происходит от значения слова "spigot" – крана или вентиля, регулирующего поток жидкости. Алгоритмы последовательного вычисления можно противопоставить алгоритмам, которые хранят и обрабатывают полные числа для получения последовательно более точных приближений к желаемому трансцендентальному числу. Интерес к алгоритмам последовательного вычисления был вызван в ранние дни вычислительной математики жесткими ограничениями по объему памяти, и такой алгоритм для вычисления цифр e был представлен в статье Сале в 1968 году. В 1970 году Абдали представил более общий алгоритм для вычисления сумм рядов, в которых отношения последовательных членов могут быть выражены как частные от целочисленных функций позиций членов ряда. Этот алгоритм применим ко многим известным рядам для тригонометрических функций, логарифмов и трансцендентальных чисел, поскольку эти ряды удовлетворяют указанному условию. Название "алгоритм последовательного вычисления", по-видимому, было предложено Стэнли Рабиновицем и Стэном Вагоном, чей алгоритм вычисления цифр π иногда называют "алгоритмом последовательного вычисления для π". Алгоритм Рабиновица и Вагона является ограниченным, в том смысле, что количество членов бесконечного ряда, которые будут обработаны, должно быть определено заранее. Термин "потоковый алгоритм" (streaming algorithm) обозначает подход без этого ограничения. Это позволяет вычисление продолжаться неопределенно долго, изменяя объем необходимой промежуточной памяти по мере выполнения вычисления. Вариант подхода последовательного вычисления использует алгоритм, который может быть использован для вычисления одной произвольной цифры трансцендентального числа без вычисления предыдущих цифр: примером является формула Бэйли — Борвейна — Плуффа, алгоритм извлечения цифр для π, который генерирует цифры в шестнадцатеричной системе счисления. Неизбежное усечение базового бесконечного ряда алгоритма означает, что точность результата может быть ограничена количеством вычисленных членов ряда.
Algorithm for computing the value of a transcendental numberA spigot algorithm is an algorithm for computing the value of a transcendental number (such as or e) that generates the digits of the number sequentially from left to right providing increasing precision as the algorithm proceeds. Spigot algorithms also aim to minimize the amount of intermediate storage required. The name comes from the sense of the word "spigot" for a tap or valve controlling the flow of a liquid. Spigot algorithms can be contrasted with algorithms that store and process complete numbers to produce successively more accurate approximations to the desired transcendental. Interest in spigot algorithms was spurred in the early days of computational mathematics by extreme constraints on memory, and such an algorithm for calculating the digits of e appeared in a paper by Sale in 1968. In 1970, Abdali presented a more general algorithm to compute the sums of series in which the ratios of successive terms can be expressed as quotients of integer functions of term positions. This algorithm is applicable to many familiar series for trigonometric functions, logarithms, and transcendental numbers because these series satisfy the above condition. The name "spigot algorithm" seems to have been coined by Stanley Rabinowitz and Stan Wagon, whose algorithm for calculating the digits of is sometimes referred to as "the spigot algorithm for ". The spigot algorithm of Rabinowitz and Wagon is bounded, in the sense that the number of terms of the infinite series that will be processed must be specified in advance. The term "streaming algorithm" indicates an approach without this restriction. This allows the calculation to run indefinitely varying the amount of intermediate storage as the calculation progresses. A variant of the spigot approach uses an algorithm which can be used to compute a single arbitrary digit of the transcendental without computing the preceding digits: an example is the Bailey–Borwein–Plouffe formula, a digit extraction algorithm for which produces base 16 digits. The inevitable truncation of the underlying infinite series of the algorithm means that the accuracy of the result may be limited by the number of terms calculated.