Пользователь
Изучая криптографию, столкнулся с тем, что часто упоминаются конечные поля. Информации в сети достаточно, но есть много "но". Научные статьи слишком "заумны", в статьях попроще некоторые аспекты попросту не раскрыты. Что будет именно в этой статье: коротко рассмотрим теорию, поставлю под сомнение таблицу логарифмов, и из нового: посмотрим как быстро вычислять остаток от деления полиномов, ответим на вопрос: что такое порождающий полином и научимся генерировать их для конечных полей.
Если вы не знаете, что такое префикс-функция строки, не знаете, как она вычисляется, или, что самое главное, не до конца понимаете, почему алгоритм вычисления префикс-функции работает за линейное время, то эта статья для вас.
Я прошел через череду осознаний и озарений, прежде чем достичь просветления, и теперь предлагаю вам пройти этот путь вместе со мной.
На одном внутреннем мероприятии Илья Полянский рассказал о градиентах и цветовых моделях, а я записал и отредактировал его рассказ.
В работе над редизайном приложения Почты России мы пробовали разные способы подчеркнуть в визуальной коммуникации нашу уникальность. В том числе думали о градиентах. Под градиентами мы понимаем любые объекты, в которых один цвет переходит в другой. К ним можно отнести и тени. Оказалось, с градиентами связано много вопросов (вроде использования их в тёмной теме), и часть из них мы рассмотрели в этой статье.
Привет, Хабр! Меня зовут Евгений Сергеев, я работаю инженером-программистом в АСКОН, а в свободное время увлекаюсь астрофотографией. Именно ей будет посвящена статья. Я не буду затрагивать слишком много технических деталей, поскольку невозможно все охватить в рамках одного материала. Тем более, что на Хабре есть и другие статьи об астрофотографии. Я расскажу о своем опыте: как познакомился с этим увлекательным хобби и как можно начать самому без траты целого состояния.
Начну с громкого заявления: я придумал способ найти точку пересечения двух отрезков, заданных координатами концов. Придумал давно, лет 7 назад, в 2017 году, примерно, да, путь к этой публикации был долог, в основном из-за лени.
И да, я его придумал потому что не смог нагуглить, может он где-то и без меня описан был, может за эти 7 лет кто-то написал что-то похожее, а может я придумал какую-то фигню, которую умные люди изобретать не станут...
В этой статье я кратко изложу абстрактную идею того, что такое внутренняя размерность геометрической фигуры, попутно введя один из вариантов размерности Минковского, а затем расскажу про другой, приблизительный способ оценки внутренней размерности, который применим к реальным (то есть, конечным) облакам точек и называется Two Nearest Neighbours (TwoNN). В конце статьи для интересующихся будут оставлены ссылки на несколько научных статей, в которых второй способ используется для анализов эмбеддингов нейросетей.
Итак, давайте разбираться!
Как вы считаете, если выполнить java.util.Arrays.sort(), то какая сортировка будет вызвана? Quicksort? Timsort? И та, и другая, потому что для объектов вызывается Timsort, а для примитивов (чисел int, long, float и так далее) — Dual-Pivot Quicksort. В JDK 6 для объектов использовался стандартный Merge sort, а для чисел классическая реализация Quicksort с одним опорным элементом, предложенная Джоном Бентли и Дугласом МакИлрой. В JDK 7 оба алгоритма поменялись: теперь объекты сортируются с помощью Timsort, автор Тим Петерс, а для простых типов данных используется Dual-Pivot Quicksort, предложенный мною вместе с Джоном Бентли и Джошем Блоком в 2009 году. Эта сортировка используется более 15 лет не только в JDK, но и в Android (хотя и немного устаревшая версия).
А зачем нам вообще второй алгоритм сортировки, если есть Timsort? Почему не использовать один и для объектов, и для примитивов? Сегодня я, как автор, расскажу историю Dual-Pivot Quicksort: как он начинался, как развивался и как продолжает развиваться сейчас.
Видео показывает движение центра масс системы Земля–Луна вокруг Солнца и вращение Земли и Луны относительно него. Также наглядно показано явление прецессии лунной орбиты.
Представьте себе сложное переплетение складок, натяжение ткани, развевающейся на ветру. А теперь представьте, что вы пытаетесь воспроизвести всё это в виртуальной среде. На первый взгляд эта задача кажется обманчиво простой, но даже в ней есть свои подводные камни. В основе моделирования тканей лежит тонкий баланс между физической точностью и вычислительной эффективностью.
Моделирование ткани в основном сводится к решению задачи Коши, которая заключается в нахождении будущего состояния системы с учетом ее начальных условий и управляющих дифференциальных уравнений. В данном контексте положения и скорости частиц в ткани определяются такими силами, как гравитация, ветер и внутренние ограничения, которые и описываются диффурами. Хотя метод Эйлера часто является базовым подходом к решению подобных задач, он часто не подходит для моделирования ткани из-за своей неустойчивости и склонности к накоплению ошибок с течением времени, особенно в динамических системах с быстро меняющимися силами.
Метод Эйлера аппроксимирует будущее положение, основываясь только на текущем состоянии, что приводит к нереалистичному растяжению и артефактам в моделировании. Напротив, интеграция Верле, учитывающая как текущее, так и предыдущее положение частиц, отличается большей стабильностью и точностью, что делает ее более надежным методом решения задачи Коши в физике тканей.
На заре развития кикшеринга, как класса городских микромобильных устройств, ещё не было устоявшихся ограничений — просто в силу новизны. Довольно сложно регулировать что-то, не имея возможности наследовать уже устоявшиеся практики. Однако сегментация зоны проката на участки с различными правилами — штука весьма понятная и появилась сразу же, постепенно эволюционируя с растущими потребностями, вместе с тем обрастая проблемами с использованием. Одной из них была недостаточная скорость реакции в некоторых случаях.
Меня зовут Сергей Шилин, я руковожу разработкой электроники и встроенного ПО в Whoosh. В этой статье расскажу, почему не embedded-задача попала в embedded-отдел и как мы научили микроконтроллер считать H3-индексы и определять вхождение в любую функциональную зону за 0.1 секунды. Прошу под кат!
Ответ на вопрос о том, каким алгоритмом можно пользоваться для решения произвольных полиномиальных уравнений в практических целях, так, чтобы сходимость была гарантированной а время вычислений строго ограниченным.
Введение
Карл Давид Тольме Рунге (30 августа 1856 - 3 января 1927) - выдающийся немецкий математик, физик и спектроскопист. Обучался в Берлинском университете, где получил степень PhD, являлся профессором математики в Ганноверском университете, а также главой кафедры прикладной математики в Гёттингене. [1]
в 1901 году Карл открыл "Феномен Рунге" - в численном анализе эффект нежелательных колебаний, возникающий при интерполяции полиномами высоких степеней - о котором пойдёт речь в данной статье. [2]
Но прежде, чем мы окунёмся глубже в изучение данного феномена, давайте поговорим об интерполяционном многочлене Лагранжа, на примере которого мы и разберём Феномен Рунге.
Интерполяционный многочлен Лагранжа
Полином Лагранжа - это математическая функция, позволяющая записать полином n-степени, который будет соединять все заданные точки из набора значений, полученных опытным путём или методом случайной выборки. Многочлен в форме Лагранжа в явном виде содержит значения функций в узлах интерполяции, поэтому он удобен, когда значения функций меняются, а узлы интерполяции неизменны. Число арифметических операции, необходимых для построения многочлена Лагранжа, пропорционально и является наименьшим для всех форм записи. [3]
Полином Лагранжа в общем виде выглядит следующим образом:
Привет, Хабр! Это Саша Баулин из МТС Диджитал. Представьте, что вы решили построить дом своей мечты и активно погрузились в процесс: покупку земли, поиск строительной бригады, укладку фундамента и внутреннюю отделку. Через пару лет на строительство потрачены десятки миллионов рублей, дом почти готов. Но в самом конце оказывается, что черепица в бюджет не вписывается. И теперь дом придется разбирать.
Примерно в такой ситуации оказалось агентство NASA со своим проектом лунохода VIPER. Проект очень дорогой, для науки важный… мог бы быть. Подробности — под катом.
Привет, Хабр! Я Андрей Соколов, инженер-программист в группе разработки математических библиотек. Месяц назад моя коллега Валерия запустила цикл статей про матричные расширения, ускоряющие операции над матрицами. Вы уже смогли узнать, что они делают и какие существуют, какие из них разрабатываются для открытой архитектуры RISC-V.
В заключительной статье цикла разберем пример использования матричного расширения T-Head под RISC-V для реализации алгоритма матричного умножения. Сначала кратко рассмотрим наивную скалярную реализацию и блочный вариант алгоритма. Затем реализуем аналогичный вариант с использованием матричного расширения — как для квадратных матриц, так и матриц произвольного размера. Второй случай интересен тем, что возникает необходимость обработки так называемых «хвостов» — блоков неправильной конфигурации. В заключение немного расскажу, какие идеи можно использовать для дальнейшей оптимизации матричного умножения, и поделюсь полезными ссылками.
Статья не показывает пошаговую оптимизацию умножения матриц для достижения максимума FLOPS и не учит, как писать вычислительные ядра на ассемблере. Она демонстрирует использование матричного расширения и основные идеи оптимизации матричного умножения. Постарался описать все простыми словами, с иллюстрациями и небольшими вставками кода.
Звездное скопление Омега Центавра (Рис.1) с массой в 4 миллиона солнечных имеет радиус около 90 световых. 10 июля 2024 года в журнале Nature была опубликована сенсационная статья об открытии в этом скоплении черной дыры с массой в 8200 раз больше массы Солнца. Главными свидетелями существования этого невидимого объекта оказались быстрые звезды, которые без гравитационного поля массивной дыры должны были покинуть скопление очень быстро - в течение тысячи лет.