Вы сможете сходу ответить на вопрос, почему в результате простейшей операции 0.1 + 0.2 в консоли браузера выведется число 0.30000000000000004?
Мы привыкли списывать такие причуды на Великие и Ужасные Особенности Языка Программирования. Ну вот работает оно так, и всё.
Согласитесь, это гораздо проще, нежели потратить десять минут на поиск информации. Но за каждым глюком скрывается фундаментальный конфликт между человеческим разумом и логикой работы конечного устройства. Мы пишем код на языках высокого уровня, оперируем привычными десятками и сотнями, а под капотами наших IDE разыгрывается нешуточная вычислительная драма.
В этой статье мы поговорим об особенностях машинной арифметики: от костылей в бортовом компьютере «Аполлона» до проблемы 2038 года. Заваривайте чаёк покрепче, и мы начинаем.
Вначале было слово
Сейчас мы воспринимаем восьмибитный байт как фундаментальную константу, нечто незыблемое и вечное, наподобие скорости света или постоянной Планка. Однако многие ранние компьютеры вообще не имели привычной нам байт-адресуемой памяти. В одних архитектурах основной единицей хранения и адресации было машинное слово, в других использовались более мелкие единицы.
В CDC 6600, например, память адресовалась 60-битными словами. Чтобы работать с отдельными символами, приходилось программно «нарезать» это гигантское слово на части (например, упаковывать по десять 6-битных символов). У советского «Минск-32» слово имело длину 37 бит (36 бит информации + 1 знаковый или контрольный разряд), а в небезызвестном PDP-8 машинное слово состояло из 12 бит.
Всё изменилось в 1964 году, когда компания IBM выпустила на рынок революционную линейку мейнфреймов System/360. Перед разработчиками встала амбициозная задача: создать универсальную машину, которая одинаково эффективно справлялась бы и с научными расчетами, и с обыкновенной бухгалтерией. Бизнесу требовалось, чтобы компьютер мог оперировать не только цифрами, но и текстом — именами клиентов, названиями товаров, адресами. А текст состоит из символов.
В то время в IBM активно использовался старый 6-битный стандарт кодирования BCD (Binary Coded Decimal). 6 бит дают всего 64 возможные комбинации. В этот скромный лимит можно было с трудом втиснуть цифры и заглавные буквы латинского алфавита. Но для полноценного документооборота бизнесу требовались строчные буквы, знаки препинания и спецсимволы.
Именно в System/360 байт был определен как 8 бит. Для работы с текстом использовалась 8-битная кодировка EBCDIC. Это решение оказалось чрезвычайно влиятельным и помогло закрепить восьмибитный байт в качестве стандартной единицы данных. Правда, с иероглифическими языками все равно были серьезные проблемы, японским и китайским инженерам пришлось немало поломать голову над тем, как втиснуть в компьютер все богатство родной письменности.
Термин «байт», к слову, придумал инженер IBM Вернер Бухгольц в 1956 году. Это был шутливый намек на то, что за раз компьютер может «откусить» только небольшую порцию данных (искажение от англ. bite — укус). Благодаря тотальному доминированию IBM System/360 на рынке, восьмибитный байт в считаные годы стал международным стандартом.
Но стандартизация не решила главную проблему: людям по-прежнему неудобно было общаться с компьютером на языке голых единиц и нулей. Попробуйте с ходу перевести, например, число 11010111 в десятичную систему, и вы поймете боль программистов первой волны. Инженеры начали искать удобные системы счисления, которые служили бы мостом между человеческим абстрактным мышлением и реальным компьютером.
Мы давно привыкли к стандартному квартету СС: двоичная, десятичная, шестнадцатеричная и восьмеричная (впрочем, с каждым годом она все сильнее сдает позиции). Но если копнуть поглубже, выясняется, что история высоких технологий — это целое кладбище удивительных, парадоксальных и, увы, забытых систем счисления. Вот о них мы и поговорим далее.
Аполлон-11 — когда у нуля есть знак
Бортовой компьютер «Аполлона-11», который в 1969 справился с задачей мягко посадить человека на Луну, является превосходным образчиком выворачивания классической математики наизнанку. Пока на Земле IBM продвигала свои восьмибитные байты, инженеры NASA боролись за каждый грамм веса и каждый милливатт энергии космического корабля. Их 15-битный компьютер использовал для представления отрицательных чисел обратный код. Соответственно, существовало и два нуля — «положительный ноль» (000000) и «отрицательный ноль» (111111). Сделаем ниже короткое пояснение.
Аппаратная реализация вычитания в процессорах часто сводится к сложению уменьшаемого с дополнительным кодом вычитаемого. Поэтому отдельный сложный арифметический механизм для вычитания не обязателен. В двоичной системе для этого используют три кода, где самый первый бит всегда указывает на знак: 0 для плюса и 1 для минуса. Для положительных чисел прямой, обратный и дополнительный коды абсолютно одинаковы. Например, число +5 в 4 битах всегда выглядит как 0101. Различия начинаются, когда нужно записать отрицательное число.
Прямой код числа -5 получается простой заменой знака на единицу, что дает 1101. Если инвертировать все биты этого числа, получится обратный код, то есть 1010. Главная проблема прямого и обратного кодов заключается в эффекте двойного нуля, когда в системе появляются сразу два значения: +0 как 0000 и -0 как 1000 или 1111. Из-за этого приходится тратить лишние ресурсы, чтобы проверять оба варианта нуля при вычислениях.
Эту проблему решает дополнительный код, который на данный момент является стандартом. Чтобы избавиться от лишнего минусового нуля, к обратному коду просто прибавляют 1. Для числа -5 мы берем его обратный код 1010, добавляем к нему 1 и получаем финальный дополнительный код 1011. При таком подходе значение -0 исчезает, превращаясь в обычный ноль 0000, а процессор может складывать любые числа на одной простой схеме.
Но дело происходило в 1960-е. Запросто могло получиться, что в ходе навигационных расчетов компьютер складывал два противоположных числа, и процессор выдавал -0. Как вы понимаете, логика управления двигателями должна была учитывать подобные нюансы, чтобы корабль банально не разбился на подлете к Луне. Разработчикам MIT приходилось выдумывать невероятные программные костыли, лишь бы компьютер понимал, что «отсутствие скорости» и «движение назад с нулевой скоростью» — это одно и то же с точки зрения физики. Ошибка в проверке знака у нуля могла уничтожить корабль вместе с астронавтами.
ЭВМ «Сетунь»: триты вместо битов
В 1959 году в стенах МГУ группа советских ученых под руководством Николая Брусенцова создала нечто крайне занимательное — ЭВМ «Сетунь». Эта машина работала на симметричной троичной системе счисления с базой 3. Ее минимальной единицей информации был не бит, а трит, который мог принимать три значения: -1, 0 и 1.
В конце 1950-х годов советские научные институты нуждались в компьютерах, но в силу новизны и сложности технологии производство ЭВМ не поспевало за спросом. Очереди растягивались на целые годы. Поэтому академик Сергей Соболев решил, что МГУ может собрать собственную компактную, недорогую и при этом надежную машину для нужд студентов и лабораторий.
Из-за дефицита деталей в целом и низкой надежности радиоламп в частности Брусенцов принял решение обратиться к физике ферритовых сердечников и диодов. Математические расчеты показали, что троичная система счисления является наиболее плотной, экономичной и эффективной для такой элементной базы. Результат, надо сказать, превзошел все ожидания.
В 1960 году «Сетунь» была испытана и, согласно информации с официального сайта МГУ, показала «95% полезного времени, определяемого как время на решение и отладку программ, не включая время на профилактический ремонт и простои ЭВМ».
На тот момент неплохим результатом считалось даже 60% полезного времени. Соответственно, сразу после испытаний было решено запустить «Сетунь» в серийное производство.
Отрицательные числа не требовали никаких специальных знаковых битов или обратных кодов — минус был частью самой системы счисления. Более того, троичная логика идеально подходила для сложных задач моделирования, где сущностям требуется промежуточное состояние (наподобие современного null).
К сожалению, проект так и не смог набрать настоящие промышленные обороты. По воспоминаниям Николая Брусенцова, новая машина, несмотря на очевидные преимущества, была «неудобна» крупным чиновникам. За все время было выпущено только 50 ЭВМ. Сняли с производства «Сетунь» тоже несправедливо рано: спрос был отменный, готовые машины хорошо показывали себя по всей стране, от юга до крайнего севера, и хорошо переносили даже неумелое обращение персонала. К сожалению, работающего экземпляра машины не сохранилось.
Затем, как известно, наступил «тихий бум» клонирования западных технологий, преодолеть который смогли лишь единицы самобытных ЭВМ и микрокомпьютеров. А о «Сетуни» незаслуженно забыли.
Как Кармак обратный корень вычислял
Когда объемы памяти выросли, а процессоры стали 32-битными, программисты практически перестали заглядывать в бинарный код. Шестнадцатеричная система (Hex) окончательно утвердилась как стандарт де-факто, поскольку оказалась тем самым идеальным интерфейсом между человеком и машиной: один байт элегантно упаковывался всего в два символа от 00 до FF, а длинные адреса превращались в компактные конструкции вроде 0x7FFF.
Так как один Hex-символ всегда равен ровно четырем битам, программист своими глазами видит границы байтов. Например, если вам нужно включить самый первый (знаковый) бит в 32-битной структуре, в Hex пишется 0x80000000. В десятичной системе это превратится в 2147483648 — абсолютно нечитаемое число, в котором битовая логика полностью скрыта. Надо сказать, в умелых руках Hex как инструмент действительно творил чудеса.
В 1999 году мир увидел культовый шутер Quake III Arena. Игра на тот момент поражала плавностью работы вкупе с отличной 3D-графикой. При этом даже на слабой машине можно было успешно поиграть на высокой частоте кадров. Секрет крылся в гениальном алгоритме быстрого вычисления обратного квадратного корня. Эта математическая операция необходима для расчета трехмерного освещения, отражений и физики частиц. Для корректной работы игры требовалось выполнять ее по несколько тысяч раз за фрейм. При этом классический подход с делением не давал нужной производительности и намертво «вешал» игру.
Представьте себе: процессор сначала должен взять число, найти его корень, а затем разделить единицу на этот корень. Операция деления чисел типа float на архитектурах тех лет была невероятно «дорогой» и занимала десятки тактов процессора: непозволительная роскошь для сложной трехмерной игры, целевая аудитория которой вряд ли располагала суперсовременным «железом».
Джон Кармак воспринял это как личный вызов. Он элегантно обошел это ограничение, провернув безумный трюк на стыке шестнадцатеричной системы счисления и стандарта хранения чисел с плавающей точкой (IEEE 754). В результате трюка дорогостоящую операцию удалось заменить несколькими дешёвыми целочисленными операциями и одним шагом метода Ньютона. На тогдашнем железе такой подход мог быть значительно быстрее стандартного вычисления через FPU. Код выглядел так:
float Q_rsqrt( float number ) {
long i;
float x2, y;
const float threehalfs = 1.5F;
x2 = number * 0.5F;
y = number;
i = ( long ) &y;
i = 0x5f3759df - ( i >> 1 );
y = ( float ) &i;
y = y ( threehalfs - ( x2 y * y ) );
return y;
}
Обратите внимание на строчку i = 0x5f3759df - ( i >> 1 );. Программа брала число типа float, временно интерпретировала его биты как обычное целое число, сдвигала всю эту бинарную цепочку на один бит вправо (i >> 1) и вычитала результат из Hex-значения.
Никто долго не мог понять математическую природу этого числа. За счет побитового сдвига и особенностей представления float алгоритм получал очень хорошее начальное приближение обратного квадратного корня, после чего уточнял его методом Ньютона. Эта строчка кода до сих пор считается одной из самых ярких вспышек инженерного гения в истории разработки.
Впрочем, не будем лукавить. В 2005 году, когда исходники Quake III были опубликованы, Кармак признался, что взял этот код из чьих-то старых наработок. Поэтому воздадим ему должное: на его месте далеко не всякому программисту хватило бы терпения и эрудиции найти подходящее решение и умело его интегрировать в свой код.
По итогам журналистского расследования, стартовавшего вслед за публикацией исходного кода, выяснилось, что корни «магического числа» 0x5f3759df уходят в 1980-е. Главным «подозреваемым» считается Грег Уолш, один из основателей Ardent Computer. Он разработал сам принцип побитового сдвига для вычисления корня, а дорабатывали и вычисляли точное значение константы математики Клив Моулер (создатель MATLAB) и Гэри Таролли (основатель легендарной компании 3dfx, создававшей видеокарты Voodoo). Кармак же просто наткнулся на этот трюк, изучая открытые кодовые базы, и применил его очень к месту.
После одного шага метода Ньютона ошибка для классической реализации снижалась примерно до 0,17%, чего для расчета освещения в игре было вполне достаточно.
Linux и восьмеричная система счисления
Пока шестнадцатеричная система счисления набирала обороты, ее предшественница, восьмеричная система (Octal), медленно отмирала. Она была популярна во времена 12- и 36-битных компьютеров, потому что позволяла разбить машинное слово на аккуратные триплеты битов (2³ = 8). С появлением восьмибитного байта нужда в Octal практически отпала. Но не везде.
Каждый системный администратор и DevOps-инженер сталкивается с восьмеричной системой на регулярной основе. С ее помощью задаются права доступа в операционных системах семейства Unix и Linux.
Когда вы пишете в терминале команду chmod 755, вы используете Octal. Дело в том, что права доступа к файлам в Linux состоят из трех групп (владелец, группа, остальные), и внутри каждой группы есть ровно три флага: чтение (r), запись (w) и исполнение (x).Каждая группа — это идеальный трехбитный триплет.
Например, 111 в двоичной системе — это 7 в восьмеричной (полные права: rwx). 101 в двоичной системе — это 5 в восьмеричной (чтение и исполнение: r-x). Если бы создатели Unix использовали шестнадцатеричную систему, кодировать права было бы неудобно: оставались бы «лишние» биты, которые ломали бы всю красоту подхода. Восьмеричная система счисления идеально легла на эту концепцию – и поэтому еще долгое время останется актуальна, пусть даже в таком рудиментарном виде.
Unix Epochalypse
Все эти исторические курьезы и хаки из девяностых могут показаться делами давно минувших дней. Теперь у нас есть терабайты памяти, мощные IDE и 64-битные процессоры, так что подобные проблемы, казалось бы, должны остаться в прошлом. Но прямо сейчас в самом сердце миллиардов цифровых устройств тикает часовая бомба, заложенная еще создателями операционной системы Unix. Называется она проблемой 2038 года (или Y2K38).
Как современный компьютер определяет сегодняшнее число и время суток? В Unix-подобных системах (включая Linux, macOS, Android и прошивки роутеров и прочих умных чайников) время отсчитывается в секундах, прошедших с полуночи 1 января 1970 года. Эта концепция называется Unix Epoch (Эпоха Unix). Проблема возникает в старых системах и legacy-коде, где time_t реализован как 32-битное знаковое целое число. Один бит используется под знак, поэтому для счетчика секунд остаётся 31 бит. Максимальное значение — 2³¹ - 1, или 2 147 483 647 секунд.
А теперь переведем эти секунды в понятные нам даты. Счетчик заполнится 19 января 2038 года в 03:14:07 по всемирному времени (UTC). В эту секунду 32-битный регистр времени будет выглядеть в двоичном коде как 01111111 11111111 11111111 11111111.
Что произойдет ровно через одну секунду, в 03:14:08? Переполнение. Вся цепочка единиц превратится в нули, а в самый левый знаковый бит перенесется единица. Компьютер увидит строку 10000000 00000000 00000000 00000000. Эта комбинация означает минимально возможное отрицательное число: -2 147 483 648. Для операционной системы время мгновенно открутится назад на 68 лет от начала Unix Epoch, в 13 декабря 1901 года.
В зависимости от конкретной системы последствия могут быть очень разными — от некорректных дат и логов до ошибок в базах данных, планировщиках, протоколах и программном обеспечении, которое работает с сертификатами и сроками действия.
И если современные десктопы и смартфоны уже давно перешли на 64-битные процессоры и типы данных (где лимита времени хватит еще на 292 миллиарда лет), то в мире интернета вещей (IoT), встроенных систем и старого софта эта проблема стоит невероятно остро.
Разумеется, решения уже есть, и они планомерно внедряются. На современных 64-битных Linux-системах классическая проблема переполнения 32-битного time_t уже не актуальна — время представляется 64-битными значениями. А вот старые 32-битные системы и embedded-устройства по-прежнему требуют отдельной проверки.
Для устройств, физически неспособных обрабатывать 64-битные числа, было решено убрать бит знака и тем самым отвести под хранение времени все доступные 32 бита. Компьютер полностью теряет способность понимать даты до 1970 года (они превращаются в огромные числа из будущего), но для условных датчика температуры в прихожей или умной плиты это совершенно не критично. В этом случае «большой барабум» переносится на 7 февраля 2106 года.
Последний вариант – Time Windowing. Если перепрошить устройство не получится, можно создать над ним слой абстракции. Пускай древняя БД «думает», что на дворе 1996 год – мы-то знаем, что отмотали ей время ровно на 30 лет назад, и будем учитывать сдвиг, получая из нее даты. Этот метод применяется в старых закрытых коммерческих программах, исходный код которых утерян, а сами они зашиты в ПЗУ станков или банковских терминалов.
Так что запасаться попкорном и ждать очередного апокалипсиса в духе 2000 года не стоит. Просто не говорите своей старой-доброй микроволновке, что будущее уже наступило.
Вся история программирования — это хроника компромиссов. Мы берем бесконечно огромный, плавный и живой аналоговый мир, пропускаем его через мясорубку дискретных систем счисления, а после героически пишем костыли, чтобы сгладить углы, допущения, шероховатости и неточности.
Мы молодцы. Мы научили компьютер понимать буквы. Заставили шестнадцатеричные константы участвовать в просчете физики света в 3D-играх. Даже права доступа красиво упаковали в восьмеричную СС. Однако мыслить по-человечески компьютер от этого не стал.
Совсем скоро этот зоопарк тоже станет частью истории. Эра квантовых вычислений готовит революцию, которая вообще уничтожит привычное понятие систем счисления. Квантовый кубит работает по совершенно иным законам. Но пока этого не произошло, следует помнить: за каждым элегантным интерфейсом на реакте или строчкой кода на питоне всегда стоят регистры памяти. И побеждает тот программист, который умеет думать не только абстракциями высокого уровня, но и понимает, как его код выглядит там, в самом низу, в виде череды единиц и нулей.
P.S.
В JavaScript (и многих других языках программирования) выражение 0.1 + 0.2 возвращает 0.30000000000000004 из-за особенностей двоичного представления чисел с плавающей точкой. Компьютеры не могут с совершенной точностью записать некоторые десятичные дроби в двоичной системе.
JavaScript использует стандарт IEEE 754. На каждое число выделяется ровно 64 бита памяти. Бесконечная дробь обрезается и округляется. При сложении двух уже округленных чисел погрешности суммируются, и на конце появляется лишняя четверка.
