Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 62
Текст из файла (страница 62)
— Прим. иерее. найти в книгах О. Е. Яш1ГЬ, НЕввогу оЕ МавЬепшбсв 2 (Вовгои: Сшп апд Со., 1925), 228-247, и Ч. Л. Кавв, А Н1вгогу оЕМавйетаг1ев (Ыеж тигре ИагрегСоП1пв, 1993).) Двоичная система счисления имеет собственную интересную историю. Известно, что многие племена, ведущие в наше время первобытный образ жизни, используют двоичную, или парную, систему счета (группирование по два, а не по пять или десять), но было бы ошибкой утверждать, что они действительно считают в двоичной системе, так как при этом степени двойки никоим образом не выделяются.
Интересные подробности о примитивных числовых системах можно найти в статье АЬгаЬат Яе1депЬегй ТЬе ПНЕив1оп оЕ Соипипй Ргасбеев Ушю оЕ СаНЕ. Рийй 1и Маей. 3 (1960), 215-300. Другой "примитивный" пример двоичной системы— музыкальная нотация (для обозначения ритма и длительности нот). В 17 веке предметом обсуждения в Европе были недесятичные системы. В течение многих лет астрономы от случая к случаю использовали шестидесятеричную арифметику как для целых, так и для дробных частей чисел, главным образом, при выполнении умножения (см. ЛоЬп Жатв, Тгеайве оЕА)леЬга (Ох(огб, 1685), 18-22, 30). Тот факт, что любое целое, большее 1, может служить основанием для системы счисления, впервые опубликован около 1658 года Блезом Паскалем (В!шве Равса1) в 11е Хишег1в Ми!6р!Ес(Ьив. (См, полное собрание сочинений Паскаля (Еиггви Сошр!йгев (Рапв: Ео!1!она ди Беш!, 1963), 84-89.) Паскаль писал: "Вепапа еппп ех!пав!сиво !юпшипп, поп ех песевв1ваее паеигш иг ти!йив агЬПгасиг, ев вале вас!в !нерве, ров)га евг", т.
е. "Десятичная система построена довольно неразумно, в соответствии с человеческими обычаями, а вовсе не с требованиями естественной необходимости, как склонно думать большинство людей". Он утверждал, что было бы желательно перейти к двенвдцатеричной (по основанию двенадцать) системе, и предложил правило проверки делимости двенадцатеричного числа на 9. Эрхард Вайгель (ЕгЬап! %е(йе!) в ряде публикаций начиная е 1673 года пытался пробудить интерес к четверичной (по основанию четыре) системе счисления. Подробное обсуждение арифметики по основанию двенадцать было проведено Джошуа Джордэйном (ЛовЬиа Логба1пе) в работе 11иодесипа) Аг(йтейе)с (Ьопбоп, 1687).
Хотя в арифметике на протяжении всей этой эпохи применялась почти исключительно десятичная система счисления, системы мер и весов редко основывались (если вообще основывались) на кратности десяти, и для ведения многих торговых операций требовалась изрядная доля умения складывать величины наподобие фунтов, шиллингов и пенсов. Поэтому на протяжении столетий купцы учились складывать н вычитать величины, выражаемые специфическими денежными единицами„единицами мер и весов, а это фактически была арифметика в недесятичной системе счисления.
Особого внимания заслуживают, в частности, основные единицы измерения объема жидкости в Англии, установившиеся еще в 13 веке или даже раньше. 2 джила = 2 полуштофа = 2 пинты= 2 кварты = 2 потла = 2 !эллина = 1 полуштоф 1 пиита 1 кварта 1 потл 1 галлон 1 пек 2 пека 2 полубушеля 2 фиркина 2 килдеркииа 2 барреля 2 хогсхеда 2 пайпа 1 палубу щель 1 бушель или фиркин 1 килдеркин 1 баррель 1 хогсхед 1 пайп 1 тан Объемы жидкости, выраженные в галлонах, патлах, квартах, пинтах и т. д., по существу, записывались в двоичной системе. Быть может, подлинными изобретателями двоичной арифметики были английские виноторговцы! Насколько сейчас известно, впервые чисто двоичная система счисления появилась в 1605 голу в нескольких неопубликованных работах Томаса Хэрриота (ТЬошав НагпоС) (1560-1621). Хэрриот был личностью творческой н приобрел известность по прибытии в Америку в качестве представителя сэра Уолтера Рэлея (1Ъа1сег Ва1е!кЬ).
Он изобрел (среди всего прочего) символы для обозначения отношений "меньше" и "больше", используемые и ныне, но по некоторым соображениям предпочел не публиковать большинство своих открытий. Выдержки из его заметок по двоичной арифметике воспроизведены Джоном У. Ширли (ЛоЬп %. БЫг1еу) в журнале Ашег. Л. РЬув!св 19 (1951), 452 — 454. Впервые заметки Хэрриота относительно двоичной системы были процитированы Марли (Мог1еу) и появились в журнале ТЬе Яс!епг!Йс Мопй!у 14 (1922), 60-66. Первый опубликованный анализ двоичной системы появился в работе испанского священника Хуана де Карамюэля Лобковица (Лпап с!е Сагапше) 1оЫсся !сх) МаСЬев!в В!сера 1 (Сашрап!ш, 1670), 45-46. Карамюзль рассмотрел представление чисел в системах по основаниям 2, 3, 4, 5, 6, 7, 8, 9, 10, 12 и 60„но не привел никаких примеров арифметических операций в недесятнчных системах, кроме шестидесятеричиой системы.
Наконец, статья Г. В. Лейбница (С. %. Ье!Ьп!в) Мелю!гев с(е ! "Асяс!4ппе Науа!е с!ев ЯсЛепсев (Рапв„1703), 110-116, в которой были описаны сложение, вычитание, умножение и деление в двоичной системе, действительно привлекла к этой системе всеобщее внимание, и именно на эту статью ссылаются, говоря о рождении арифметики по основанию 2.
Лейбниц и в дальнейшем очень часто обращался к двоичной системе счисления. Он не рекомендовал ее для практических вычислений, однако подчеркивал важность этой системы в теории чисел, твк как закономерности поведения числовых последовательностей часто гораздо легче усмотреть в двоичной записи, чем в десятичной. Он также вкладывал некий мистический смысл в тот факт, что все в мире можно выразить с помощью нулей и единиц. Неопубликованные работы Лейбница показывают, что он интересовался двоичной системой счисления еще в 1679 галу, когда ссылался на нее как иа систему "Ь!шар' (аналогично "десятичной" ).
Подробное исследование ранних работ Лейбница по двоичным числам выполнено Гансом Й. Захером (Наив Л. ЕасЬег) в работе Р!е НаирсвсЬг>йеп хпг Руас)!Ь гоп 6. В. !е!Ьп!в (Ргап!с!агс аш Ывлп: К!овсеппапп, 1973), Захер отмечал, что, предложив способ вычислений при помощи камней, ориентированных на использование абаки по основанию 2, Лейбниц стал близок к так называемой "локаль- ной арифметике" Джона Непера. Непер в 1617 году опубликовал идею локальной арифметики в приложении к своей маленькой книге ВЬабг)о!о8!а, Эта идея может трактоваться как первая в мире '*двоичная машина", тем более что она была самой дешевой машиной в мире, хотя Непер и чувствовал, что это не машина, а, скорее, игрушка.
(См. обзор Мартина Гарднера (Магбп Оап(пег) Кпоггег! 0ои8Ьпияя апг! Ойег МайетаНса! Епгеггшптепгя (Нетг Ъог)г: Ггеешап, 1986), гл. 8.) Интересно отметить, что в то время важная концепция отрицательных степеней числа справа от разделяющей точки еще не была по-настоящему осознана. Лейбниц попросил Якова Бернулли (Затея Вегпоийг) вычислить х в двоичной системе счисления, и Бернулли решил задачу. Он вычислил 35-значное приближение к х, умножил его на 10Я', а затем, выразив полученное целое число в двоичной системе счисления, получил искомый ответ! Для меньшего масштабного множителя это рассуждение выглядело бы как к ж 3.14, а (314)т = (100111010)гб следовательно, и в двоичной системе счисления равно 100111010! (См.
Ье!Ьп1з, Май. БсЬг!гсеп, егЫег! Ьу К. ОеЬгЬагг!Г, 3 (На11е, 1855), 97; из-за ошибок в вычислениях два из 118 бит в ответе неверны.) Бернулли„скорее всего, выполнил эти вычисления, чтобы в таком представлении числа х выявить какие-либо простые закономерности. Шведский король Карл ХП, математический талант которого, возможно, превосходил таланты всех остальных королей в мировой ггсторни, около 1717 года увлекся восьмеричной арифметикой. Скорее всего, это было его собственное изобретение, хотя он и встречался с Лейбницем в 1707 году. Карлу казалось, что основание 8 или 64 было бы более удобным для вычислений, чем 10, и он собирался ввести восьмеричную систему в Швеции, но погиб в битве, так и не успев провести эту реформу.
(См. Сочинения Вольтера (Ъо!гшге) 21 (Рапя, Е. Й.. РиМопг, 1901), 49; Е. Бгчег!епЬогй, Сеня!этап Ъ Макая!пе 24 (1754), 423-424.) Восьмеричная система счисления была также предложена в Американских колониях Хью Джонсом (НийЬ допев), профессором колледжа шунльям и Мэри" около 1750 года (см. Оепя!етап'я Майая!пе 15 (1745), 377-379; Н. В.. РЬа1еп, АММ 56 (1949), 461-465).
Спустя столетие выдающийся американский инженер, швед по национальности, Джон Нистром (доЬп %. Нуясгопг) решил сделать еще один шаг в развитии идей Карла ХП и предложил полную систему нумерации, мер и весов, основанную на шестнадцатеричной арифметике. Он писал: "Я не боюсь и не колеблюсь выступить в защиту двоичной системы в арифметике и метрологии. Я знаю, на моей стороне природа; если мне не удастся убедить вас в ее полезности и чрезвычайной важности для человечества, это не сделает чести ни нашему поколению, ни нашим ученым и философам'.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
