Позиционный принцип представления чисел

Сразу после защиты докторской диссертации в 1972 г. логика развития моего научного направления вывела меня на проблему «систем счисления», одну из фундаментальных проблем математики и науки в целом. И естественно, что после «алгоритмической теории измерения» я начал размышлять над этой проблемой. Результаты своих размышлений по этому поводу я изложил в статье «Системы счисления и их роль в развитии математики и компьютеров», написанной в конце 2002 г. по заказу «Виртуального компьютерного Музея России». И мне кажется, что читателям моей книги будет интересно ознакомиться с основными идеями этой статьи.

Каждый человек на земном шаре, окончивший хотя бы четыре класса начальной или «церковно-приходской» школы, знает, по меньшей мере, две полезные вещи: он умеет писать и читать и использовать десятичную систему счисления для выполнения простейших арифметических операций. И эта система кажется нам настолько простой и элементарной, что многие из нас с большим недоверием отнесутся к утверждению, что десятичная система является одним из крупнейших математических открытий за всю историю математики. И чтобы убедить читателя в этом, обратимся к мнению «авторитетов».

Пьер Симон Лаплас (1749-1827), французский математик, член Парижской академии наук, почетный иностранный член Петербургской академии наук:

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

М.В. Остроградский (1801-1862), русский математик, член Петербургской академии наук и многих иностранных академий:

«Нам кажется, что после изобретения письменности самым большим открытием было использование так называемой десятичной системы счисления. Мы хотим сказать, что соглашение, с помощью которого мы можем выразить все полезные числа двенадцатью словами и их окончаниями, является одним из самых замечательных созданий человеческого гения …»

Жюль Таннери (1848-1910), французский математик, член Парижской академии наук:

«Что касается до нынешней системы письменной нумерации, в которой употребляется девять значащих цифр и ноль, и относительное значение цифр определяется особым правилом, то эта система была введена в Индии в эпоху, которая не определена точно, но, по-видимому, после христианской эры. Изобретение этой системы есть одно из самых важных событий в истории науки, и несмотря на привычку пользоваться десятичной нумерацией, мы не можем не изумляться чудной простоте ее механизма».

К сожалению, историки компьютерной науки, владея развитой компьютерной теорией, иногда забывают о той роли, которую сыграли системы счисления в истории компьютеров. Ведь первые проекты счетных приборов (абаков и арифмометров), прообразов современных компьютеров, появились задолго до возникновения алгебры логики, теории алгоритмов – и главную роль при создании таких счетных приборов сыграли именно системы счисления и правила выполнения в них простейших арифметических операций. Об этом не следует забывать, прогнозируя дальнейшее развитие компьютерной техники.

Создание первых систем счисления относится к периоду зарождения математики, когда потребности счета предметов, измерения времени, земельных участков и количества продуктов привели к созданию простейших понятий арифметики натуральных чисел. Как подчеркивает А.Н. Колмогоров в статье «Математика» (БСЭ, том. 15), «только на основе разработанной системы устного счисления возникают письменные системы счисления и постепенно вырабатываются приемы выполнения над натуральными числами четырех арифметических действий».

В истории систем счисления выделяют несколько этапов: начальная стадия счета, непозиционные системы счисления, алфавитные системы нумерации, поместные или позиционные системы счисления. Начальная стадия счета характеризуется изображением сосчитываемых множеств при помощи частей тела, особенно пальцев рук и ног, палочек, узлов веревки и т.д. Как подчеркивается в статье Башмаковой И.Г. и Юшкевича А.П. «Происхождение систем счисления» («Энциклопедия Элементарной Математики, том 1 «Арифметика», 1951 г.), «несмотря на крайнюю примитивность этого способа изображения, он сыграл исключительную роль в развитии понятия числа». Таким образом, именно системы счета сыграли определяющую роль в формировании понятия натурального числа, одного из фундаментальных понятий математической науки.

Уже в период зарождения математики было сделано одно из крупнейших математических открытий за всю историю математики. Речь идет о позиционном принципе представления чисел. Как подчеркивается в упомянутой выше статье Башмаковой И.Г. и Юшкевича А.П., «первой известной нам системой счисления, основанной на поместном или позиционном принципе, является шестидесятеричная система древних вавилонян, возникшая примерно за 2000 лет до н.э.».

Алфавитные системы нумерации

У многих народов широкое распространение получили так называемые алфавитные системы нумерации, когда буквам алфавита присваивались некоторые числовые значения. Так поступали древние греки, евреи, славяне и другие народы. С алфавитной нумерацией связано возникновение так называемого «звериного» числа 666. Если записать на древнееврейском языке два слова «император Нерон», а затем подсчитать сумму числовых значений входящих в него букв, то она окажется равной 666. Таким образом, число 666 является скрытым обозначением имени Нерона, гонителя христианства, человека-зверя, который с крайней жестокостью расправлялся со своими политическими противниками и с ведома которого были убиты его мать, обе жены, философ Сенека и многие другие.

Славяне также использовали алфавитную нумерацию. Но чтобы отличить буквы от чисел, они ставили над буквами, изображающими числа, особый знак, названный «титло».

Всем известна римская система нумерации, которая предшествовала появлению нашей позиционной системы счисления. Она использует специальные знаки для изображения «узловых» чисел (I, V, X, L, C, D, M). Крупнейшим недостатком римской нумерации является то, что она совершенно не приспособлена для производства арифметических действий в письменном виде.

Появление позиционной системы обозначения чисел считается одной из основных вех в истории материальной культуры. В ее создании принимали участие целые народы. В 6 в. н.э. подобная система возникла у племени майя. Наиболее распространено мнение, что основанием системы счисления майя является число 20, имеющее «пальцевое» происхождение. Однако известно, что в системе майя есть одно отступление от двадцатеричного основания. Вес следующего за «узловым» числом 20 индейцы майя выбрали равным 360 (а не 400, как того требовал «позиционный принцип»). Все последующие веса разрядов являются производными от чисел 20 и 360, которые и выступают в роли «узловых» чисел, образующих систему майя. Как подчеркивается в упомянутой выше статье Башмаковой И.Г. и Юшкевича А.П., это «объясняется тем, что год майя делили на 18 месяцев, по 20 дней в каждом, плюс еще пять дней». Таким образом, как и основание вавилонской системы, узловые числа системы майя имеют астрономическое происхождение.

История десятичной системы счисления

Мы используем для повседневных вычислений десятичную систему счисления. Хорошо известно, что предшественницей десятичной системы счисления является Индусская десятичная система, возникшая примерно в 8-м столетии нашей эры. В Европу десятичная нумерация проникла из Исламского Востока. Наиболее ранние рукописи на арабском языке, содержащие индийскую позиционную запись чисел, относятся к 9-му столетию нашей эры. Одним из первых в Европе понял преимущества новой нумерации французский церковнослужитель и математик Герберт, который в 999 году стал римским папою под именем Сильвестра П. Новоиспеченный папа попытался провести реформу в преподавании математики и ввести новую систему нумерации. Однако нововведение встретило яростный гнев со стороны инквизиции. Папу обвинили в том, что он «продал душу сарацинским дьяволам». Реформу постарались провалить, и папа-математик вскоре умер. Но и после смерти его не оставили в покое. Несколько столетий ходили слухи, что из мраморного саркофага папы непрерывно сочится серный дым и слышится шорох чертей.

Хотя первые записи арабско-индийскими цифрами встречаются в испанских рукописях еще в 10-м веке, десятичная система начинает закрепляться в Европе только, начиная с 12-го века. Новая нумерация в Европе встретила ожесточенное сопротивление как со стороны официальной схоластической науки того времени, та и со стороны отдельных правительств. Так, например, в 1299 г. во Флоренции купцам было запрещено пользоваться новыми цифрами, в бухгалтерии приказано было либо пользоваться римскими цифрами, либо писать числа словами.

Убежденным сторонником использования арабско-индийской системы счисления в торговой практике был известный итальянский математик Леонардо Пизанский (Фибоначчи), получивший математическое образование в арабских странах. В своем сочинении «Liber abaci» (1202) он писал:

«Девять индусских знаков – суть следующие: 9, 8, 7, 6, 5, 4, 3, 2, 1. С помощью этих знаков и знака 0, который называется по-арабски «zephirum», можно написать какое угодно число».

Здесь словом «zephirum» Фибоначчи передал арабское слово «as-sifr», являющееся дословным переводом индусского слова «sunya», то есть пустое, служившее названием нуля. Слово «zephirum» дало начало французскому и итальянскому слову «zero» (нуль). С другой стороны, то же арабское слово «as-sifr» было передано через «ziffer», откуда произошли французское слово «chiffre», немецкое «ziffer», английское «cipher» и русское «цифра».

В начале 17-го века новая нумерация проникает в Россию, но православная церковь встречает ее в штыки и объявляет новую нумерацию колдовской и безбожной. Закрепилась десятичная нумерация в России только после издания в 1703 году знаменитой «Арифметики» Магницкого, в которой все вычисления в тексте производились исключительно с использованием десятичной системы счисления.

История двоичной системы

В связи с развитием компьютерной техники на первые роли в современной науке выдвинулась двоичная система счисления. Зачатки двоичной системы наблюдаются у многих народов. Как упоминалось, у древних египтян широкое распространение получили методы умножения и деления, основанные на принципе «удвоении». Изобретение двоичного способа нумерации приписывают китайскому императору Фо Ги, жизнь которого относится к 4-му тысячелетию до новой эры.

Кто же изобрел правила выполнения арифметических операций в двоичной системе счисления? Оказывается, что автор двоичной арифметики в истории науки доподлинно известен; им является известный немецкий математик Готфрид Лейбниц (1646-1716), который в 1697 г. разработал двоичную арифметику. Лейбниц настолько был восхищен этим своим открытием, что в его честь он выпустил специальную медаль, на которой были даны двоичные изображения начального ряда натуральных чисел – и, возможно, это был тот редкий случай в истории науки, когда именно математическое открытие было удостоено такой высокой почести.

Лейбниц, однако, не рекомендовал двоичную нумерацию для практических вычислений вместо десятичной системы, но подчеркивал, что «вычисление с помощью двоек, то есть 0 и 1, в вознаграждение его длиннот, является для науки основным и порождает новые открытия, которые оказываются полезными впоследствии, даже в практике чисел, а особенно в геометрии: причиной чего служит то обстоятельство, что при сведении чисел к простейшим началам, каковы 0 и 1, всюду выявляется чудесный порядок».

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

Принципы Неймана-Лебедева

Блестящие предсказания Лейбница относительно роли двоичной системы счисления в современной науке сбылись только через 2,5 столетия, когда выдающийся американский ученый, физик и математик Джон фон Нейман (1903-1957) после тщательного анализа достоинств и недостатков первого в компьютерной истории электронного компьютера ЭНИАК отдал решительное предпочтение двоичной системе счисления в качестве универсального способа кодирования информации в электронных компьютерах. Независимо от Неймана к этим же принципам пришел выдающийся советский ученый С.А. Лебедев, генеральный конструктор первых советских компьютеров. Поэтому в российской историко-математической литературе фундаментальные принципы построения современных электронных компьютеров называются также «принципами Неймана-Лебедева».

Идея Неймана использовать двоичную систему счисления в электронных компьютерах была обусловлена как присущими ей арифметическими преимуществами, так и спецификой электронных элементов. «Наш основной блок памяти, — писал Нейман, — по своей природе приспособлен к двоичной системе … Триггер в сущности – опять-таки двоичное устройство … Основное же преимущество двоичной системы по сравнению с десятичной состоит в большей простоте и быстродействии, с которыми могут выполняться элементарные операции …. Дополнительное замечание состоит в том, что основная часть машины по своему характеру является не арифметической, а логической. Новая логика, будучи системой типа «да-нет», в основном двоичная. Поэтому двоичное построение арифметических устройств существенно содействует построению более однородной машины, которая может быть лучше скомпонована и более эффективна».

Троичный принцип Брусенцова и троичный компьютер «Сетунь»

Несмотря на огромные преимущества двоичной системы счисления, она все же обладает рядом недостатков. Попытка их преодоления и стимулировала развитие машинной арифметики и создание проектов новых компьютеров. Одним из существенных недостатков классической двоичной системы счисления является «проблема знака», то есть «проблема представления отрицательных чисел». В двоичной системе счисления отрицательные числа играют роль некоторых «изгоев», так как не могут быть в ней представлены в «прямом коде»; они представляются в двоичной компьютерной арифметике путем введения так называемых «обратного» и «дополнительного» кодов. Это существенно усложняло архитектуру и структуру компьютеров и стало причиной поиска математических и технических решений, исключающих этот недостаток. Одним из первых такое решение нашел выдающийся русский инженер Николай Брусенцов, который предложил использовать в компьютерах «троичную симметричную систему счисления», в которой действительные числа (отрицательные и положительные) представляются в виде следующей суммы:

,

(33)

где число 3 – основание системы счисления; 3ⁱ – вес i-го разряда; c_i – троичная цифра i-го разряда, принимающая значение из множества {-1=` 1, 0, 1}.

Основное преимущество системы счисления (33) по сравнению с классической двоичной системой счисления с цифрами 0 и 1 состоит в изящном решении «проблемы знака». Знак числа определяется старшей значащей цифрой троичного представления. Например, число N₁ = 0` 1 1 1 0` 1 является отрицательным, а число N₂ = 1` 1 0` 1 0 0 1 положительным. Как положительные, так и отрицательные числа представляются в «прямом» коде, и все арифметические действия выполняются в «прямом» коде. Очень просто получить представление отрицательного числа (-N) из троичного представления положительного числа N, используя правило «троичной инверсии»:

1 ® ` 1, 0 ® 0, ` 1® 1.

(34)

Троичное симметричное сложение и умножение основываются на тривиальных тождествах, связывающих степени числа 3: 3ⁱ + 3ⁱ = 3ⁱ⁺¹ — 3ⁱ (для сложения) и 3^mґ 3ⁿ = 3^m+n (для умножения). Троичное симметричное вычитание чисел А — B сводится к сложению чисел А + (-B), если к вычитаемому B применить правило троичной инверсии (34). Троичное симметричное деление подобно классическому двоичному делению и сводится к сдвигу делителя и его вычитанию из делимого.

Именно троичная симметричная система счисления (33) является ключевой идеей нового принципа конструирования компьютеров, в основу которого положены три идеи: (1) использование троичной логики, (2) использование троичного элемента памяти, (3) использование троичной системы счисления (33). С использованием этого принципа, названного «троичным принципом Брусенцова» в честь его создателя, уже на заре компьютерной эры был создан компьютер «Сетунь», первый в истории компьютерной техники троичный компьютер. Компьютер «Сетунь» был разработан на магнитных элементах, и поэтому не получил широкого практического использования, но его архитектура, основанная на «Троичном Принципе», оказалась настолько совершенной, что в настоящее время проект этого компьютера привлекает внимание многих компьютерных специалистов.

Известный советский компьютерный специалист профессор Поспелов написал:

«Барьеры, стоящие на пути приложения троичной симметричной систем счисления в компьютерах, являются препятствиями технического порядка. До сих пор не разработаны экономичные и эффективные элементы с тремя устойчивыми состояниями. Как только такие элементы будут разработаны, большая часть компьютеров универсального типа и многие специальные компьютеры по всей вероятности будут разработана таким образом, чтобы они функционировали в троичной симметрической системе счисления ».

Также известный американский ученый Дональд Кнут выражал мнение, что замена двоичного триггера («flip-flop») на троичный триггер («flip-flap-flop») в один прекрасный день обязательно произойдет.

Система остаточных классов

В 60-е годы 20-го столетия широкую популярность завоевала так называемая машинная арифметика в остаточных классах. Толчком к исследованиям в этой области послужили опубликованные в 1955-1957 гг. работы чешских ученых М. Валаха и А. Свободы, посвященные представлению чисел в виде совокупности неотрицательных вычетов по группе взаимно простых оснований. Идея была подхвачена советскими учеными И.Я. Акушским и Д.И. Юдицким, опубликовавшим в 1968 г. книгу «Машинная арифметика в остаточных классах», фундаментальный труд по новой машинной арифметике. На вопрос о побудительных мотивах создания применения СОК в компьютерах И.Я. Акушский и Д.И. Юдицкий отвечают следующим образом:

«Следует отметить, что позиционные системы счисления, в которых представляется и обрабатывается информация в современных вычислительных машинах, обладает существенным недостатком – наличием межразрядных связей, которые накладывают свой отпечаток на способы реализации арифметических операций, усложняют аппаратуру и ограничивают быстродействие. Поэтому естественно изыскание возможностей такой арифметики, в которой бы поразрядные связи отсутствовали.

Оказалось, что такая арифметика может быть построена на базе непозиционной системы счисления, в частности системы остаточных классов».

Таким образом, главной побудительной причиной разработки машинной арифметики в системе остаточных классов (СОК) явилось преодоление серьезного недостатка позиционных систем счисления, в частности, двоичной системы – наличие межразрядных связей при выполнении арифметических операций, что принципиально снижало быстродействие компьютеров.

Важно подчеркнуть, что Акушский и Юдицкий были не только теоретиками в области СОК, но и принимали активное участие в реализации компьютера на основе СОК. Такой компьютер начал создаваться в Советском Союзе еще в 1957 г. В компьютере, основанном на СОК, была достигнута рекордная производительность – 1,25 млн. операций в секунду, что почти на порядок превышало производительность компьютеров того времени, которые проектировались на основе классической двоичной системы счисления.

Будучи весьма перспективной в отношении межразрядных связей, система остаточных классов оказалась далеко не безупречной в других отношениях, на что обращают внимание Акушский и Юдицкий в своей книге:

«Однако столь удобной в одном отношении системе остаточных классов присущ ряд недостатков в других отношениях: ограниченность действия этой системы полем целых положительных чисел, трудность определения соотношений чисел по величине, определения выхода результата операции из диапазона и т.д.»

И хотя авторам книги «Машинная арифметика в остаточных классах» удалось продвинуться в преодолении этих трудностей, но полностью разрешить их не удалось. «Компьютерной революции» на основе СОК не получилось, то есть проектировщики компьютеров отдавали все же предпочтение классической позиционной двоичной системе счисления, то есть позиционный принцип представления чисел, одно из величайших изобретений математической мысли, остался непоколебимым. Преодоление недостатков, присущих двоичной системе счисления, надо было искать в рамках позиционного представления. И появление систем счисления с иррациональными основаниями стало дальнейшим развитием машинной арифметики.

Роль систем счисления в развитии математики

Таким образом, появление компьютеров привело к возникновению нового интереса к одной из древнейших проблем науки и математики – проблеме «систем счисления». И есть все основания предполагать, что именно эти научные результаты могут стать основой для создания новых компьютерных проектов. С другой стороны, исследования в области новых систем счисления и компьютерных арифметик как бы возвращают математику к периоду своего зарождения, когда одной из ее главных проблем был счет предметов и разработка правил выполнения арифметических операций. Но тогда вполне резонным является постановка следующего вопроса: а не могут ли современные системы счисления, созданные для удовлетворения потребностей компьютерной техники, повлиять на развитие самого понятия числа и теории чисел и таким путем повлиять на развитие не только компьютерной науки, но и всей математики.

Эта идея и стала предметом моих исследований в последующие годы. Двигаясь в этом направлении, я пришел к идее нового геометрического определения числа, которая и вывела меня позже на идею создания новой математики, «Математики Гармонии», основанной на золотом сечении.