Аналитическая машина
Чарльз Бэббидж был настоящим гением своего времени, блестящим изобретателем, героем романов Гёте: он был готов душу дьяволу продать, лишь бы заглянуть «за кулисы» мироздания. Мы его помним за «Аналитическую Машину». По стопам великого Паскаля он пытался воплотить в жизнь то, что сегодня пылится у каждого в доме. И если первый изобрёл не более чем усложнённые счёты, то Бэббидж намного лет вперёд опередил своё время и предвосхитил создание вычислительных машин.
Как и многие великие учёные, Бэббидж видел корень зла в одном, а именно – в неточных вычислениях. В те поры обычно использовали таблицы с рассчитанными значениями различных функций. Нужен синус 23 градусов, открывай страницу 32. Табличные значения высчитывали люди в столбик, люди ошибались, ошибки накапливались, а Бэббидж негодовал. В конце 80х XIX столетия после того, как он в очередной раз обсудил проблему с астрономом Гершелем, его терпению настал конец. На тот момент у него уже было пару работ, где на высоком уровне анализировались убытки государства за счёт «плохих» цифр, и он решил положить конец проблеме раз и навсегда.
После мучительных и долгих исканий в его голову пришла идея «Разностной Машины». Машина должна была последовательно высчитывать значения какой-либо функции в различных точках. Например, f(x)=x², при x=1..10. Сразу возникает несколько вопросов, которые сводятся к одному общему: «Как заставить груду металлолома это сделать?». Даже сегодня, имея ПК, зная язык программирования, нам бы пришлось написать какой-никакой рекурсивный анализатор выражений (или parser), решить проблему представления трансцендентных функций (синуса, логарифма) и вычислить в цикле уже все значения. К счастью, вторая проблема была решена ещё задолго до Бэббиджа с помощью рядов Тейлора. Как он решил первый вопрос здесь я и попробую рассказать, последний – оставим механикам.
Возьмём самую простую функцию f(x)=a*x+b. И построим такую таблицу:
| x | f(x) | Δf |
|---|---|---|
| 1 | a*1+b | a |
| 2 | a*2+b | a |
| 3 | a*3+b | a |
| 4 | a*4+b | - |
Третий столбец строится по формуле Δf=f(x+h)-f(x), где h=1, и он символизирует среднюю скорость изменения функции, для линейной функции она постоянна. Если h устремить к нулю, то мы получим дифференциал, который связан с Δf, как Δf=(f'(x)+ε)*h, т.е. отличается от Δf на величину бесконечно малую высшего порядка. В нашем элементарном примере видно, что для того чтобы получить значение в следующей точке, достаточно прибавить постоянную a. Вот она, главная идея. Если у нас есть полином n-ой степени, то мы можем построить все разности, вплоть до n-ого порядка, и потом рекурсивно делать вычисления. Сейчас всё поясним на примере.
Предположим, что мы хотим подсчитать значения функции f(x)=x³ в точках x=2..2.5, с шагом h=0.1. Теперь строим табличку:
| x | f(x) | Δf | Δ²f | Δ³f |
|---|---|---|---|---|
| 2 | 8.000 | 1.261 | 0.126 | 0.006 |
| 2.1 | 9.261 | 1.387 | 0.132 | 0.006 |
| 2.2 | 10.648 | 1.519 | 0.138 | 0.006 |
| 2.3 | 12.167 | 1.657 | 0.144 | - |
| 2.4 | 13.824 | 1.801 | - | - |
| 2.5 | 15.625 | - | - | - |
Как видно из таблицы, в последнем столбце значения одинаковы и это есть хорошо. Это значит, что можно только вычислить все значения первого ряда (вручную), а потом последовательно переходить к следующим рядам. Вот правило: значение в данной клетке равно сумме значений в верхней и верхней-правой клетках. Например:
9.261 = 8.000 + 1.261;
1.387 = 1.261 + 0.126;
0.132 = 0.126 + 0.006.
Именно это и реализовал Бэббидж, именно поэтому его машина и называлась разностной (или аналитической). Важно отметить, что в его машине было всего 8 ячеек памяти, поэтому удавалось вычислять полиномы только n-ой степени, где n<=8. Каждая ячейка была представлена 31 шестёренкой: могла хранить значение величиной в двойное слово. Машина должна была работать на пару, до ума её довёл уже сын учёного.
Интересный факт, что уже в те годы Бэббидж правильно угадал архитектуру будущих компьютеров. Только вот процессор у него назывался фабрикой, память – складом, а шина была прообразом Фордовского конвейера. Но разве можно от него было требовать большего.