Итерационный бинарный критерий делимости: Деление без деления. Алгоритм для Big Integers и FPGA

Итерационный бинарный критерий делимости: Деление без деления. Алгоритм для Big Integers и FPGA. Деление — одна из самых ресурсоемких операций для Big Integers в криптографии и для аппаратных ускорителей (FPGA/ASIC). Что, если бы можно было проверять делимость, полностью исключив операцию деления и взятия остатка? Представляем новый детерминированный алгоритм, который заменяет дорогой N mod d на O(logN) итераций, состоящих исключительно из сложения (X+d) и побитового сдвига. Разбираем, как этот подход, обладающий линейно-логарифмической сложностью O(n⋅logN), обеспечивает радикальное снижение константного фактора и становится идеальным решением для многословной арифметики и низкоуровневой оптимизации железа. Экспертный уровень .

https://habr.com/ru/articles/975814/

#алгоритмы #теория_чисел #бинарный_алгоритм #big_integers #многословная_арифметика #оптимизация #fpga #аппаратная_реализация #криптография #деление_без_деления

Тёмная сторона Си: трюки, хаки, магия и алгоритмы

Доброго времени суток, господа и дамы! Иногда у некоторых людей возникает желание заняться откровенным непотребством в программировании — то, что не несет практической пользы напрямую, но помогает развлечься. И я — не исключение. В этой статье я хочу рассказать вам о лайфхаках, трюках (магических и не очень), алгоритмах на языке C! Идея написать эту статью зародилась из моего поста , после него я написал статью «Математика, биты, магия и немного ненормального программирования на C» и «Фокусы, хаки, магия и прочее ненормальное программирование на C» , которые раскрывали много интересных моментов. Увидев, что многим понравилась, я задумался: почему бы не изучить еще какие-нибудь трюки, заодно практикуясь в программировании на C? В этой статье будет еще больше всевозможных генераторов псевдослучайных чисел, гонок за скоростью и производительностью, алгоритмов, хаков и трюков! Всех, кто заинтересовался — прошу под кат.

https://habr.com/ru/companies/timeweb/articles/970910/

#C #трюки #хаки #фаны #алгоритмы #магия #математика #ГПСЧ #timeweb_статьи

Объяснение алгоритма деления двухразрядных чисел по материалам Дональда Кнута

Стоит задача разделить два числа, то есть найти частное от деления и остаток, используя встроенный в процессор алгоритм деления двухразрядного числа на одноразрядное, который дает лишь одноразрядное частное и остаток. Ограничимся делением двухразрядных чисел без знака. Деление чисел большей разрядности можно обобщить, при необходимости обратившись к первоисточнику [1]. Описываемый алгоритм назовем "программный 128/128". Заметим, что во многих 64-битных компиляторах он реализован (GCC, Clang, Intel Compiler) и может быть использован напрямую без изобретения велосипеда. Цель данной статьи - подробно объяснить детали алгоритма, чтобы снизить порог входа в энциклопедические труды Д. Кнута, в том числе объяснить почему деление в процессоре дает лишь одноразрядное частное (конкретно для 64-битных процессоров можно делить 128-битное число на 64-битное, получая лишь 64-битное частное). Назовем процессорный алгоритм деления как "аппаратный 128/64". Ключевым моментом в понимании алгоритма деления является процесс нормализации чисел, который позволяет воспользоваться встроенным в процессор делением 128/64. Алгоритм деления двухразрядных чисел в зависимости от разрядности делителя разделяется на два: половинчатое деление, когда делитель по факту одноразрядный, и полное деление, когда делитель двухразрядный. Назовем первый алгоритм как "половинчатый программный", а второй как "полный программный". Заметим, что "аппаратный 128/64" является половинчатым; он будет использован в обеих ветках программного алгоритма.

https://habr.com/ru/articles/974048/

#алгоритмы #деление_чисел

Как попасть в мир олимпиадного (спортивного) программирования? Спорт для ума, который меняет мышление

Олимпиадное программирование — это спорт для ума, который прокачивает алгоритмическое мышление, скорость и выдержку. Разбираем, с чего начать, какие навыки нужны, почему для соревнований чаще выбирают C++ и какие ресурсы помогут подготовиться школьникам, студентам и взрослым новичкам. Хочешь попробовать интеллектуальный спорт, где за пять часов нужно решить несколько задач и обойти соперников по скорости мышления? Спортивное программирование даёт не только адреналин соревнований, но и реальный буст к учёбе, поступлению и карьере — от первых олимпиад в школе до участия в ICPC и стажировок в IT-компаниях.

https://habr.com/ru/articles/972682/

#олимпиадное_программирование #спортивное_программирование #алгоритмы #c++ #python #icpc #программирование_для_начинающих #подготовка_к_олимпиадам #задачи_по_программированию #задачи_и_решения

Вероятностный анализ финансовых рынков на основе чистого OHLCV и многомодульной математической модели

Большинство торговых систем работают так: “если RSI пересёк X — покупай”. Но рынок — стохастическая система. Сигналы не бинарны, они вероятностны . Это приводит к фундаментальным проблемам классических индикаторных систем, из-за которых они чаще всего и не работают. Поэтому я решил создать рыночный анализатор, основанный на огромном количестве переменных - от простых индикаторов до анализа корреляций, волатильности, объёмов. Разберём логику этого анализатора и как именно он работает.

https://habr.com/ru/articles/972584/

#аналитика #алгоритмы #финансовая_аналитика #торговые_роботы #алгоритмические_системы #криптовалюты #системы_анализа_рынков

Продолжение статьи: Архитектура торгового Telegram-бота для сигналов пампов и дампов

В первой статье я показал, как сделал парсер пампов/дампов на BingX. Сейчас же проект вырос: из простого сборщика сигналов он превратился в полноценного торгового бота , который позволяет делать максимально гибкую настройку для каждой стратегии. Я решил использовать 12% и 5% сигналы как основные - от них и будет отталкиваться бот. Сейчас он находится в стадии тестирования (на демо-апи) и каждый может его протестировать! Разобрал основную структуру бота, функции, работу с базой данных и логику стратегий.

https://habr.com/ru/articles/972562/

#криптовалюта #боты #алгоритмическая_торговля #финансы #крипторынок #трейдинг #торговые_роботы #автоматизация #алгоритмы

Книга: «Разработка алгоритмов. Инженерный подход»

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

https://habr.com/ru/companies/piter/articles/970978/

#разработка_алгоритмов #алгоритмы

Фокусы, хаки, магия и прочее ненормальное программирование на C

Доброго времени суток, господа и дамы! Иногда у некоторых людей возникает желание заняться откровенным непотребством в программировании — то, что не несет практической пользы напрямую, но помогает развлечься. И я — не исключение. В этой статье я хочу рассказать вам о лайфхаках, трюках (магических и не очень), алгоритмах на языке C! Идея написать эту статью зародилась из моего поста , после него я написал статью «Математика, биты, магия и немного ненормального программирования на C» , которая раскрывала много интересных моментов. Увидев, что многим понравилась, я задумался: почему бы не изучить еще какие-нибудь трюки, заодно практикуясь в программировании на C? В этой статье мы погрузимся глубже и раскроем больше тем, такие как генераторы псевдослучайных чисел, трюки с побитовыми сдвигами и прочие быстрые алгоритмы на C! Всех, кто заинтересовался — прошу под кат.

https://habr.com/ru/companies/timeweb/articles/967678/

#c #трюки #хаки #фаны #алгоритмы #ГПСЧ #ненормальное_программирование #битовые_операции #математика #timeweb_статьи

Генерируем G-code прямо в браузере: как я написал карманную CAM-систему на JS+WebGL, чтобы не запускать тяжелый CAD

Зачем запускать тяжелый Fusion 360 или ArtCAM, чтобы просто вырезать фланец или прокладку? Я написал свой CAM-процессор на чистом JavaScript и Three.js, который готовит G-code из DXF за пару секунд прямо в браузере. В статье разбираем архитектуру легковесного инженерного софта: парсинг DXF, визуализацию траекторий на WebGL, алгоритмы оффсетов и опыт парного программирования с нейросетью. Заглянуть под капот

https://habr.com/ru/articles/970998/

#CAM #CNC #ЧПУ #Gcode #JavaScript #Threejs #WebGL #DXF #алгоритмы #инженерный_софт

Выйти из Матрицы: доказательство того, что реальность реальна

Что есть реальность? То, что мы можем увидеть? Но, одев очки виртуальной реальности, мы тоже видим множество вещей, что не есть реальностью. Фантазии на тему того, что окружающий нас мир является всего лишь симуляцией циркулируют в научной фантастике уже очень давно. Однако с выходом фильма «Матрица» поклонников данной гипотезы стало в разы больше. Конечно, нам бы сильно хотелось верить в то, что все ужасы окружающего мира, часто являющиеся творениями нас самих, являются не более чем симуляцией, из которой можно вырваться на свободу. Однако, такой эскапизм полностью противоречит законам природа, в частности физики. Ученые из Университета Британской Колумбии (Ванкувер, Канада) провели исследование, в котором сформировали доказательства того, что наша Вселенная вполне реальна. Как именно ученым это удалось, мы узнаем из их доклада.

https://habr.com/ru/companies/ua-hosting/articles/970022/

#Матрица #виртуальная_реальность #симуляция #реальность #теория_всего #сингулярность #черная_дыра #пространствовремя #алгоритмы #вселенная