Хочу в очередной раз затронуть метод реализации умножения Карацубы с использованием возможностей стандарта C++11. Данный алгоритм неоднократно рассматривался здесь («Умножение длинных чисел методом Карацубы», «Алгоритм Карацубы для умножения двух чисел»), но видимо из-за того, что я не умею их готовить, первый вариант не работал с числами разной длины, а второй делает не совсем то, что было нужно.

Для тех, кто не устал от этой заезженной темы, а также всех, кто испытывает трудности с реализацией этого простого, но очень эффективного алгоритма, прошу читать дальше.

Я много раз сталкивался с задачей динамической генерации кода (например, при написании эффективного сериализатора или компилятора DSL). Это можно делать разными способами, какой из них лучший – дискуссия для отдельной статьи. По ряду причин я предпочитаю Reflection.Emit и CIL (Common Intermediate Language) и расскажу, с какими проблемами пришлось столкнуться на этом пути, а также об их решении: умной обертке над ILGenerator – GroboIL из библиотеки Graceful Emit.

Хочу отметить при этом, что иногда встречаются ситуации, когда у нас нет большого выбора: например, при написании сериализатора необходимо иметь доступ к приватным полям, и приходится использовать IL. Кстати, известный сериализатор protobuf-net содержит несколько сотен IL-инструкций.

Если вы ни разу не сталкивались с использованием IL-кода, то статья может показаться сложной для понимания, поскольку содержит много примеров кода с использованием IL. Для получения базовых знаний рекомендую прочитать статью Introduction to IL Assembly Language.

Реализация поведения юнитов в RTS играх может стать серьезной проблемой. Компьютер, зачастую, контролирует огромное количество юнитов, в том числе и принадлежащих игроку, которые должны передвигаться в большом динамическом мире, попутно избегая столкновения друг с другом, выискивая врагов, защищая собственные базы и координируя атаки для истребления противника. Стратегии реального времени работают в реальном времени, что делает довольно сложным слежение за планированием действий и навигацией.

Этот урок описывает метод планирования течения игры и навигации юнитов, который использует многоагентные потенциальные поля. Он основан на работах под номерами [1, 2, 3]. (Смотри в конце статьи ссылки на используемые материалы)

Часто возникает задача сохранить изменяемые данные, например конфигурацию, во флэш памяти микроконтроллера. Решение кажется простым, однако обеспечить надежность обновления данных при условии, что питание может отключиться в любой момент, оказывается весьма нетривиально, и даже использование контрольных сумм не решает проблему полностью. Из этой статьи вы узнаете

• как устроена флэш память
• к каким проблемам приводит выключение питания в момент записи или стирания
• как эти проблемы решаются

Для желающих применить на практике — работающий код под STM32F4

«Галоп пикселя», часть I — базовые понятия, этапы взросления, прикладные упражнения (линк)
«Галоп пикселя», часть II — перспектива, цвет, анатомия и прикладные упражнения (линк)
«Галоп пикселя», часть III — Анимация (линк)
«Галоп пикселя», часть IV — Анимация света и тени (линк)
«Галоп пикселя», часть V — Анимация персонажей. Ходьба (линк)линк)

Первая статья данного цикла была воспринята тепло, вследствие чего затягивать с продолжением не имело никакого смысла, но, увы – это произошло. Зимнее наступление захлебнулось и плавно переросло в летнюю кампанию. В конце статьи я объясню почему, не хотелось бы вас огорчать с самых первых строк. Итак. Публика выразила желание ознакомиться с предметом глубже, чем предполагалось изначально. Большое количество писем пришло на почту, наряду с регулярными тычками в социальных сетях. В этом месте мне вспоминается одна фраза – «будьте осторожны в своих желаниях».

Сегодня мы продолжаем диалог о пиксель-арте, методах его создания и приёмах в работе с ним. Сегодняшняя статья будет чуть более сложной в освоении, ведь мы уже прошли истоки и ознакомились с базовыми понятиями. Сегодня мы ударим и по теории, с примерами из мира игр, и коснемся конкретных приемов в работе с пиксель-артом. Если вы не любите теорию и не считаете её важной частью обучения – смело прыгайте в лифт и спускайтесь на нижние этажи, с выходом на уровнях анатомии и цвета. Каждый этаж маркирован авторским пиксель-артом, не пропустите.
Те же, кто остался по доброй воле, и те несчастные, кому по какой-то причине не хватило места в лифте, узнают, почему в предыдущей публикации не были затронуты – композиция, перспектива, анатомия и цвет, сущности столь важные в изобразительном искусстве.

Не будем мешкать. Возьмем наши пиксельные лопатки и двинемся на врага сплоченной группой. Быть может, нам повезет, и кто-нибудь, выжив, расскажет потомкам о ещё одной битве Теоретического войска возле местечка, вошедшего в историю сети как Хаброва падь.

«Галоп пикселя», часть I — базовые понятия, этапы взросления, прикладные упражнения (линк)
«Галоп пикселя», часть II — перспектива, цвет, анатомия и прикладные упражнения (линк)
«Галоп пикселя», часть III — Анимация (линк)
«Галоп пикселя», часть IV — Анимация света и тени (линк)
«Галоп пикселя», часть V — Анимация персонажей. Ходьба (линк)
«Галоп пикселя», часть VI — Анимация персонажей. Бег (линк)

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

В данной публикации мы не рассматриваем программы, но копаем нечто большее. Сами пиксели. От истоков, начав с четырехцветной CGA-эры, вплоть до эпохи ренессанса. В публикации мы не рассматриваем игры, не поем дифирамбы художникам прошлого (разве что самую малость), занимаясь именно процессом создания простейшего пиксель-арта. Данный материал будет интересен начинающим артистам и интересующимся. Статья практически не содержит теории, нудных умозаключений и представляет сторонний взгляд на мир пиксель-арта со стороны некоего самоучки, который предпочел открыть каждую из Америк самостоятельно, не оглядываясь на официальных, общепризнанных и задокументированных Колумбов. Статья снабжена обильным количеством поясняющих иллюстраций, примеров, и советов.

Материал разделен на несколько публикаций в виду объема текста и изображений. Каждая статья имеет свою степень сложности, однако, все из них наглядны и могут быть использованы как руководство к действию.

Недавно мы в «Я люблю ИП» закончили курсы по дизайну от trydesignlab.com. И это одна из самых важных статей, которую нам посоветовал ментор в процессе обучения. Именно поэтому мы решили её перевести. Посмотреть все наши работы с курсов можно в ВКонтакте по тэгу #design101@iloveip.

Вступление

Сначала о главном. Это руководство не для всех. Это руководство прежде всего для:

• разработчиков, которые хотят уметь делать хорошие интерфейсы для себя, если вдруг прижмёт;
• UX-дизайнеров, которые знают, что хороший UX-дизайн продаётся лучше в красивой UI-упаковке.

Если вы ходили в художественную школу или считаете себя хорошим дизайнером интерфейсов, то скорее всего это руководство покажется вам а) скучным, б) неправильным или даже в) вызывающим раздражение. Это нормально. Просто закройте эту вкладку и двигайтесь дальше.

А пока давайте я расскажу, что вы найдёте в этой статье.

Понятие энтропии в середине XX века ввёл Клод Шеннон. Её можно интуитивно описать как «среднее количестве битов информации в одном значении случайной величины». Но её нельзя применить к индивидуальным объектам (скажем, к тексту романа или ДНК) — где нет ансамбля многих однородных объектов, нет и случайных величин.



В середине 1960-х годов разным людям (Колмогоров, Соломонов, Левин, Чейтин) стало понятно, что можно определять количество информации (сложность) индивидуального объекта как минимальную длину программы, которая этот объект порождает (при естественных ограничениях на язык программирования). Возникла алгоритмическая теория информации, которая оказалась связанной с разными областями: от философских вопросов оснований теории вероятностей (когда мы отвергаем статистические гипотезы?) до комбинаторики (неравенства, связывающие размеры множеств и их проекций) и теории вычислимости.

Лекцию, которую мы выбрали для вас сегодня, читал на факультете компьютерных наук Вышки известный математик Александр Шень. Когда-то он под руководством Владимира Успенского, ученика Колмогорова, защитил диссертацию «Алгоритмические варианты понятия энтропии».

Финальный этап создания электронного продукта — серийное производство, именно оно в конечном итоге определяет качество устройства. Пользователь не сможет оценить идеальную программную и аппаратную платформу новой электроники, если на сборочном конвейере произойдет сбой, поэтому контроль функциональности и тестирование сборки — обязательные этапы массового производства.

Читатели этой статьи познакомятся с основными методиками и задачами тестирования электронных устройств и получат общее понимание обеспечения качества на производстве. Особое внимание будет уделено достоинствам и недостаткам различных методов тестирования.

Мечта любого разработчика независимо от опыта и сферы деятельности — сделать проект для крупной компании, который выйдет в массовое производство. Даже если не получится разжиться с этого серьёзными дивидендами сразу, то впоследствии такой проект будет вашей визитной карточкой. Переход от макетного образца к изделию, выпускаемому серийными партиями очень сложный процесс, особенно для тех кто проходит его первый раз. Особенно для изделия, имеющего сложную электронную начинку. Вероятность успеха такого проекта сильно увеличивается в случае, если и проектировщик и инвестор хорошо осознают все шаги на предстоящем им пути.

Двигаясь от опытного образца к серийному изделию мы попадаем в область действия “нелинейной математики” с большим количеством факторов, которые необходимо учитывать чтобы правильно рассчитать объём вложений. Данный вывод кажется очевидным, но на практике я часто сталкиваюсь с любовью к недопустимым упрощениям в расчётах. В дальнейшем приводит к серьёзным финансовым проблемам, трениям в команде, зачастую финалом становится крах проекта.

Сегодня мы публикуем седьмую лекцию из курса «Анализ изображений и видео», прочитанного Натальей Васильевой в петербургском Computer Science Center, который создан по совместной инициативе Школы анализа данных Яндекса, JetBrains и CS-клуба.



Всего в программе девять лекций, из которых уже были опубликованы:

1. Введение в курс «Анализ изображений и видео»;
2. Основы пространственной и частотной обработки изображений;
3. Морфологическая обработка изображений;
4. Построение признаков и сравнение изображений: глобальные признаки;
5. Построение признаков и сравнение изображений: локальные признаки;
6. Поиск по подобию. Поиск нечетких дубликатов.

Под катом вы найдете план новой лекции и слайды.

По роду своей деятельности мне приходится осуществлять контроль различных параметров наземных импульсно-фазовых радионавигационных систем (ИФРНС) «Чайка» и Loran-C. В этой статье я хочу поделиться одним из методов обнаружения времени прихода импульса ИФРНС при наличии шумов. Метод применим во многих задачах поиска сигнала известной формы.

---

Official translation (with a bit of polishing) is available here.

---

Очередная вводная статья для начинающих программировать графику реального времени

У меня когда-то возникла задача (быстро) визуализировать молекулы. Например, молекула может быть представлена просто как набор сфер навроде вот этого:



Конкретно этот вирус состоит из примерно трёх миллионов атомов. Вы можете скачать его модель на замечательном сайте rcsb.org.

Это отличный топик для обучения шейдерам.

Это последняя, на сегодняшний день, статья из цикла про внутреннее устройство конкурентных ассоциативных контейнеров. В предыдущих статьях рассматривались hash map, был построен алгоритм lock-free ordered list и контейнеры на его основе. За бортом остался один важный тип структур данных — деревья. Пришло время немного рассказать и о них.

Исследования, посвященные алгоритмам конкурентных деревьев, не требующих внешней синхронизации доступа к ним, начались довольно давно — в 70-х годах прошлого века, — и были инициированы развитием СУБД, поэтому касались в основном оптимизации страничных деревьев (B-tree и его модификации).

Развитие lock-free подхода в начале 2000-х не прошло мимо алгоритмов деревьев, но лишь недавно, в 2010-х годах, появилось множество действительно интересных работ по конкурентным деревьям. Алгоритмы деревьев довольно сложны, поэтому исследователям потребовалось время — порядка 10 лет — на их lock-free/non-blocking адаптацию. В данной статье мы рассмотрим самый простой случай — обычное бинарное дерево, даже не самобалансирующееся.

Одна из базовых задач анализа данных — поиск взаимосвязи двух величин. Здесь я хочу показать пример поиска связи между ценой нефти и курсом рубля.



Во-первых надо определить, имеет ли вообще задача смысл. Почему нефть и рубль должны/могут быть взаимосвязаны? Вкратце, модель такая: экспортёры продают нефть за доллары, а затем продают доллары, чтобы получить рубли для расчётов внутри страны. Механизм крайне упрощён, надо учитывать объёмы добычи-продажи, что эскортируют не только нефть, не всегда экспортёры продают доллары, на курс валют влияет ЦБ интервенциями и т.д. И тем не менее, будем считать, что модель более-менее рабочая, то есть, что существуют фундаментальные причины для взаимосвязи цены нефти и курса рубля.

(пятница)

Обычно развернутое приложение в файловой системе выглядит как-то так:



Совершенно незащищенное от инструментов типа рефлектора или IlSpy, но что если оно станет таким:



По крайней мере легкий ступор хакеру-неофиту обеспечен. Приятно смотрится, и антивирусы не заинтересуются.

Привет, Хабр! Сегодня поговорим о BLE – технологии Bluetooth с низким энергопотреблением, которая нашла применение как в коммерческих, так и в сугубо любительских продуктах благодаря и низкой стоимости, и столь же низкому аппетиту к ресурсам аккумуляторов. Эти факторы делают BLE отличным выбором для связи смартфона или планшета под ОС Android с проектами на базе плат Intel для разработчиков – Edison или Galileo.



Задача предложенной ниже статьи – показать, как нужно писать код для соединения «железа» посредством протокола BLE на примере платформы Intel Edison и Android-устройства с Bluetooth версии 4.0. При этом используется исключительно бесплатное ПО и недорогие «железные» компоненты, уже готовые к работе.

Посмотрите на это фото.



Это совершенно обычная фотография, найденная в Гугле по запросу «железная дорога». И сама дорога тоже ничем особенным не отличается.

Что будет, если убрать это фото и попросить вас нарисовать железную дорогу по памяти?

Если вы ребенок лет семи, и никогда раньше не учились рисовать, то очень может быть, что у вас получится что-то такое:

На картинке изображен график роста траффика, который облачные адепты по всему миру продают в виде одного из сценариев, когда эластичное масштабирование имеет высокую ценность:



Это график посещений сайта Have I been pwned? (HIBP), который в один момент стал обслуживать со ~100 сессий в час до… 12000 сессий в час. Практически мгновенно.

Это случилось на неделе в сентябре, когда траффик буквально увеличился в 60 раз. 10 сентября – 2105 сессий, 11 сентября – 124036 сессий. Интересные вещи происходят, когда нагрузка увеличивается так резко, так быстро. Так что мне захотелось поделиться с вами несколькими вещами, которые я узнал – что было сделано мной хорошо и что следовало улучшить.

При первом знакомстве с Objective C он произвёл на меня впечатление уродливого и нелогичного языка. На тот момент я уже имел достаточно сильную базу в C/C++ и ассемблере x86, а так же был знаком с другими высокоуровневыми языками. В документации писалось, что Objective C это расширение языка C. Но, как бы я ни старался, мне всё же не удавалось применить свой опыт в разработке приложений для iOS.

Сегодня он всё так же кажется мне уродливым. Но однажды окунувшись в глубины Objective-C Runtime я влюбился в него. Изучение Objective-C Runtime позволило мне найти те тонкие ниточки, которые связывают Objective C с его «отцом» — великолепным и непревзойдённым языком C. Это тот самый случай, когда любовь превращает недостатки в достоинства.

Если вам интересно взглянуть на Objective C не просто как на набор операторов и базовых фреймворков, а понять его низкоуровневое устройство, прошу под кат.