• Как обновление Rust 1.26 ускорило мой код в три с лишним раза

    • Перевод
    Хочу поделиться небольшой историей о мощи LLVM и преимуществах языков высокого уровня над ассемблером.

    Я работаю в компании Parity Technologies, которая поддерживает клиент Parity Ethereum. В этом клиенте нам нужна быстрая 256-битная арифметика, которую приходится эмулировать на программном уровне, потому что никакое оборудование не поддерживает её аппаратно.

    Долгое время мы параллельно делаем две реализации арифметики: одну на Rust для стабильных сборок и одну со встроенным ассемблерным кодом (который автоматически используется nightly-версией компилятора). Мы так поступаем, потому что храним 256-битные числа как массивы 64-битных чисел, а в Rust нет никакого способа умножить два 64-битных числа, чтобы получить результат более 64 бит (так как целочисленные типы Rust только доходят до u64). Это несмотря на то, что x86_64 (наша основная целевая платформа) нативно поддерживает 128-битные результаты вычислений с 64-битными числами. Так что мы разделяем каждое 64-битное число на два 32-битных (потому что можно умножить два 32-битных числа и получить 64-битный результат).
    Читать дальше →
  • Хроматическое число плоскости не меньше 5

      Задача о хроматическом числе плоскости формулируется следующим образом: в какое наименьшее число цветов можно раскрасить плоскость так, чтобы любые две точки на расстоянии 1 были покрашены в различные цвета?

      Эту задачу сформулировали Хуго Хадвигер и Пал Эрдёш в сороковых годах XX века. Независимо от них примерно в то же самое время этой задачей занимались Эдуард Нелсон и Дж. Р. Исбелл. После работы Хадвигера 1961 года об открытых на тот момент проблемах, хроматическое число плоскости стало активно изучаться.

      Сразу же было показано, что в 3 цвета плоскость требуемым образом раскрасить нельзя, однако 7 цветов достаточно. Действительно, легко выбрать на плоскости несколько точек так, что некоторые из них находятся на расстоянии ровно 1 (такая конструкция точек называется графом единичных расстояний), и затем перебором показать, что в 3 цвета эти точки раскрасить невозможно. Примеры таких графов — веретено Мозера и граф Голомба приведены на картинке ниже. Чтобы показать, что 7 цветов достаточно, замостим плоскость правильными шестиугольниками со стороной 0.4 и закрасим их по определённому паттерну, как на картинке ниже. Тогда, как несложно убедиться, концы любого отрезка длины 1 будут лежать в разных шестиугольниках различных цветов.



      Однако, с тех пор никто не мог уточнить ни верхнюю, ни нижнюю границы. Задача получила название Проблема Нелсона — Эрдёша — Хадвигера. Прошло 60 лет, и вот, в апреле 2018 года математик-любитель Обри де Грей предъявил граф единичных расстояний, который нельзя покрасить в 4 цвета.
      Читать дальше →
      • +30
      • 7,1k
      • 7
    • Инверсная кинематика в двухмерном пространстве

      • Перевод

      Часть 1. Математика



      Введение


      Мы так привыкли к взаимодействию с окружающим нас миром, что не задумываемся о том, насколько сложно двигаются наши руки и ноги. В академической литературе задача управления манипулятором робота называется инверсной кинематикой. Кинематика обозначает "движения", а понятие "инверсная" связано с тем, что обычно мы не управляем самой рукой. Мы управляем «двигателями», поворачивающими каждую отдельную часть. Инверсная кинематика — это задача определения того, как перемещать эти двигатели, чтобы сдвинуть руку в конкретную точку. И в своём общем виде эта задача чрезвычайно сложна. Чтобы вы понимали, насколько она сложна, то можете вспомнить о таких играх, как QWOP, GIRP или даже Lunar Lander, в которой вы выбираете не куда двигаться, а какие мускулы (или ускорители) приводить в действие.

      Задача управления подвижными приводами распостраняется даже на область робототехники. Вас не должно удивлять то, что на протяжении веков математики и инженеры смогли разработать множество решений. В большинстве 3D-редакторов и игровых движков (в том числе и в Unity) есть наборы инструментов, позволяющих выполнять риггинг человекоподобных и звероподобных существ. Для различных схем (манипуляторов роботов, хвостов, щупалец, крыльев и т.д.) встроенных решений обычно не существует.
      Читать дальше →
      • +36
      • 5,9k
      • 3
    • Математическое моделирование хабро-будущего

      image

      Неделю назад на Хабре появился очередной пост, что Хабр уже не тот. Безотносительно к затрагиваемым в нем темам заинтересовал вопрос о системе рейтинга и кармы — некоторые видят деградацию или сползание ресурса «не туда» именно в ней.

      Ни в коей мере не критикуя нынешнюю систему и не влазя во внутренние дела администрации захотелось исследовать этот вопрос с теоретической стороны — нахождение оптимальной системы градации пользователей с помощью элементарных математических методов.
      Читать дальше →
      • –10
      • 1,3k
      • 1
    • Пронумеровать все действительные числа на отрезке [0,1]

        В качестве доказательства несчетности действительных чисел во всех учебниках по теории множеств приводится так называемый диагональный метод Кантора (подробнее можно ознакомиться в книге «Что такое математика?», авторы Курант, Роббинс, §4. Математический анализ бесконечного. 2. Счетность множества рациональных чисел и несчетность
        континуума.). Данный метод доказывает несчетность подмножества действительных чисел, принадлежащих диапазону [0,1]. Однако, если присмотреться к доказательству, становится ясно, что оно не учитывает экспоненциальный рост возможных вариантов с каждым увеличиеним порядкового номера в десятичной дроби.
        Читать дальше →
      • Теория вычислений. Введение в конечные автоматы

        Спойлер
        Cкажу cразу, что не буду объяснять слишком формально.

        Конечные автоматы (finite-state machine)


        Это до предела упрощенная модель компьютера имеющая конечное число состояний, которая жертвует всеми особенностями компьютеров такие как ОЗУ, постоянная память, устройства ввода-вывода и процессорными ядрами в обмен на простоту понимания, удобство рас­суждения и легкость программной или аппаратной реализации.

        С помощью КА можно реализовать такие вещи как, регулярные выражения, лексический анализатор, ИИ в играх и тд.

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

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

        Пример 1
        • По горизонтали вверху находятся возможные входные символы.
        • По вертикали слева находятся текущие возможные состояния.

        image

        Здесь видно, что из состояния 0 в состояние 1 можно попасть только, если у нас будет входной символ 'a', из состояния 1 в состояние 2, если символ 'b'.


        Текущее состояние — множество состояний в котором автомат может находиться в данный момент времени.

        Стартовое состояние — состояние откуда КА начинает свою работу.

        Заключительное состояние — множество состояний в которых автомат принимает определенную цепочку символов, в ином случае отвергает.
        Читать дальше →
        • +19
        • 6,5k
        • 8
      • Ой, у вас баннер убежал!

        Ну. И что?
        Реклама
      • Ищем циклы на аттракторе Лоренца в пакете Maxima

          image

          Этот топик продолжает серию моих статей на Хабре, посвященных исследованию аттрактора Лоренца.

          Часть 1. Критический взгляд на аттрактор Лоренца
          Часть 2. Динамическая система Лоренца и вычислительный эксперимент
          Часть 3. О существовании периодических решений в системе Лоренца
          Часть 4. Три цикла в аттракторе Лоренца

          Итак, рассмотрим нелинейную систему дифференциальных уравнений, введенную Эдвардом Лоренцом в 1963 году:

          $ (1)\left\{ \begin{array}{l} \dot{x}=\sigma(y-x),\\ \dot{y}=rx-y-xz,\\ \dot{z}=xy-bz, \end{array}\right. $

          где

          $\sigma=10,\:r=28,\:b=8/3\:-$

          классические значения параметров системы.
          Читать дальше →
        • Ричард Хэмминг: Глава 6. Искусственный интеллект — 1

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

          imageПривет, Хабр. Помните офигенную статью «Вы и ваша работа» (+219, 2394 в закладки, 380k прочтений)?

          Так вот у Хэмминга (да, да, самоконтролирующиеся и самокорректирующиеся коды Хэмминга) есть целая книга, написанная по мотивам его лекций. Мы ее переводим, ведь мужик дело говорит.

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

          Мы уже перевели 19 (из 30) глав. И ведем работу над изданием «в бумаге».

          Глава 6. Искусственный интеллект — 1


          (За перевод спасибо Иванникову Алексею, который откликнулся на мой призыв в «предыдущей главе».) Кто хочет помочь с переводом, версткой и изданием книги — пишите в личку или на почту magisterludi2016@yandex.ru

          Рассматривая историю компьютерных приложений, мы обращаем внимание на возможности пределов машин не столько в плане вычислительной сложности, сколько в плане классов задач, которые компьютер сможет или возможно не сможет решать в будущем. Перед дальнейшим рассуждениями необходимо напомнить, что компьютеры оперируют символами, а не информацией; мы не можем просто сказать, не говоря о том, чтобы написать, программу в терминах “информации”. Все мы считаем, что знаем значения слов, но хорошие размышления с вашей стороны убедят в том, что, в лучшем случае, информация — это нечёткая концепция и ей нельзя дать определение, которое можно сконвертировать программе.
          Читать дальше →
        • Алан Кей: Как обстоят дела у всего человечества, вид «из космоса»

          • Перевод
          Почему же тогда наука и ее картографический язык — математика — считаются трудными для изучения? Я считаю, что это происходит не потому, что они настолько сложны, а скорее потому, что они на удивление просты, но очень сильно отличаются от обычного, здравого человеческого мышления.
          Моими любимыми примерами ранней науки и замечательной общей метафорой о том, чем занимается наука являются попытки точного картографирования, которое было начато греками и потеряно впоследствии на тысячи лет, а затем возобновлено в 15 веке. К концу 1700-х люди были в восторге от того, что могли купить карманный глобус «мира таким каким он выглядит из космоса». Спустя 200 лет мы вышли в космос, вспомнили прошлое, сделали фотографии и увидели то, что уже давно определили составители карт в 18 веке.

          image

          Все научные процессы и знания носят этот характер: это попытки «увидеть» и представить вещи очень точно с разных точек зрения, которые не являются частью наших разумных догадок о мире. Мы хотим сделать невидимое видимым. Большую часть истории человечества наши теории о себе и о мире, в котором мы живем, были, в основном, построены на необоснованных убеждениях, которые служили утешительными историями. Несколько лет назад мы обнаружили новый способ видения, который позволил нам воспринимать физический мир как бы «из космоса» с гораздо меньшим количеством предрассудков. В XXI веке нам нужно не только сделать это для физического мира, но и понять наше человеческое состояние словно смотрим на него «из космоса», без каких-либо утешительных историй, но с более глубоким пониманием того, как нам бороться с нашей человеческой природой и воспитанием.
          Читать дальше →
          • +11
          • 4,2k
          • 3
        • Два акселерометра, губка для посуды и четыре гайки

            Вводная: измерение угла маятника


            Итак, разобравшись с датчиками Холла для бесколлекторных двигателей, покажу для чего это было нужно. Я сделал стенд с простейшим обратным маятником, который стабилизируется при помощи маховика, вращаемого моторчиком на свободном конце маятника:


            Читать дальше →
          Самое читаемое