Рубрика «математика» - 80

Всем привет!

Однажды меня спросили заказчики, нет ли у меня в проектах целочисленного БПФ, на что я всегда отвечал, что это уже сделано другими в виде готовых, хоть и кривых, но бесплатных IP-ядер (Altera / Xilinx) – берите и пользуйтесь. Однако, эти ядра не оптимальны, обладают набором «особенностей» и требуют дальнейшей доработки. В связи с чем, уйдя в очередной плановый отпуск, который не хотелось провести бездарно, я занялся реализацией конфигурируемого ядра целочисленного БПФ.

Реализация целочисленного БПФ на ПЛИС - 1
КДПВ (процесс отдладки ошибки переполнения данных)

В статье я хочу рассказать, какими способами и средствами реализуются математические операции при вычислении быстрого преобразования Фурье в целочисленном формате на современных кристаллах ПЛИС. Основу любого БПФ представляет узел, который носит название «бабочка». В бабочке реализуются математические действия – сложение, умножение и вычитание. Именно о реализации «бабочки» и её законченных узлов будет идти рассказ в первую очередь. За основу взяты современные семейства ПЛИС фирмы Xilinx – это серия Ultrascale и Ultrascale+, а также затрагиваются старшие серии 6- (Virtex) и 7- (Artix, Kintex, Virtex). Более старшие серии в современных проектах – не представляют интереса в 2018 году. Цель статьи – раскрыть трудности и особенности реализации кастомных ядер цифровой обработки сигналов на примере БПФ.
Читать полностью »

«Цель этого курса — подготовить вас к вашему техническому будущему.»

imageОсталось опубликовать 2 главы…

Моделирование — III

Я продолжу общее направление, заданное в предыдущей главе, но на этот раз я сконцентрируюсь на старом выражении «Мусор на входе – мусор на выходе», которое часто сокращают как GIGO (garbage in, garbage out). Идея в том, что если вы поместите неаккуратно собранные данные и неверно определенные выражения на вход, то на выходе вы можете получить только некорректные результаты. Так же неявно предполагается и обратное: из наличия точных входных данных следует и получение корректного результата. Я покажу, что оба эти предположения могут быть ложными.
Читать полностью »

Самое большое препятствие улучшения образования для детей (с компьютерами или без них) — это совершенно обедневшее воображение большинства взрослых.
— Алан Кей

image

Откопал статью Алана Кея 2009 года. Содержание — бомба и напалм, особенно на фоне большинства сегодняшних ИБД в области образования.

Вопрос: Вы часто говорите, что компьютерная революция еще не произошла. Что вы имеете в виду?

Ответ: Если вы сегодня посмотрите прищурившись на большинство персональных компьютеров, вы увидите, что мы в основном просто автоматизируем бумагу — используем цифровые версии документов и почты. Но, как и в случае с изобретением печатного станка, в компьютере интересно то, что он позволяет вам использовать новые способы представления вещей, новые способы споров о разных вещах и новые способы понимания информации в момент ее восприятия.

Большинство школ определяют компьютерную грамотность как умение использовать Microsoft Office и, возможно, немного заниматься веб-дизайном. Они упускают суть. Это все равно что сказать: «Если вы знаете, за какой конец книги нужно держаться, и вы знаете, как перейти к третьей главе, тогда вы грамотны».

Литература — это прежде всего наличие достаточно важных идей для обсуждения и записи в той или иной форме. Поэтому вы должны задать себе вопрос: «Какая литература лучше всего подходит для записи на компьютере?» Один из ответов — создание динамического моделирования некоторой идеи, которая, по вашему мнению, важна, симуляции, с которой вы можете играть, и на основе которой вы можете учиться.
Читать полностью »

Продолжаю знакомить читателей Хабра с главами из своей книжки «Теория счастья» с подзаголовком «Математические основы законов подлости». Это ещё не изданная научно-популярная книжка, очень неформально рассказывающая о том, как математика позволяет с новой степенью осознанности взглянуть на мир и жизнь людей. Она для тех кому интересна наука и для тех, кому интересна жизнь. А поскольку жизнь наша сложна и, по большому счёту, непредсказуема, упор в книжке делается, в основном, на теорию вероятностей и математическую статистику. Здесь не доказываются теоремы и не даются основы науки, это ни в коем случае не учебник, а то, что называется recreational science. Но именно такой почти игровой подход позволяет развить интуицию, скрасить яркими примерами лекции для студентов и, наконец, объяснить нематематикам и нашим детям, что же такого интересного мы нашли в своей сухой науке.

Опубликованные главы:
 •  Введение в мерфологию
 •  Закон арбузной корки и нормальность ненормальности

Теория счастья. Закон зебры и чужой очереди - 1

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

Читать полностью »

Светлой памяти моего учителя — первого декана физико-математического факультета Новочеркасского политехнического института, заведующего кафедрой «Теоретическая механика» Кабелькова Александра Николаевича

Введение

Август, лето подходит к концу. Народ яростно рванул на моря, да оно и неудивительно — самый сезон. А на хабре, тем временем, буйным цветом распускается и пахнет лженаука. Если говорить о теме данного выпуска «Моделирования...», то в нем мы совместим приятное с полезным — продолжим обещанный цикл и совсем чуть-чуть поборемся с этой самой лженаукой за пытливые умы современной молодежи.

Моделирование динамических систем: Как движется Луна? - 1

А вопрос ведь действительной не праздный — со школьных лет мы привыкли считать, что наш ближайший спутник в космическом пространстве — Луна движется вокруг Земли с периодом 29,5 суток, особенно не вдаваясь в сопутствующие подробности. На самом же деле наша соседка своеобразный и в какой-то степени уникальный астрономический объект, с движением которого вокруг Земли не всё так просто, как, возможно хотелось бы некоторым моим коллегам из ближайшего зарубежья.

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

Читать полностью »

«Совпадение» — случай, который нам кажется очень маловероятным, но все же случается.

Вы встречали в жизни «совпадения»? На парковке три красных автомобиля стоят рядом, ваш знакомый надел на встречу точно такую же футболку, номер с красивым видом оказался единственным свободным, а компьютер выключился в тот момент, когда надо было открывать дверь гостям. Мы встречаем ситуации, которые сами по себе очень маловероятны. И действительно, давайте посмотрим, с какой вероятностью у моего дома остановится два Nissan Skyline? Даже если всего автомобилей 10000, и среди них только два Nissan Skyline, то вероятность ничтожная:
$$display$$frac{2!}{10000^2}$$display$$
Каждый раз мы удивляемся таким «совпадениям», но так ли это маловероятно? Разберемся.

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

Допустим, есть две параллельные вселенные. В каждой из них вы сидите дома и собираетесь идти в кафе:
Читать полностью »

18-летний Ювин Тан доказал, что классические компьютеры могут решать «задачу рекомендаций» почти так же быстро, как квантовые. Этот результат аннулирует один из наилучших примеров квантового ускорения расчётов.

Серьёзному успеху в квантовых вычислениях помешал подросток - 1

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

В наиболее практичном виде проблема рекомендаций связана с тем, как сервисы вроде Amazon и Netflix определяют, какие продукты могут вам понравиться. Специалисты по информатике считали её одним из наилучших примеров задач, решать которые на квантовых компьютерах будет экспоненциально быстрее – что подчёркивало потенциальные возможности этих футуристических машин. И вот теперь Тан опроверг это мнение.
Читать полностью »

image

Привет! В прошлой статье «бесконечный узор на основе простых чисел» я рассказал про алгоритм, который позволяет генерировать бесконечные красивые узоры, похожие то ли на инопланетные рисунки, то ли на нечто технологическое, подобно устройству микросхем. Однако, алгоритм для генерирования 2D узоров можно так же использовать и для создания мелодий. Подробнее под катом.
Читать полностью »

Работа с числовыми матрицами в целом и решение систем линейных алгебраических уравнений в частности — классическая математическая и алгоритмическая задача, широко используемая при моделировании и расчёте огромного класса бизнес-процессов (например, при расчёте себестоимости). При создании и эксплуатации конфигураций «1С:Предприятия» многие разработчики сталкивались с необходимостью вручную реализовывать алгоритмы расчёта СЛАУ, а после — с проблемой длительного ожидания решения.
«1С:Предприятие» 8.3.14 будет содержать функционал, позволяющий значительно сократить время решения систем линейных уравнений за счёт использования алгоритма, основанного на теории графов.
Он оптимизирован для использования на данных, имеющих разреженную структуру (то есть содержащие не более 10% ненулевых коэффициентов в уравнениях) и в среднем и в лучшем случаях демонстрирует асимптотику Θ(n⋅log(n)⋅log(n)), где n — количество переменных, а в худшем (при заполненности системы ~100%) его асимптотика сопоставима с классическими алгоритмами ( Θ(n3)). При этом на системах, имеющих ~105 неизвестных, алгоритм показывает ускорение в сотни раз по сравнению с реализованными в специализированных библиотеках линейной алгебры (например, superlu или lapack).
Важно: статья и описанный алгоритм требуют понимания линейной алгебры и теории графов на уровне первого курса университета.
Читать полностью »


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