Разностная машина — это автоматический механический калькулятор, предназначенный для табулирования полиномиальных функций. Он был разработан в 1820-х годах и впервые создан Чарльзом Бэббиджем . Название разностная машина происходит от метода разделенных разностей , способа интерполяции или табулирования функций с использованием небольшого набора полиномиальных коэффициентов. Некоторые из наиболее распространенных математических функций, используемых в технике, науке и навигации, построены на основе логарифмических и тригонометрических функций , которые можно аппроксимировать полиномами, поэтому разностная машина может вычислять множество полезных таблиц .
Идея механического калькулятора для математических функций восходит к Антикитерскому механизму II века до н. э., тогда как ранние современные примеры приписываются Паскалю и Лейбницу XVII века.
В 1784 году инженер Гессенской армии Й. Х. Мюллер разработал и построил арифмометр и описал основные принципы работы разностной машины в книге, опубликованной в 1786 году (первое письменное упоминание о разностной машине датируется 1784 годом), но он не смог получить финансирование для развития этой идеи. [1] [2] [3]
Чарльз Бэббидж начал конструировать небольшую разностную машину примерно в 1819 году [4] и завершил ее к 1822 году (разностная машина 0). [5] Он объявил о своем изобретении 14 июня 1822 года в докладе Королевскому астрономическому обществу под названием «Заметка о применении машин к вычислению астрономических и математических таблиц». [6] Эта машина использовала десятичную систему счисления и приводилась в действие поворотом рукоятки. Британское правительство было заинтересовано, поскольку создание таблиц было трудоемким и дорогим, и они надеялись, что разностная машина сделает задачу более экономичной. [7]
В 1823 году британское правительство выделило Бэббиджу 1700 фунтов стерлингов для начала работы над проектом. Хотя проект Бэббиджа был осуществим, методы металлообработки той эпохи не позволяли экономически эффективно изготавливать детали с требуемой точностью и в требуемом количестве. Таким образом, реализация оказалась намного более дорогой и сомнительной в плане успеха, чем первоначальная оценка правительства. Согласно проекту 1830 года для Разностной машины № 1, она должна была иметь около 25 000 деталей, весить 4 тонны [ 8] и работать с 20-значными числами с разностями шестого порядка. В 1832 году Бэббидж и Джозеф Клемент изготовили небольшую рабочую модель (одну седьмую часть плана), [5] которая работала с 6-значными числами с разностями второго порядка. [9] [10] Леди Байрон описала, как увидела работающий прототип в 1833 году: «Мы оба пошли посмотреть на думающую машину (или так кажется) в прошлый понедельник. Она возвела несколько чисел во вторую и третью степени и извлекла корень квадратного уравнения». [11] Работа над более крупной машиной была приостановлена в 1833 году.
К тому времени, как правительство отказалось от проекта в 1842 году, [10] [12] Бэббидж получил и потратил более 17 000 фунтов стерлингов на разработку, которая все еще не достигала рабочей машины. Правительство ценило только выход машины (экономически производимые таблицы), а не разработку (по непредсказуемой стоимости) самой машины. Бэббидж отказывался признавать это затруднительное положение. [7] Тем временем внимание Бэббиджа переключилось на разработку аналитической машины , что еще больше подорвало уверенность правительства в конечном успехе разностной машины. Улучшив концепцию как аналитическую машину, Бэббидж сделал концепцию разностной машины устаревшей, а проект по ее внедрению — полным провалом с точки зрения правительства. [7]
Незавершённая разностная машина № 1 была представлена публике на Международной выставке 1862 года в Южном Кенсингтоне , Лондон. [13] [14]
Бэббидж продолжил проектировать свою гораздо более общую аналитическую машину, но позже разработал улучшенную конструкцию «Разностной машины № 2» (31-значные числа и разности седьмого порядка) [9] между 1846 и 1849 годами. Бэббидж смог воспользоваться идеями, разработанными для аналитической машины, чтобы сделать новую разностную машину более быстрой, используя меньше деталей. [15] [16]
Вдохновленный разностной машиной Бэббиджа в 1834 году, Пер Георг Шойц построил несколько экспериментальных моделей. В 1837 году его сын Эдвард предложил построить рабочую модель из металла, а в 1840 году закончил вычислительную часть, способную вычислять ряды с 5-значными числами и разностями первого порядка, которая позже была расширена до третьего порядка (1842). В 1843 году, после добавления печатной части, модель была завершена.
В 1851 году, финансируемое правительством, началось строительство более крупной и улучшенной (15-значные числа и разности четвертого порядка) машины, которое было завершено в 1853 году. Машина была продемонстрирована на Всемирной выставке в Париже в 1855 году, а затем продана в 1856 году в обсерваторию Дадли в Олбани, штат Нью-Йорк . Доставленная в 1857 году, она стала первым проданным печатным калькулятором. [17] [18] [19] В 1857 году британское правительство заказало следующую разностную машину Шейтца , которая была построена в 1859 году. [20] [21] Она имела ту же основную конструкцию, что и предыдущая, и весила около 10 центнеров (1100 фунтов ; 510 кг ). [19]
Мартин Виберг усовершенствовал конструкцию Шойца ( около 1859 г. , его машина имела ту же производительность, что и машина Шойца: 15 цифр и четвертый порядок), но использовал свое устройство только для создания и публикации печатных таблиц (процентных таблиц в 1860 г. и логарифмических таблиц в 1875 г.) [22] .
Альфред Дикон из Лондона в 1862 году создал небольшую разностную машину (20-значные числа и разности третьего порядка). [17] [23]
Американец Джордж Б. Грант начал работать над своей вычислительной машиной в 1869 году, не зная о работах Бэббиджа и Шейца (Schentz). Год спустя (1870) он узнал о разностных машинах и приступил к проектированию одной из них сам, описав свою конструкцию в 1871 году. В 1874 году Boston Thursday Club собрал средства на постройку крупномасштабной модели, которая была построена в 1876 году. Она могла быть расширена для повышения точности и весила около 2000 фунтов (910 кг). [23] [24] [25]
Кристель Хаманн построил одну машину (16-значные числа и разности второго порядка) в 1909 году для «Таблиц Баушингера и Петерса» («Логарифмико-тригонометрических таблиц с восемью десятичными знаками»), которые были впервые опубликованы в Лейпциге в 1910 году. Она весила около 40 килограммов (88 фунтов). [23] [26] [27]
Примерно в 1912 году корпорация Burroughs построила машину для Управления морского альманаха , которая использовалась в качестве разностной машины второго порядка. [28] : 451 [29] Позднее, в 1929 году, она была заменена на Burroughs Class 11 (13-значные числа и разности второго порядка или 11-значные числа и [по крайней мере] разности пятого порядка). [30]
Александр Джон Томпсон около 1927 года построил интегрирующую и разностную машину (13-значные числа и разности пятого порядка) для своей таблицы логарифмов "Logarithmetica britannica". Эта машина состояла из четырех модифицированных калькуляторов Triumphator. [31] [32] [33]
Лесли Комри в 1928 году описал, как использовать вычислительную машину Брунсвига -Дупла в качестве разностной машины второго порядка (15-значные числа). [28] Он также отметил в 1931 году, что National Accounting Machine Class 3000 может быть использована в качестве разностной машины шестого порядка. [23] : 137–138
В 1980-х годах Аллан Г. Бромли , доцент Сиднейского университета , Австралия , изучал оригинальные чертежи Бэббиджа для разностной и аналитической машин в библиотеке Музея науки в Лондоне. [34] Эта работа привела к тому, что Музей науки построил рабочую вычислительную секцию разностной машины № 2 с 1985 по 1991 год под руководством Дорона Суэйда , тогдашнего куратора вычислений. Это было сделано в ознаменование 200-летия со дня рождения Бэббиджа в 1991 году. В 2002 году также был завершен принтер , который Бэббидж изначально спроектировал для разностной машины. [35] Преобразование оригинальных чертежей проекта в чертежи, пригодные для использования производителями техники, выявило некоторые незначительные ошибки в конструкции Бэббиджа (возможно, внесенные в качестве защиты на случай кражи планов), [36] которые необходимо было исправить. Машина разностного счета и принтер были построены с допусками, достижимыми с помощью технологий 19-го века, разрешив давний спор о том, могла ли конструкция Бэббиджа работать с использованием инженерных методов эпохи Георга. Машина содержит 8000 деталей и весит около 5 тонн. [37]
Основная цель принтера — производить стереотипные пластины для использования в печатных станках, что он делает, вдавливая шрифт в мягкий гипс для создания флонга . Бэббидж намеревался напрямую передать результаты работы машины массовой печати, осознав, что многие ошибки в предыдущих таблицах были результатом не человеческих ошибок в расчетах, а ошибок в процессе ручного набора . [7] Выходные данные принтера в основном являются средством проверки производительности машины.
Помимо финансирования создания выходного механизма для разностной машины Музея науки, Натан Мирволд заказал создание второй полной разностной машины № 2, которая экспонировалась в Музее истории компьютеров в Маунтин-Вью, Калифорния , с мая 2008 года по январь 2016 года. [37] [38] [39] [40] С тех пор она была передана в Intellectual Ventures в Сиэтле , где она экспонируется прямо за главным вестибюлем. [41] [42] [43]
Машина разности состоит из ряда столбцов, пронумерованных от 1 до N. Машина может хранить одно десятичное число в каждом столбце. Машина может только складывать значение столбца n + 1 со столбцом n , чтобы получить новое значение n . Столбец N может хранить только константу, столбец 1 отображает (и, возможно, печатает ) значение вычисления на текущей итерации .
Движок программируется путем установки начальных значений в столбцах. Столбец 1 устанавливается на значение полинома в начале вычисления. Столбец 2 устанавливается на значение, полученное из первой и более высоких производных полинома при том же значении X. Каждый из столбцов от 3 до N устанавливается на значение, полученное из первой и более высоких производных полинома. [44]
В конструкции Бэббиджа одна итерация (т.е. один полный набор операций сложения и переноса ) происходит за каждый оборот главного вала. Нечетные и четные столбцы попеременно выполняют сложение за один цикл. Последовательность операций для столбца такова: [44]
Шаги 1,2,3,4 выполняются для каждого нечетного столбца, а шаги 3,4,1,2 — для каждого четного столбца.
Хотя в оригинальной конструкции Бэббиджа рукоятка располагалась непосредственно на главном валу, позже стало понятно, что усилие, необходимое для проворачивания машины, было бы слишком большим для того, чтобы человек мог с комфортом с ней справиться. Поэтому две построенные модели включают редуктор 4:1 на рукоятке, и для выполнения одного полного цикла требуется четыре оборота рукоятки.
Каждая итерация создает новый результат и выполняется в четыре шага, соответствующих четырем полным оборотам ручки, показанной справа на рисунке ниже. Четыре шага таковы:
Движок представляет отрицательные числа как дополнение до десяти . Вычитание равносильно добавлению отрицательного числа. Это работает таким же образом, как современные компьютеры выполняют вычитание, известное как дополнение до двух .
Принцип разностной машины — метод разделенных разностей Ньютона . Если начальное значение полинома (и его конечных разностей ) вычисляется некоторыми способами для некоторого значения X , разностная машина может вычислить любое количество близлежащих значений, используя метод, обычно известный как метод конечных разностей . Например, рассмотрим квадратичный полином
с целью табулирования значений p (0), p (1), p (2), p (3), p (4) и т. д. Таблица ниже построена следующим образом: второй столбец содержит значения полинома, третий столбец содержит разности двух левых соседей во втором столбце, а четвертый столбец содержит разности двух соседей в третьем столбце:
Числа в третьем столбце значений постоянны. Фактически, начиная с любого полинома степени n , номер столбца n + 1 всегда будет постоянным. Это решающий факт, стоящий за успехом метода.
Эта таблица была построена слева направо, но ее можно продолжить строить справа налево вниз по диагонали, чтобы вычислить больше значений. Чтобы вычислить p (5), используйте значения из самой нижней диагонали. Начните с постоянного значения четвертого столбца 4 и скопируйте его вниз по столбцу. Затем продолжите третий столбец, прибавив 4 к 11, чтобы получить 15. Затем продолжите второй столбец, взяв его предыдущее значение 22 и добавив 15 из третьего столбца. Таким образом, p (5) равно 22 + 15 = 37. Чтобы вычислить p (6), мы повторяем тот же алгоритм для значений p (5): берем 4 из четвертого столбца, прибавляем его к значению третьего столбца 15, чтобы получить 19, затем прибавляем его к значению второго столбца 37, чтобы получить 56, что равно p (6). Этот процесс может быть продолжен до бесконечности . Значения многочлена производятся без необходимости умножения. Разностной машине нужно только уметь складывать. От одного цикла к другому необходимо хранить 2 числа — в этом примере (последние элементы в первом и втором столбцах). Для табулирования многочленов степени n требуется достаточно памяти для хранения n чисел.
Машина разности Бэббиджа № 2, наконец построенная в 1991 году, может хранить 8 чисел по 31 десятичной цифре каждое и, таким образом, может табулировать полиномы 7-й степени с такой точностью. Лучшие машины от Шойца могли хранить 4 числа по 15 цифр каждое. [45]
Начальные значения столбцов можно рассчитать, сначала вручную вычислив N последовательных значений функции, а затем выполнив возврат (т.е. вычислив требуемые разности).
Col получает значение функции в начале вычисления . Col — это разница между и ... [46]
Если вычисляемая функция является полиномиальной функцией , выраженной как
начальные значения могут быть рассчитаны непосредственно из постоянных коэффициентов a 0 , a 1 , a 2 , ..., a n без вычисления каких-либо точек данных. Начальные значения, таким образом, следующие:
Многие часто используемые функции являются аналитическими функциями , которые можно выразить в виде степенных рядов , например, в виде рядов Тейлора . Начальные значения можно вычислить с любой степенью точности; если все сделано правильно, движок выдаст точные результаты для первых N шагов. После этого движок выдаст только приближение функции.
Ряд Тейлора выражает функцию как сумму, полученную из ее производных в одной точке. Для многих функций высшие производные получить тривиально; например, функция синуса в точке 0 имеет значения 0 или для всех производных. Задавая 0 в качестве начала вычисления, мы получаем упрощенный ряд Маклорена
Тот же метод вычисления начальных значений из коэффициентов может быть использован для полиномиальных функций. Полиномиальные постоянные коэффициенты теперь будут иметь значение
Проблема с методами, описанными выше, заключается в том, что ошибки будут накапливаться, и ряд будет иметь тенденцию расходиться с истинной функцией. Решение, которое гарантирует постоянную максимальную ошибку, заключается в использовании подгонки кривой . Минимальное количество значений N вычисляется равномерно распределенным по диапазону желаемых вычислений. Используя технику подгонки кривой, такую как редукция Гаусса, находится интерполяция полинома N −1-й степени функции. [46] С оптимизированным полиномом начальные значения могут быть вычислены, как указано выше.
WikiSource, а также перепечатано в
The works of Charles Babbage,
Vol 2, p.119ff