Здравствуйте, друзья, как вы думаете, если мы напишем такой код:
s = a+b;
z = s-a;
t = b-z;
то не кажется ли вам, что в результате его выполнения получится, что t=0? С точки зрения привычной математики действительных чисел это и правда так, а вот с точки зрения арифметики с плавающей запятой в переменной t будет кое-что другое. Там будет то, что спасает нас от потери точности при сложении чисел 
и 
. Кого интересует данная тема, прошу под кат.
Вы сталкивались когда-нибудь с построением (непрерывного) пути обхода кривой на плоскости, заданной отрезками и кривыми Безье?
Вроде бы не сильно сложная задача: состыковать отрезки кривых в один путь и обойти его "не отрывая пера". Замкнутая кривая обходится в одном направлении, ответвления — в прямом и обратном, начало и конец в одном узле.
Всё было хорошо, пока из-под рук дизайнеров не стали вылезать монструозные пути, где отдельные кривые могли пересекаться или не точно состыковываться. Объяснение было предельно простым — визуально они все лежат как надо, а для станка, который этот путь будет обходить, такие отклонения незаметны.
Вооружившись знанием о величине максимально допустимого отклонения, я приступил к исследованию, результатами которого хочу поделиться.
Думаю, с переводом чисел в ASCII строки в своей жизни сталкивался каждый программист. В свое время для меня было удивительно узнать, что перевод десятичной цифры в равнозначный ASCII символ – операция сложения. С этим знанием я ложился спать, и с этим же знанием я бодро просыпался утром. Но однажды я задал себе вопрос – а как переводятся числа с плавающей запятой: Float или Double!? С этого момента, сна в моей жизни, а тем более крепкого и спокойного – стало меньше. Уверен, не я один задавался этим вопросом, и более того, не я один нашел ответ на оный. Но я думаю, есть те, кто заблудился, те, кто до сих пор неровно дышит от полного непонимания, что же происходит под капотом этих ваших трансляторов, компиляторов и прочего-прочего. Более того, не только полное отсутствие знаний в трансляции чисел нарушало мое психическое равновесие: люди, услышавшие мои душевные страдания, кидали сомнения в нужности и полезности этого знания. Мне говорили так: “Ну раскроешь ты завесу тайны, а дальше то что?! Напишешь свой велосипед, который будет работать в сто раз медленнее?! Иди ка ты, Ваня, асфальт укладывай, а мы тут великим займемся – вон, JSON пришел, надо еще подумать, как его переложить...”. Я же, парировал: “Нет, я напишу мотоцикл! Он будет быстр как Ямаха, а его рев будет устрашать даже матерых программистов!”.Читать полностью »
Стандарт С++ почти никогда не указывает, как именно должен быть реализован тот или иной std алгоритм. Дается только описание того, что на входе, что на выходе и асимптотические ограничения по времени работы и памяти. В статье я постарался прикинуть, какие математические алгоритмы и структуры данных имели ввиду авторы стандарта, указывая ограничения для той или иной сортировки и для некоторых других алгоритмов. А так же как эти алгоритмы реализованы на практике.
При написании статьи я использовал стандарт C++17. В качестве реализаций рассматривал GCC 10.1.0 (май 2020) и LLVM/Clang 10.0.0 (март 2020). В каждой и них есть своя реализация STL, а значит и std алгоритмов.
Вы наверняка уже использовали в своих проектах UUID и полагали, что они уникальны. Давайте рассмотрим основные аспекты реализации и разберёмся, почему UUID практически уникальны, поскольку существует мизерная возможность возникновения одинаковых значений.
Современную реализацию UUID можно проследить до RFC 4122, в котором описано пять разных подходов к генерированию этих идентификаторов. Мы рассмотрим каждый из них и пройдёмся по реализации версии 1 и версии 4.
Читать полностью »
Задача движения юнитов в играх является одной из ключевых задач, стоящих перед разработчиками игр. От того, как двигаются игровые юниты, во многом зависит восприятие всего геймплея в целом.
Традиционно считается, что достаточно реализовать алгоритм поиска пути и дальше всё будет работать само собой.
На практике же мы имеем совсем другую ситуацию.
Алгоритмы поиска пути разобраны досконально.
Нужен поиск пути с весами? A*. Нужен поиск для большого количества юнитов? Flow Field или кластеризация.
По большому счету по поиску пути не осталось не разобранных вопросов.
И вот, поиск пути реализован и довольный игродел запускает свою игру… И видит, что болванчики полностью оправдывают своё название. Они конечно находят путь и едут туда, куда им сказали. Но при этом спотыкаются о препятствия… Толкаются друг с другом или проезжают насквозь… Упираются друг в друга при встречном движении…
Эти проблемы и будем сегодня решать.
Если вы разработчик и перед вами стоит задача выбора кодировки, то почти всегда правильным решением будет Юникод. Конкретный способ представления зависит от контекста, но чаще всего тут тоже есть универсальный ответ — UTF-8. Он хорош тем, что позволяет использовать все символы Юникода, не тратя слишком много байт в большинстве случаев. Правда, для языков, использующих не только латиницу, «не слишком много» — это как минимум два байта на символ. Можно ли лучше, не возвращаясь к доисторическим кодировкам, ограничивающим нас всего 256 доступными символами?
Ниже предлагаю ознакомиться с моей попыткой дать ответ на этот вопрос и реализацию относительно простого алгоритма, позволяющего хранить строчки на большинстве языков мира, не добавляя той избыточности, которая есть в UTF-8.Читать полностью »
В этой статье автор предложил написать свои книги, которые относятся к разряду неувядающей классики. Я написал несколько книг в комментариях, а потом решил, что достойных книг гораздо больше, и решил написать статью. Если в оригинальной статье был сделан упор на электронику, то у меня будет упор на разработку программ.
Disclaimer: это мой личный топ из тех книг, которые я лично прочитал, и у которых первое издание было в прошлом веке, даже если она переиздавалась недавно (при условии актуальности именно того издания, которое было в прошлом веке).
Мой CNC-роутер служил верой и правдой два года, но что-то пошло не так слетела прошивка, а был это woodpecker 0.9.
Сначала я хотел ее просто перезалить, и, с этой целью раздобыл исходные коды Grbl CNC Project. Но любопытство пересилило и я погрузился в изучение этих исходников…
Построены они очень просто и логично, но какой же русский не любит быстрой езды как же можно пройти мимо возможности что-нибудь подковать улучшить! По мотивам того что получилось, эта короткая воскресная заметка.
С удивлением обнаружил, что на русском языке трудно отыскать информацию по данной проблеме, как будто мало кого волнует, что математические библиотеки, используемые в современных компиляторах, иногда не дают корректно-округлённого результата. Меня эта ситуация волнует, так как я как раз занимаюсь разработкой таких математических библиотек. В иностранной литературе эта проблема освещена хорошо, вот я и решил в научно-популярной форме изложить её на русском языке, опираясь на западные источники и пока ещё небольшой личный опыт.
Читать полностью »