Pull to refresh
108
0
Михаил Борисов @MichaelBorisov

User

Send message

Приближение многочленом с условием прохождения через точки

Reading time 6 min
Views 8.9K

При моделировании данных методом наименьших квадратов, кривая обычно не проходит через точки измерений (рис. 1).

Что, если нужно, чтобы эта кривая точно проходила через одну или несколько особо выделенных точек (рис. 2)?

Тогда читаем дальше
Total votes 21: ↑18 and ↓3 +15
Comments 30

«Большие батальоны» в непрерывном времени (симуляция сражений)

Reading time 7 min
Views 16K
«Бог всегда на стороне больших батальонов» — Жак д'Эстамп дела Ферте, французский маршал

Рис. 1

Во многих компьютерных играх необходимо симулировать сражения без отображения их хода на экране. Например, это может быть Rogue-like пошаговая игра, в которой компьютер должен посчитать только исход сражения (кто победил) и потери сторон. Даже в интерактивных играх сражения, которые происходят за пределами поля видимости игрока, можно моделировать упрощенно. Я разработал интересную математическую модель для такого моделирования и представляю ее читателям.

В статье рассматривается «непрерывный» подход — то есть силы сторон являются непрерывными величинами, а их взаимодействие происходит в непрерывном времени. Это позволяет воспользоваться методами мат. анализа и получить решение в явном виде. Для армий, состоящих из большого количества боевых единиц, такое упрощение не вносит большой погрешности. Вместе с тем, решение в явном виде позволяет понять многое о задаче.
Читать дальше →
Total votes 22: ↑19 and ↓3 +16
Comments 59

Компактная реализация RSA для встраиваемых применений

Reading time 15 min
Views 59K
RSA является широкоизвестным алгоритмом шифрования с открытым ключом. На его основе, кроме асимметричного шифрования, можно также реализовать электронную подпись (ЭЦП). Эти возможности привлекательны для встраиваемых систем, микроконтроллеров. Сам метод шифрования с виду чрезвычайно прост:
C = (Me) mod n (1)
где C,M,e,n — целые числа, M — открытый текст, числа e и n представляют собой открытый ключ, C — шифротекст. mod — остаток от деления.

Расширование выглядит столь же просто:
M = (Cd) mod n (2)
где C,M,n играют ту же роль, что и при шифровании, d — закрытый ключ.

При этом n=p*q, где p и q — простые числа (секретные), e обычно равно 65537, d вычисляется на основе e, p и q. Криптостойкость основана на том, что для достаточно больших p и q задача разложения n на множители или обращения формулы шифрования без знания p и q не решается за приемлемое время.

Но эта кажущаяся простота обманчива. За ней скрывается огромное количество деталей и сложностей реализации. Особенно если стоит цель получить эффективную по быстродействию и памяти реализацию, пригодную для применения в микроконтроллерах. Я не нашел в интернете подходящих библиотек, а попытки изучения исходников libgcrypt заводят в такие дебри, из которых не выберешься. Поэтому я написал свою компактную библиотеку, которой и делюсь с уважаемыми читателями.
Читать дальше →
Total votes 33: ↑31 and ↓2 +29
Comments 29

Вытесняющая многозадачность на ассемблере Z80

Reading time 8 min
Views 29K
Медленный процессор и маленький объем ОЗУ — это еще не значит, что на такой платформе нельзя реализовать вытесняющую многозадачность. Более того, главный смысл организации многозадачной среды — это эффективное использование процессорного времени, чтобы процессор не простаивал, пока одни программы ждут какого-либо события, а использовался другими программами. Даже на таких платформах, как ZX Spectrum (Z80 3.5МГц, 48-128кБ ОЗУ), или 8-битные микроконтроллеры AVR, организация вытесняющей многозадачности имеет большой смысл.

Предлагаю вашему вниманию собственную реализацию многозадачного диспетчера на ассемблере Z80 (ZX Spectrum), который не является частью какой-либо ОС, а может использоваться отдельно. В нем нет ничего лишнего — только организация исполнения потоков и синхронизации между ними. Диспетчер можно использовать как составную часть программного проекта, как основу для создания более серьезного диспетчера для ОС, или как обучающий материал.
Читать дальше →
Total votes 66: ↑64 and ↓2 +62
Comments 32

Музыкальная шкатулка на PIC16F753

Reading time 8 min
Views 26K


Меня в свое время очень впечатлил этот пост о создании светомузыкального устройства на микроконтроллере в подарок любимой. И однажды пришло мое время сделать такой подарок. Учитывая отличия от автора упомянутого проекта в навыках и инструментарии; будучи сильно ограничен во времени подготовки (3-4 дня), я пошел другим путем и разработал свое музыкальное устройство для установки в купленную в сувенирном магазине шкатулку. Оно отличается более простой схемой и легкостью изготовления. В статье описываются подробности моего проекта и их мотивация. Осторожно, фотографии (всего около 1Мб).
Читать дальше →
Total votes 37: ↑26 and ↓11 +15
Comments 28

Организация памяти в текстовом редакторе

Reading time 6 min
Views 35K
Каждый, кто пытался запрограммировать хотя бы простейший редактор текста на низком уровне, сталкивался с задачей организации памяти для хранения редактируемого текста. Структура данных для хранения текста должна удовлетворять следующим требованиям:
  1. иметь малые накладные расходы по памяти. Большая часть доступной памяти должна использоваться для хранения текста, а не служебной информации;
  2. допускать эффективную вставку и удаление в произвольном месте текста.

Удовлетворить эти требования одновременно непросто. Если рассмотреть широкоизвестные структуры данных, такие как массивы, списки, деревья, стеки, очереди, кольцевые буфера — то такой структуры, которая бы позволила эффективно выполнить оба требования, не встречается. В случае массива имеем незначительные накладные расходы по памяти, но операция вставки имеет сложность O(n), где n — размер редактируемого текста. В случае списка сложность вставки и удаления составляет O(1), однако накладные расходы по памяти в несколько раз превышают размер собственно текста. Деревья, кучи, кольцевые буфера, ассоциативные массивы и прочие структуры и вовсе неприменимы для хранения текста в редакторе.

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

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

Несмотря на то, что эта структура данных была открыта давно и использовалась в текстовых редакторах на старых ЭВМ в 8-битную эпоху, это тайное знание предков было в значительной мере утеряно и в современных редакторах встречается редко. Попробуйте открыть файл, состоящий из одной строки мегабайт на 10, в Notepad или Far. Вставка и удаление символов будет длиться секундами.
Читать дальше →
Total votes 126: ↑119 and ↓7 +112
Comments 57

Автоматическая генерация операторов сравнения структур в C++

Reading time 7 min
Views 9.4K
Язык C++ для всех пользовательских классов и структур генерирует по умолчанию копирующий конструктор и копирующий оператор присваивания. Тем самым для важного ряда случаев программист освобождается от написания указанных функций вручную. Например, операторы по умолчанию хорошо работают для структур, которые содержат данные. При этом данные могут храниться как в простых типах, так и в сложных контейнерах, таких как std::vector или std::string.

В свете этого удобно было бы иметь и операторы сравнения структур == и != по умолчанию, однако компилятор C++, в соответствии со стандартом, не генерирует их.
Читать дальше →
Total votes 30: ↑28 and ↓2 +26
Comments 43

Information

Rating
Does not participate
Registered
Activity