Квизы и задачи

Условие С заброшенной орбитальной станции «Гелиос-1» поступил сигнал с архивного сервера, который никто не выключал с прошлого века. Инженер-подрядчик Марина восстановила связь с бортовым хронистом — древним контроллером, который с момента запуска станции ведет журнал телеметрии. Внутри станции время считает отдельный аппаратный счетчик — кварцевый таймер, который с 1 января 1970 года 00:00:00 UTC исправно тикает раз в секунду и хранит свое значение как обычное целое число, не подверженное округлению. Проблема не в этом счетчике, а в формате архивного журнала: чтобы упростить парсер на старом контроллере, разработчики станции сделали единый формат записи для всех каналов телеметрии — температуры, давления, углов ориентации, заряда батареи — где каждое поле, включая метку времени, кодируется как IEEE 754 float32 с 24 битами точности на мантиссу. При формировании каждой записи текущее точное время просто конвертируется в float32 и пишется в лог — заново, с нуля, а не накоплением через прибавление секунд к уже сохраненному float-значению. Марина заметила: чем «древнее» становится станция, тем чаще идущие подряд записи телеметрии получают одинаковый таймстамп. В журнале станции таймстамп служит уникальным ключом записи, поэтому при совпадении новая запись перезаписывает предыдущую — они буквально стирают друг друга. Судя по всему, где-то по дороге числа перестали помещаться в отведенную точность. Задача Определите точные даты (UTC), когда точность таймстампа станции последовательно падает с 1 секунды до 2, 4, 8 секунд и так далее — вплоть до сегодняшнего дня. С каким интервалом сейчас могут столкнуться два события в журнале станции, если она считает время без остановки с 1 января 1970 года 00:00:00 UTC? Решение У числа с плавающей точкой одинарной точности мантисса — 24 бита (23 явных плюс скрытая единица). Это значит, что все целые числа от 0 до 2^24 включительно хранятся точно, а начиная с 2^24 + 1 часть целых значений уже невозможно представить без округления. До отметки 2^24 шаг между соседними представимыми числами равен 1 секунде. Дальше этот шаг (в терминологии IEEE 754 — ULP, unit in the last place) удваивается на каждой степени двойки: от 2^24 до 2^25 — шаг 2 секунды, от 2^25 до 2^26 — шаг 4, и так далее. Это и называется «утечка на стыке эпох»: станция пересекает границы двоичных эпох, и с каждой границей расстояние между соседними представимыми значениями удваивается. Здесь и далее секунды считаются как в стандарте Unix time — без учета високосных секунд (leap seconds). Важное уточнение архитектуры: точность «плывет» именно потому, что в float32 каждый раз конвертируется точное время из аппаратного счетчика, а результат округляется до ближайшего представимого значения независимо для каждой записи. Если бы вместо этого станция хранила текущее время прямо в float32-регистре и каждую секунду прибавляла к нему единицу (t t + 1), эффект был бы куда драматичнее часов, теряющих точность: начиная с t 2^24, операция t + 1 попадает ровно на середину между двумя соседними представимыми числами, и по правилу округления «к ближайшему четному» (round-half-to-even) результат всегда откатывается обратно к t. Часы в такой схеме не деградировали бы постепенно — они замерли бы навсегда в первый же момент пересечения границы 2^24. Именно поэтому в реальной прошивке накопление ведется в точном (целочисленном/аппаратном) счетчике, а float32 используется только как формат записи в архив — иначе станция замолчала бы уже 14 июля 1970 года. Способ №1. Математический Порог для шага в 2^k секунд наступает при t 2^(23+k). Переводим пороги в точные даты и время (UTC, с точностью до секунды) от эпохи Unix: 2^24 c — 14 июля 1970, 04:20:16 — шаг 2 с 2^25 c — 24 января 1971, 08:40:32 — шаг 4 с 2^26 c — 16 февраля 1972, 17:21:04 — шаг 8 с 2^27 c — 3 апреля 1974, 10:42:08 — шаг 16 с 2^28 c — 4 июля 1978, 21:24:16 — шаг 32 с 2^29 c — 5 января 1987, 18:48:32 — шаг 64 с 2^30 c — 10 января 2004, 13:37:04 — шаг 128 с 2^31 c — 19 января 2038, 03:14:08 — шаг 256 с (станция это еще не застала) Спустя больше полувека работы станции таймстамп перевалил за 2^30 и еще не достиг 2^31 — значит, шаг между соседними представимыми значениями сейчас равен 128 секундам: таймстамп может принимать только значения, кратные 128. Два разных события не обязательно получат одинаковые таймстампы, даже если разница между ними меньше 128 секунд, — всё зависит от того, куда именно относительно этой 128-секундной сетки попадают оба момента. Если оба события укладываются в один и тот же интервал округления, они сольются в одну запись; а если разница приходится ровно на границу интервала, то даже событие, случившееся секундой позже, может получить уже другой, соседний таймстамп. Способ №2. Проверим на Python Напишем короткий скрипт, который сам вычислит, сколько порогов уже пройдено (через now.bit_length()), посчитает даты порогов и текущий шаг коллизий, выведет результат, а заодно проверит поведение округления на настоящем float32 через numpy: После запуска кода получаем: Результат подтверждает расчеты: начиная с 2004 года и по сей день (пока в 2038 году порог не сдвинется снова) станция хранит время с шагом 128 секунд — таймстамп способен различать события только с точностью до этого шага. Два события могут получить одинаковый таймстамп, если попадают в один и тот же 128-секундный интервал округления, а могут не совпасть, даже если разделены всего секундой, — это целиком зависит от их положения на сетке округления, а не от самой разницы во времени. Второй эксперимент с накоплением t t + 1 прямо во float32 наглядно показывает, почему так делать нельзя: последовательность быстро выходит на 16777216.0 и дальше не сдвигается ни на шаг, сколько бы секунд ни прошло. Это и есть та самая «бомба замедленного действия»: если бы часы станции работали именно так, они замолчали бы навсегда уже в июле 1970 года, а не деградировали бы постепенно. Заключение Марина закрыла тикет с формулировкой «не баг, а особенность математики» и заменила float32 на int64 в новой прошивке — со знаковым 64-битным целым счет в секундах не переполнится еще около 292 миллиардов лет, так что станции повторное появление этой проблемы больше не грозит.