Изучая криптографию, столкнулся с тем, что часто упоминаются конечные поля. Информации в сети достаточно, но есть много "но". Научные статьи слишком "заумны", в статьях попроще некоторые аспекты попросту не раскрыты. Что будет именно в этой статье: коротко рассмотрим теорию, поставлю под сомнение таблицу логарифмов, и из нового: посмотрим как быстро вычислять остаток от деления полиномов, ответим на вопрос: что такое порождающий полином и научимся генерировать их для конечных полей.
User
Доктора Кнут, Моррис и Пратт, или Как я перестал бояться и полюбил префикс-функцию
Если вы не знаете, что такое префикс-функция строки, не знаете, как она вычисляется, или, что самое главное, не до конца понимаете, почему алгоритм вычисления префикс-функции работает за линейное время, то эта статья для вас.
Я прошел через череду осознаний и озарений, прежде чем достичь просветления, и теперь предлагаю вам пройти этот путь вместе со мной.
Как делать чистые градиенты
На одном внутреннем мероприятии Илья Полянский рассказал о градиентах и цветовых моделях, а я записал и отредактировал его рассказ.
В работе над редизайном приложения Почты России мы пробовали разные способы подчеркнуть в визуальной коммуникации нашу уникальность. В том числе думали о градиентах. Под градиентами мы понимаем любые объекты, в которых один цвет переходит в другой. К ним можно отнести и тени. Оказалось, с градиентами связано много вопросов (вроде использования их в тёмной теме), и часть из них мы рассмотрели в этой статье.
Астрофотография: от советского объектива до автоматизированного управления телескопом
Привет, Хабр! Меня зовут Евгений Сергеев, я работаю инженером-программистом в АСКОН, а в свободное время увлекаюсь астрофотографией. Именно ей будет посвящена статья. Я не буду затрагивать слишком много технических деталей, поскольку невозможно все охватить в рамках одного материала. Тем более, что на Хабре есть и другие статьи об астрофотографии. Я расскажу о своем опыте: как познакомился с этим увлекательным хобби и как можно начать самому без траты целого состояния.
Изобретаю свой сложный способ поиска координат точки пересечения двух линий
Начну с громкого заявления: я придумал способ найти точку пересечения двух отрезков, заданных координатами концов. Придумал давно, лет 7 назад, в 2017 году, примерно, да, путь к этой публикации был долог, в основном из-за лени.
И да, я его придумал потому что не смог нагуглить, может он где-то и без меня описан был, может за эти 7 лет кто-то написал что-то похожее, а может я придумал какую-то фигню, которую умные люди изобретать не станут...
Размерность Минковского и Two Nearest Neighbours (TwoNN)
В этой статье я кратко изложу абстрактную идею того, что такое внутренняя размерность геометрической фигуры, попутно введя один из вариантов размерности Минковского, а затем расскажу про другой, приблизительный способ оценки внутренней размерности, который применим к реальным (то есть, конечным) облакам точек и называется Two Nearest Neighbours (TwoNN). В конце статьи для интересующихся будут оставлены ссылки на несколько научных статей, в которых второй способ используется для анализов эмбеддингов нейросетей.
Итак, давайте разбираться!
Удивительная история развития сортировки в JDK
Как вы считаете, если выполнить 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: как он начинался, как развивался и как продолжает развиваться сейчас.
Поделить нельзя — умножить или алгоритм быстрого деления по методу Ньютона-Рафсона
Все мы в школе проходили деление «столбиком» — простой алгоритм, который несложно реализовать, вот только не очень быстрый. В прошлый раз мы рассматривали, как компилятор оптимизирует деление в случаях, когда делитель известен во время компиляции, но применение его напрямую, чтоб оптимизировать деление для делителей, определямых в run-time, невозможно: вычисление констант сдвига и умножения само по себе требует деления.
В этот раз хочется поговорить о другом методе, сводящем деление к умножениям и битовым сдвигам, основанном на методе поиска корней функции.
Особенности движения Земли и Луны
Видео показывает движение центра масс системы Земля–Луна вокруг Солнца и вращение Земли и Луны относительно него. Также наглядно показано явление прецессии лунной орбиты.
Симуляция ткани методом Стёрмера — Верле
Представьте себе сложное переплетение складок, натяжение ткани, развевающейся на ветру. А теперь представьте, что вы пытаетесь воспроизвести всё это в виртуальной среде. На первый взгляд эта задача кажется обманчиво простой, но даже в ней есть свои подводные камни. В основе моделирования тканей лежит тонкий баланс между физической точностью и вычислительной эффективностью.
Моделирование ткани в основном сводится к решению задачи Коши, которая заключается в нахождении будущего состояния системы с учетом ее начальных условий и управляющих дифференциальных уравнений. В данном контексте положения и скорости частиц в ткани определяются такими силами, как гравитация, ветер и внутренние ограничения, которые и описываются диффурами. Хотя метод Эйлера часто является базовым подходом к решению подобных задач, он часто не подходит для моделирования ткани из-за своей неустойчивости и склонности к накоплению ошибок с течением времени, особенно в динамических системах с быстро меняющимися силами.
Метод Эйлера аппроксимирует будущее положение, основываясь только на текущем состоянии, что приводит к нереалистичному растяжению и артефактам в моделировании. Напротив, интеграция Верле, учитывающая как текущее, так и предыдущее положение частиц, отличается большей стабильностью и точностью, что делает ее более надежным методом решения задачи Коши в физике тканей.
Практическое применение эффекта полного внутреннего отражения с потерями
Задумывались ли вы о том, что вокруг нас, в технике широко применяется интересное физическое явление, на базе которого вы и сами сможете собрать множество интересных самоделок?
И именно об этом и будет наш рассказ…
Венера или первые 60 kpx с другой планеты
В этом топике я хочу восстановить историческую справедливость и рассказать о том, как советским инженерам удалось создать устройство, которое успешно осуществило панорамную съемку в условиях крайне агрессивной среды при температуре более 470°С и давлении в 93 атм.
IoT Geofencing: как мы сократили время определения функциональных зон, используя H3-индексы
На заре развития кикшеринга, как класса городских микромобильных устройств, ещё не было устоявшихся ограничений — просто в силу новизны. Довольно сложно регулировать что-то, не имея возможности наследовать уже устоявшиеся практики. Однако сегментация зоны проката на участки с различными правилами — штука весьма понятная и появилась сразу же, постепенно эволюционируя с растущими потребностями, вместе с тем обрастая проблемами с использованием. Одной из них была недостаточная скорость реакции в некоторых случаях.
Меня зовут Сергей Шилин, я руковожу разработкой электроники и встроенного ПО в Whoosh. В этой статье расскажу, почему не embedded-задача попала в embedded-отдел и как мы научили микроконтроллер считать H3-индексы и определять вхождение в любую функциональную зону за 0.1 секунды. Прошу под кат!
Надежный алгоритм поиска корней полиномиальных уравнений
Ответ на вопрос о том, каким алгоритмом можно пользоваться для решения произвольных полиномиальных уравнений в практических целях, так, чтобы сходимость была гарантированной а время вычислений строго ограниченным.
Феномен Рунге
Введение
Карл Давид Тольме Рунге (30 августа 1856 - 3 января 1927) - выдающийся немецкий математик, физик и спектроскопист. Обучался в Берлинском университете, где получил степень PhD, являлся профессором математики в Ганноверском университете, а также главой кафедры прикладной математики в Гёттингене. [1]
в 1901 году Карл открыл "Феномен Рунге" - в численном анализе эффект нежелательных колебаний, возникающий при интерполяции полиномами высоких степеней - о котором пойдёт речь в данной статье. [2]
Но прежде, чем мы окунёмся глубже в изучение данного феномена, давайте поговорим об интерполяционном многочлене Лагранжа, на примере которого мы и разберём Феномен Рунге.
Интерполяционный многочлен Лагранжа
Полином Лагранжа - это математическая функция, позволяющая записать полином n-степени, который будет соединять все заданные точки из набора значений, полученных опытным путём или методом случайной выборки. Многочлен в форме Лагранжа в явном виде содержит значения функций в узлах интерполяции, поэтому он удобен, когда значения функций меняются, а узлы интерполяции неизменны. Число арифметических операции, необходимых для построения многочлена Лагранжа, пропорционально и является наименьшим для всех форм записи. [3]
Полином Лагранжа в общем виде выглядит следующим образом:
Отмена миссии VIPER. NASA придется разобрать луноход ценой в 0,45 млрд $
Привет, Хабр! Это Саша Баулин из МТС Диджитал. Представьте, что вы решили построить дом своей мечты и активно погрузились в процесс: покупку земли, поиск строительной бригады, укладку фундамента и внутреннюю отделку. Через пару лет на строительство потрачены десятки миллионов рублей, дом почти готов. Но в самом конце оказывается, что черепица в бюджет не вписывается. И теперь дом придется разбирать.
Примерно в такой ситуации оказалось агентство NASA со своим проектом лунохода VIPER. Проект очень дорогой, для науки важный… мог бы быть. Подробности — под катом.
Простая красота XOR-сжатия чисел с плавающей запятой
Недавно я реализовал небольшую программу для визуализации внутренней работы схемы, сжимающей временные последовательности чисел с плавающей запятой при помощи выполнения XOR последующих значений. Визуализации получились красивыми и помогли мне понять этот красивый алгоритм гораздо проще, чем все объяснения, которые я встречал ранее.
Алгоритм
Алгоритм* прост. Сначала мы записываем первое число с плавающей запятой полностью; для всех последующих чисел выполняется XOR с предыдущим числом, а затем результат кодируется одним из трёх способов.
[*Конкретно эта версия сжатия чисел с плавающей запятой при помощи XOR была впервые описана в «Gorilla: A Fast, Scalable, In-Memory Time Series Database» и часто называется «Gorilla-сжатием».]
Математика матричных расширений: как происходит умножение матриц на примере T-Head Matrix Extension
Привет, Хабр! Я Андрей Соколов, инженер-программист в группе разработки математических библиотек. Месяц назад моя коллега Валерия запустила цикл статей про матричные расширения, ускоряющие операции над матрицами. Вы уже смогли узнать, что они делают и какие существуют, какие из них разрабатываются для открытой архитектуры RISC-V.
В заключительной статье цикла разберем пример использования матричного расширения T-Head под RISC-V для реализации алгоритма матричного умножения. Сначала кратко рассмотрим наивную скалярную реализацию и блочный вариант алгоритма. Затем реализуем аналогичный вариант с использованием матричного расширения — как для квадратных матриц, так и матриц произвольного размера. Второй случай интересен тем, что возникает необходимость обработки так называемых «хвостов» — блоков неправильной конфигурации. В заключение немного расскажу, какие идеи можно использовать для дальнейшей оптимизации матричного умножения, и поделюсь полезными ссылками.
Статья не показывает пошаговую оптимизацию умножения матриц для достижения максимума FLOPS и не учит, как писать вычислительные ядра на ассемблере. Она демонстрирует использование матричного расширения и основные идеи оптимизации матричного умножения. Постарался описать все простыми словами, с иллюстрациями и небольшими вставками кода.
Звездные битвы: Талли-Фишер против Кеплера
Звездное скопление Омега Центавра (Рис.1) с массой в 4 миллиона солнечных имеет радиус около 90 световых. 10 июля 2024 года в журнале Nature была опубликована сенсационная статья об открытии в этом скоплении черной дыры с массой в 8200 раз больше массы Солнца. Главными свидетелями существования этого невидимого объекта оказались быстрые звезды, которые без гравитационного поля массивной дыры должны были покинуть скопление очень быстро - в течение тысячи лет.
Красное смещение: доплер-эффект или гравитация?
Тема обсуждения
В недавно опубликованном здесь материале о космологической модели Неустойчивой решётки (НР), то есть модели Вселенной без Большого взрыва (БВ), не обсуждались такие доводы в пользу БВ, как космологическое красное смещение, наличие космологического горизонта и реликтового микроволнового излучения, которых в квазистационарной Вселенной быть, казалось бы, не должно. «Старение фотонов», объясняющее красное смещение света и наблюдаемое в некоторых случаях аномальное торможение тел передачей кинетической энергии от тел и фотонов флуктуациям вакуума, подвергается сомнениям после моделирования обстоятельств торможения аппаратов «Пионер», доказывающего тепловую природу торможения [1]. Наконец, и старение фотонов, и гравитационная гипотеза «покраснения» выглядят не совместимыми с динамикой эволюции сверхновых, которая коррелирует с их красным смещением, а в рамках этих двух гипотез, вроде, не должна бы.
Первый довод можно попытаться оспорить, заявив, что бесконечно протяжённая Вселенная не обязана быть стационарной, поскольку не придумано пока ещё запретов на её расширение (с соответствующим красным смещением) по каким‑нибудь причинам. Другое дело, что неизвестная причина расширения — это на данный момент «излишняя сущность», а «бритва Оккама» настойчиво рекомендует таковых избегать при «измышлении гипотез». Удастся ли вписать красное смещение и т. п. в модель НР, не прибегая, по возможности, к новым сущностям?
Рассмотрим гравитационную гипотезу более внимательно.
Information
- Rating
- Does not participate
- Date of birth
- Registered
- Activity