В пещерах этого не было

в 12:24, , рубрики: математика, Программирование

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

image

Глава 0. Base-1

Когда я учился в школе (199x) все сидели на Pascal – язык чёткий, мудрый, на нём даже Dos Navigator был написан c VESA скринсейверами, а позже The Bat!, и олимпиадники ACM ICPC в 2000-е годы были в основном паскалистами. Мне из-за любви к играм и графике в то время зашёл C/C++, и сразу же в глаза бросилось фундаментальное различие – от ноля или единицы индексируются массивы, это до сих пор приходится уточнять на том же hackerrank.com.

Всё исходит из человеческой психологии, но не всё вовремя пересматривается. От единицы исторически в речи нумеруют по причине, каким был по счёту объект, когда он был добавлен – отсюда «первый», «второй» — т.е. сколько их стало после добавления. Но для компов это неудобно, т.к. проще оперировать смещениями – на сколько байт надо перепрыгнуть от базового адреса, поэтому «нулевой», «первый». Из-за этого паскалевские конструкции вида FOR N := 1 TO N DO излишне нагружают ALU либо превращаются в квест для компилятора.

Есть еще один момент, где 1..N индексация даёт себя знать по сравнению с [0;N) индексацией – это работа с float’ами. Если требуется собрать несколько сегментов встык ala [a0;a1) U [a1;a2) U [a2;a3) – не возникает «магических чисел» вида a1+1, a2+1 – конец одного сегмента является началом следующего, и этот критерий работает что для целых, что для вещественных чисел. В 1..N нотации даже для целых начинаются плюс-минус-единицы, а для вещественных по идее вообще никак :) хотя на C++ есть лайфхак (int&)++floatVariable; Большинство off-by-one-errors и сопутствующих им buffer overrun происходит как раз из-за этого.

Глава 1. Little-Big-Adventure

image

Сначала в пещерах были палочки/насечки, чтобы научиться считать и освоить базовую арифметику. Потом в Египте придумали концепцию нуля/ноля (back to the roots of 0-indexed). Дальше были римские числа – красивые/гламурные/винтажные, но деление, как я слышал, изучали на четвёртом курсе университетов.

После этого цивилизация переключилась на порядковую систему передач — пришла с арабской стороны; десятичная, видимо, по количеству пальцев. Но вот незадача — у них по каким-то причинам пишут справа налево (об этом ниже), а импортировали as is, и с тех пор пишем числа от старшего разряда к младшему, хоть глазами и бегаем слева направо. При этом практически все операции выполняем от младшего к старшему – вспомните ручное сложение и умножение «в столбик» в тетрадке, справа налево. Единственная операция, которая требует ориентации слева направо – это сравнение (и деление, т.к. завязано на сравнение), но и там числа предварительно выравнивают по правому краю, подразумевая лидирующие нули слева.

Теперь, собственно, к IT. Когда начали проектировать процессоры и программирование, недообдуманные человеческие привычки просочились в распайку транзисторов – возник big-endian (старший разряд в первых байтах). Потом было много холиваров о том, что это, мол, вопрос привычки и роли не играет. Роль это играет – в случае little-endian смещение байта соответствует степени двойки, которой он соответствует. Как человек, познакомившийся с x86 ассемблером на 8086 в ~10 лет, я до сих пор помню такие вещи как BL/BH/BX (позже EBX, еще позже RBX) – и когда надо кастануть 32-битный int в 8-битный, ALU вообще не требуется – это сугубо вопрос интерпретации, базовый адрес остаётся тем же. Поэтому работает такая штука, как «кармическое воздаяние» — мотороллы, PowerPC и SPARC’и остались только в банковской сфере, с нормального рынка они повылетали даже после захода на XBOX/PS приставки. ARM тем временем старается угодить и тем, и другим, и тратит на это литографический бюджет – как-то endianness в нём переключается.

Оттуда же у нас такие вещи как htonl и ntohl (host-to-network-long / network-to-host-long). Мотивируется всё это тем, что сисадминам в дремучие годы было психологически проще читать дампы, но мотивация, если честно, странная – если ты и так перепрошил свою биологическую нейронку c десятичной системы на шестнадцатеричную – для достижения полного дзэна достаточно всего одного шага на extended перепрошивку мозга в математически-естественный порядок младший->старший, по возрастанию адреса.

И были холивары на эту тему, и кто-то даже прикололся в RFC с лилипутами Блефуску и нарисовал всё сверху вниз. Нюанс в том, что в компе это всё не симметрично. Речь не про лево/право или верх/низ – речь о том, идёт ли оно по возрастанию адреса или по убыванию. Когда выделяется память, мы оперируем адресом первого нулевого байта, а не последнего. Когда мы дёргаем malloc/realloc – отсчёт идёт со старта. Часто кэши работают как read-ahead и write-behind, особенно на механических HDD – т.е. упор идёт на возрастание адреса, симметрии с убыванием тут нет.

Едем дальше. Когда речь идёт про «одноразовые» 8/16/32/64-битные числа – оно в принципе действительно не так уж важно и смахивает на холивар. Но бывает еще «длинная арифметика» в сотни цифр. При сложении можно в little-endian на ADD/ADC (x86) выехать, рассматривая куски длинного числа как 32/64-битные, т.е. при сложении число рассматривается как base-2^64, а при умножении, чтобы не переполниться, можно рассмотреть длинное число как, к примеру, base-2^8 – вопрос интерпретации — и никаких SIB выкрутасов для этого не потребуется, чтобы вертеть каждые 4 байта на ALU. В случае big-endian – welcome to hell.

Глава 2. XYZ

image

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

Когда что-то пишешь, важен контекст — важен “backspace головного мозга” – т.е. желательно видеть только что набранное. Представим себе стандартного питекантропа у пергамента или каменной стены, и он правша. Чтобы видеть уже «набранный» текст и учитывая физиологию организма (правша) — текст пишется слева направо и сверху вниз. Отсюда, вероятно, возникла ось X как слева направо. Тем временем в параллельной реальности, видимо, доминировали левши — отсюда RTL BiDi (right-to-left bidirectional заморочки) и упомянутый выше endianness.|

Дальше — ось Y, вертикаль. Рене Декарт, а скорее всего раньше. Могли направить вверх, могли направить вниз. Полагаю, что вниз не направили, чтобы не думать лишний раз об Осирисе :) Но при этом всём супер-физики и супер-математики всего мира изобретают телевизор и… ось Y направлена вниз – развёртка ЭЛТ кинескопа идёт сверху вниз, и до сих пор технологически по HDMI в LCD так же попадает. Полагаю, что пиксели первого ЭЛТ кинескопа проассоциировали с направлением письма.

Дальше 3D веселуха – идём по оси Z. У одних (DirectX) она направлена из глаза. У других (OpenGL) в глаз. У третьих (Maya/3D-Max/Blender) она местами вертикально стоит. Связано опять же с психологией. Кто-то привык воспринимать геометрию с школьной/университетской доски — тогда Z логично идёт в направлении от, а кто-то привык дома на столе чертежи рисовать — и тогда XY плашмя на столе, а Z вверх под люстру с комарами. Я посмеялся в своё время, когда в DirectX(10-11) Z-Buffer толерантно переименовали в Depth-Buffer :)

К теме, почему ось Z идёт из глаза (DirectX) или в глаз (early OpenGL, maybe now too). Есть такая штука как правоориентированный или левоориентированный базис, чтобы на векторном произведении работало «правило буравчика» или «правило отвёртки» — крутишь первый вектор во второй — получаешь направление результата. Правая резьба / левая резьба – всё о том же самом, под какую руку оно физиологически удобней. Нюанс в том, что при устоявшихся математических X-вправо, Y-вверх получается, что логичный Z-вдаль порождает левоориентированный базис, что и покусали в OpenGL, направив Z внутрь в глаз тупо ради правоориентированного базиса, но оно математически криво, т.к. работать приходится с отрицательными числами.

Есть и другая попроще версия, почему XY то спереди, то плашмя. И почему Z то в бровь, то в глаз.

image

А чем дальше, тем круче. Люди не смогли договориться о том, как писать вектора – в строку или в столбец. Меня в российском универе (ПетрГУ) учили в столбец. В OpenGL вроде та же ситуация. В DirectX в MSDN сталкиваюсь со строчной записью – и она мной воспринимается как непривычная, но более логичная. По одной простой причине – если flow мозга работает слева направо (я правша), то каскад преобразований в случае строчного представления вектора выглядит по ходу пьесы и чтения, т.е. VxM1xM2xM3, а не в обратном операторном порядке M3(M2(M1(V))), и в HLSL в итоге имеем декларацию ориентации матриц, чтобы всем было удобно row/column. Everybody’s business is nobody’s business.

Back to XY. В своё время еще по школе меня удивила постановка вопроса про синус и косинус. Этимологически косинус — нечто, сопряжённое синусу (ко-синус). Тем не менее, более «первичный» синус определяют как отношение противолежащего катета к гипотенузе, хотя обсуждаемый угол образует прилежащий — и он вроде ближе. Непонятный «перевёртыш», правда математически логичный, т.к. sin(0)=0 и sin'(0)=1 (у косинуса ТТХ хуже). Та же ситуация с тангенсом и ко-тангенсом, технически тангенс можно было определить и как cos(x)/sin(x). Тангенс в том виде, в котором он есть, просто более логичен с математической точки зрения. А теперь, внимание, вопрос:

Почему, когда начали рисовать «стандартный математический круг» с радианами — первичный «синус» положили на вторичную ось Y, а вторичный «косинус» положили на первичный X? (X «первичный» по той простой причине, что когда мы, человеки, обсуждаем что-нибудь одномерное, мы это делаем по-горизонтали). Отсюда возникает «ломка мозгов», что есть часовая стрелка, а есть еще и математическая. Одна стартует сверху-по-центру, а вторая сбоку-припёку. Плюс направление приходится в башке вращать. Плюс все эти Culling mode в DirectX'ах с CW/CCW (clockwise/counter-clockwise) и т.д. и т.п.

Представим на момент, что перевёртыша не было, т.е. X0=X=sine, X1=Y=cosine. sin(0)=0, cos(0)=1. Брюки превращаются в…

В пещерах этого не было - 5

элегантный clockwise. Вместо того классического легаси недорефакторинга, с которым приходится иметь дело. Вероятно, с тех пор, как sin(x) versus x привыкли рисовать по ординатам, как функцию.

(...to be continued MMXX...)

Eternal P.S: Все эти «репризы эпистолярного жанра» не просто так. Часто в жизни возникают моменты, когда ты что-то придумываешь, а тебя осекают фразами вида «так неудобно». Ты начинаешь рефлексировать, включать режим отладки головного мозга, — только ради того, чтобы прийти к выводу, что «неудобно == непривычно». Отсюда и название статьи — full reset до пещер, когда придумок не было, чтобы понять — где придумки, а где реальная физика мира. Периодически имеет смысл сделать retrace своей жизни и взглядов при иных входных данных. Часто «неудобное» вдруг становится «удобным», а непривычное привычным, или наоборот. Это — основа рефакторинга.

Автор: Денис Кошман

Источник

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js