Системы счисления и их роль в истории компьютеров

Открытие Бергмана относится к такому старейшему разделу математики как системы счисления. И чтобы по-настоящему оценить значение этого открытия, мы должны коротко рассказать об истории систем счисления и оценить их роль в развитии математики. В истории систем счисления можно выделить несколько этапов: начальная стадия счета, непозиционные системы счисления, алфавитные системы нумерации, поместные или позиционные системы счисления. Поскольку первым вычислительным инструментом у человека было его собственное тело, то и сосчитываемые множества определялись при помощи частей тела. Пальцы – группы по 5 или по 10 предметов, локоть, пядь, фаланга большого пальца – единицы измерения длины и т.д. До нас дошла римская система записи чисел (алфавитная, непозиционная):

I V X L C D M

1 5 10 50 100 500 1000

На Руси вплоть до XVIII века использовалась непозиционная система славянских цифр, основанная на буквах кириллицы (помните у Горького: аз, буки, веди …).

Высшим достижением древней арифметики является открытие позиционного принципапредставления чисел. Хорошо известно, что первой из известных систем счисления, основанных на позиционном принципе, была вавилонская 60-ричная система счисления, возникшая в Древнем Вавилоне примерно во 2-м тысячелетии до новой эры.

Мы используем для повседневных вычислений десятичную систему счисления. Хорошо известно, что предшественницей десятичной системы счисления является индусская десятичная система, возникшая примерно в 8-м столетии нашей эры. Известный французский математик Лаплас (1749-1827) выразил свое восхищение позиционным принципом и десятичной системой в следующих словах:

"Мысль выражать все числа 9 знаками, придавая им, кроме значения по форме, еще значение по месту, настолько проста, что именно из-за этой простоты трудно понять, насколько она удивительна. Как нелегко было прийти к этой методе, мы видим на примере величайших гениев греческой учености Архимеда и Аполлония, от которых эта мысль осталась скрытой".

Еще более удивительным открытием была мысль добавить к девяти индусским знакам знак 0, с помощью которого можно было написать какое угодно большое число. Как известно, основанием десятичной системы счисления является число 10.

В современной науке с развитием компьютерной техники на первые роли выдвинулась двоичная система счисления. Кто же открыл двоичный способ представления чисел и двоичную арифметику? Открытие двоичного способа представления чисел приписывают китайскому императору Фо Ги, жизнь которого относится к 4-му тысячелетию до новой эры. Известный немецкий математик Лейбниц (1646-1716) в 1697 г. разработал правила двоичной арифметики. Он не рекомендовал двоичную арифметику для практических вычислений вместо десятичной системы счисления, но подчеркивал, что "вычисление с помощью двоек, то есть 0 и 1, в вознаграждение его длиннот, является для науки основным и порождает новые открытия, которые оказываются полезными впоследствии, даже в практике чисел, а особенно в геометрии: причиной чего служит то обстоятельство, что при сведении чисел к простейшим началам, каковы 0 и 1, всюду выявляется чудесный порядок".

Блестящие предсказания Лейбница сбылись только через 2,5 столетия, когда выдающийся американский ученый, физик и математик Джон фон Нейман предложил использовать именно "двоичную" систему счисления в качестве универсального способа кодирования информации в компьютерах ("Принципы Джона фон Неймана").

Таким образом, как подчеркивают многие выдающиеся математики, открытие вавилонянами позиционного принципа, а затем индусами десятичной системы счисления, основанной на позиционном принципе, по праву относятся к эпохальным открытиям математики за всю историю ее существования.

Почему же в теории чисел и теоретической арифметике не уделялось системам счисления того внимания, которое они несомненно заслуживали. Все дело - в традиции. В греческой математике, достигшей высокого уровня развития, впервые происходит сохранившееся до наших дней разделение математики на "высшую" математику, к которой относилась геометрия и теория чисел, и "логистику" - прикладную науку о технике арифметических вычислений ("школьная" арифметика), геометрических измерениях и построениях. Уже со времени Платона "логистика" третировалась как низшая, прикладная дисциплина, не входящая в круг образования философа и ученого. Восходящее к Платону пренебрежительное отношение к "школьной" арифметике и ее проблемам, а также отсутствие какой-либо достаточно серьезной потребности в создании новых систем счисления в практике вычислений, которая в течение многих столетий всецело удовлетворялась десятичной системой, а в последние десятилетия - двоичной системой (в информатике), и может служить объяснением того факта, что в теории чисел не уделялось должного внимания системам счисления и в этой части теория чисел не намного ушла вперед по сравнению с периодом своего зарождения.

Ситуация резко изменилась после появления современных компьютеров. Именно в этой области опять появился интерес к способам представления чисел и новым компьютерным арифметикам. И поэтому появление системы счисления Бергмана, переворачивающей наши представления не только о системах счисления, но и о теории чисел в целом, следует считать революционным математическим открытием 20-го столетия!

В каждой области науки и техники существуют некоторые фундаментальные идеи или принципы, которые определяют ее содержание и развитие. В компьютерной науке роль таких фундаментальных идей сыграли принципы, сформулированные независимо друг от друга двумя гениями современной науки - американским математиком и физиком Джоном фон Нейманом и советским инженером и ученым Сергеем Лебедевым.

Как известно, первый электронный компьютер ЭНИАК был изготовлен в США в 1945 г. Блестящий анализ сильных и слабых сторон проекта ЭНИАК был дан в отчете Принстонского института перспективных исследований "Предварительное обсуждение логического конструирования электронного вычислительного устройства" (июнь 1946 г.). Этот отчет, составленный выдающимся американским математиком Джоном фон Нейманом и его коллегами по Принстонскому институту Г. Голдстайном и А. Берксом, представлял проект нового электронного компьютера. Идеи, высказанные в этом отчете, известные под названием "Неймановских Принципов", оказали серьезное влияние на развитие компьютерной техники.

Сущность "Неймановских Принципов" состояла в следующем:

3. Компьютеры на электронных элементах должны работать не в десятичной, а в двоичной системе счисления.

4. Программа должна размещаться в одном из блоков компьютера - в запоминающем устройстве.

5. Программа, так же как и числа, с которыми оперирует компьютер, записываются в двоичном коде, то есть по форме представления команды и числа однотипны.

6. Трудности физической реализации запоминающего устройства большого быстродействия и большой памяти требуют иерархической организации памяти.

7. Арифметическое устройство компьютера конструируется на основе схем, выполняющих операцию сложения.

8. В компьютере используется параллельный принцип организации вычислительного процесса (операции над двоичными кодами осуществляются одновременно над всеми разрядами).

В Советском Союзе работы по созданию электронных компьютеров были начаты несколько позже. Первый советский электронный компьютер был изготовлен в Киеве в 1953 г. Он назывался МЭСМ (малая электронная счетная машина), а его главным конструктором был академик Сергей Лебедев, автор проектов компьютеров серии БЭСМ (большая электронная счетная машина). В проекте МЭСМ Сергей Лебедев независимо от Неймана пришел к тем же идеям конструирования электронных компьютеров, что и Нейман.

Говоря об основоположниках теоретической информатики, нельзя не упомянуть о двух научных достижениях, алгебре логикиитеории алгоритмов.

Алгебра логики была разработана в середине 19-го века английским математиком Джорджем Булеми рассматривалась им в качестве метода математизации формальной логики. Разработка электронных компьютеров на двухпозиционных электронных элементах сделала возможным широкое использование "булевой логики" для проектирования компьютерных схем. В первой половине 30-х годов 20-го столетия появились математические работы, в которых была доказана принципиальная возможность решения с помощью автоматов любой проблемы, поддающейся алгоритмической обработке. Данное доказательство содержалось в опубликованных в 1936 г. работах английского математикаА. Тьюрингаи американского математикаЭ. Поста. Здесь уместно упомянуть, что числа Фибоначчи и золотое сечение были "хобби" Алана Тьюринга. Таинственный, почти мистический смысл этого замечания будет понятен несколько позже.

Снова обратимся к "принципам Неймана". Существенно подчеркнуть, что центральное место среди "принципов Неймана" занимает предложение об использовании двоичной системы счисления, что было обусловлено рядом обстоятельств. Во-первых, несомненными арифметическими достоинствами двоичной системы счисления, ее "оптимальным" согласованием с "булевой" логикой и простотой технической реализации двоичного элемента памяти (триггера).

Однако на определенном этапе развития компьютерной техники было обнаружено ряд недостатков классической двоичной системы счисления. Первым из них является так называемая "проблема представления отрицательных чисел". Как известно, отрицательные числа непосредственно не могут быть представлены в классической двоичной системе счисления, использующей только две двоичные цифры 0 и 1, без дополнительных "ухищрений". Основным "ухищрением" является использование специальных кодов для представления отрицательных чисел - обратного или дополнительного.

Второй недостаток двоичной системы счисления - ее "нулевая избыточность". Дело в том, что если в процессе передачи, хранения или обработки двоичной кодовой комбинации, например 10011010, под влиянием "помех", действующих в "канале", произойдет искажение данной кодовой комбинации и она перейдет в кодовую комбинацию 11010010 (искажения отдельных битов подчеркнуты), то, поскольку комбинация 11010010 (как и любая другая двоичная кодовая комбинация) является "разрешенной" в классической двоичной системы счисления, то не существует способа обнаружить данную ошибку без дополнительных "ухищрений", то есть без использования специальных методов избыточного кодирования.

Именно попытка преодолеть эти и другие недостатки и стимулировала использование в компьютерах новых систем счисления и развитие теории систем счисления, но чтобы понять как появляются новые технологии и как они совершенствуются в своем эволюционном движении мы вынуждены вернуться на многие столетия назад.