Spigot алгоритм

Spigot-алгоритм (упоминается также как «алгоритм крана», или, что более точно, «алгоритм затвора», так как его работа похожа на движение затвора автомата, выбрасывающего очередной патрон) — алгоритм вычисления значения математических констант, например или e, который позволяет определить цифры в некоторой заранее выбранной системе счисления (обычно двоичной или с основанием в виде степени двойки) слева направо. Название происходит от английского слова «spigot», означающего кран или вентиль для управления потоком жидкости. Интерес к Spigot-алгоритму усилился в период раннего развития вычислительной математики из-за жестких ограничений на объёмы памяти. Первый подобный алгоритм вычисления знаков числа e встречается в работе Артура Сейла (Arthur Harry John Sale) 1986 года. Название «Spigot-алгоритм», скорее всего, придумали Стенли Рабинович и Стен Вагон. Алгоритм, предложенный Рабиновичем и Вагоном, — ограниченный в том смысле, что количество вычисляемых знаков должно быть определено заранее. Джереми Гиббонс (Jeremy Gibbons) в 2004 г. вводит обобщение под названием «потоковый алгоритм», в котором вычисления можно проводить бесконечно долго, тем самым убрав ограниченность исходного алгоритма. Ещё одним улучшением Spigot-алгоритма стал алгоритм, позволяющий вычислить конкретный знак без необходимости определения предыдущих знаков числа. Например, Формула Бэйли — Боруэйна — Плаффа для вычисления произвольных знаков в 16-ричной записи числа .