• «Магическая константа» 0x5f3759df

    • Перевод
    В этой статье мы поговорим о «магической» константе 0x5f3759df, лежащей в основе элегантного алгоритмического трюка для быстрого вычисления обратного квадратного корня.

    Вот полная реализация этого алгоритма:

    float FastInvSqrt(float x) {
      float xhalf = 0.5f * x;
      int i = *(int*)&x;  // представим биты float в виде целого числа
      i = 0x5f3759df - (i >> 1);  // какого черта здесь происходит ?
      x = *(float*)&i;
      x = x*(1.5f-(xhalf*x*x));
      return x;
    }

    Этот код вычисляет некоторое (достаточно неплохое) приближение для формулы

    image

    Сегодня данная реализация уже хорошо известна, и стала она такой после появления в коде игры Quake III Arena в 2005 году. Её создание когда-то приписывали Джону Кармаку, но выяснилось, что корни уходят намного дальше – к Ardent Computer, где в середине 80-ых её написал Грег Уолш. Конкретно та версия кода, которая показана выше (с забавными комментариями), действительно из кода Quake.
    В этой статье мы попробуем разобраться с данным хаком, математически вывести эту самую константу и попробовать обобщить данный метод для вычисления произвольных степеней от -1 до 1.

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

    • Перевод
    «Я экспериментировал с задачами кубического представления в стиле предыдущей работы Эндрю и Ричарда Гая. Численные результаты были потрясающими…» (комментарий на MathOverflow)
    Вот так ушедший на покой математик Аллан Маклауд наткнулся на это уравнение несколько лет назад. И оно действительно очень интересно. Честно говоря, это одно из лучших диофантовых уравнений, которое я когда-либо видел, но видел я их не очень много.

    Я нашёл его, когда оно начало распространяться как выцепляющая в сети нердов картинка-псевдомем, придуманная чьим-то безжалостным умом (Сридхар, это был ты?). Я не понял сразу, что это такое. Картинка выглядела так:


    «95% людей не решат эту загадку. Сможете найти положительные целочисленные значения?»

    Вы наверно уже видели похожие картинки-мемы. Это всегда чистейший мусор, кликбэйты: «95% выпускников МТИ не решат её!». «Она» — это какая-нибудь глупая или плохо сформулированная задачка, или же тривиальная разминка для мозга.

    Но эта картинка совсем другая. Этот мем — умная или злобная шутка. Примерно у 99,999995% людей нет ни малейших шансов её решить, в том числе и у доброй части математиков из ведущих университетов, не занимающихся теорией чисел. Да, она решаема, но при этом по-настоящему сложна. (Кстати, её не придумал Сридхар, точнее, не он полностью. См. историю в этом комментарии).

    Вы можете подумать, что если ничего другое не помогает, то можно просто заставить компьютер решать её. Очень просто написать компьютерную программу для поиска решений этого кажущегося простым уравнения. Разумеется, компьютер рано или поздно найдёт их, если они существуют. Большая ошибка. Здесь метод простого перебора компьютером будет бесполезен.
    Читать дальше →
  • Реверс-инжиниринг одной строчки JavaScript

    • Перевод
    Несколько месяцев назад я получил от друга такое письмо:



    Тема: Можешь объяснить мне эту одну строчку кода?

    Текст: Считай меня тупым, но… я не понимаю её и буду благодарен, если растолкуешь подробно. Это трассировщик лучей в 128 символах. Мне кажется, он восхитительный.

    <pre id=p><script>n=setInterval("for(n+=7,i=k,P='p.\\n';i-=1/k;P+=P[i%2?(i%2*j-j+n/k^j)&1:2])j=k/i;p.innerHTML=P",k=64)</script>



    Эта строчка JavaScript отрисует анимацию, которая показана на изображении под катом. В браузере она запускается здесь. Скрипт написан автором www.p01.org, где вы можете найти эту и много других классных демок.
    Читать дальше →
  • Сложный квест для хабравчан: 25 уровней



      Всем привет, меня зовут Влад, я программист в Mail.Ru Group. В 2010 году я делал квест для хабраюзеров и его прошло более 10 тысяч человек. На этот день программиста я решил сделать что-то похожее, но немного не успел: усложнял квест и не смог остановиться. (-:

      Решать головоломку здесь: puzzle.mail.ru

      Призы! Первому, кто ответит на все 25 вопросов, мы подарим Raspberry Pi 3 от DIY-сообщества Mail.Ru Group. Еще есть промежуточный приз: тот, кто первым пройдет 15-й уровень, получит от меня инвайт на Хабр.
      Читать дальше
    • Алгоритм Метромарафона. Как аналитик Яндекса просчитал, что все станции можно посетить за один день

        12 мая мы с товарищами зашли в московское метро с его открытием утром и, не выбираясь наверх, посетили все 199 доступных в данный момент станций до закрытия метрополитена. Зачем мы всё это сделали – совершенно не ясно, но я попробую рассказать, как так получилось.


        Давным-давно, кажется, с год назад жена сказала мне, что хотела бы как-нибудь сфотографировать все станции метро в Москве. Я тогда пошутил, что под такое дело можно рассчитать оптимальный маршрут, позволяющий посетить все станции, напрягаясь по-минимуму. Пошутил и забыл, а тут зимой вспомнил и решил попробовать.



        По мере изучения вопроса я обнаружил, что идея сама по себе не то чтобы очень нова – в нью-йоркской подземке аналогичные соревнования проходят с 1966 года. Что же касается московского метро, то ЖЖ-пользователь estrella-de-sur полгода назад проехал его за 12 часов 36 минут (расчётное время – 11 часов 50 минут) по правилу «один шаг на каждую станцию». Но у нас была другая задача – мы хотели выйти на каждой станции и по возможности красиво её сфотографировать. Это означало, что нам в большинстве случаев придётся ждать на ней следующего поезда. Исходя из этого я и строил расчёт.


        Предупреждение: если вы умеете решать задачу коммивояжёра на 200 узлах (с помощью генетических алгоритмов или без них) – вас, скорее всего, ждут в другом месте. Можете просто пролистать пост и посмотреть картинки.

        Читать дальше →
      • Как я искал (и нашел) разницу в двух побайтово идентичных файлах

          Есть у нас одно .NET-приложение, которое умеет загружать и использовать плагины. Плагины — дело хорошее. Можно функционал расширять, можно оперативненько обновлять их со своего сайта, можно даже юзерам дать SDK и позволить писать свои плагины. Мы всё это и делали. Наши плагины представляли собой обычные .NET-сборки, которые нужно было подкинуть в определённую папку, откуда основное приложения их загружало и использовало. Ну, вы, наверное представляете как — Assembly.Load(), дальше ищем класс, реализующий необходимый интерфейс, создаём объект этого класса и т.д. Всё это работало давно, стабильно и ничто не предвещало беды. Но вдруг в какой-то момент появилась необходимость создать плагин, состоящий из нескольких файлов. В связи с этим было решено считать плагином не просто .NET-сборку (1 файл), а zip-архив, в котором может быть как одна сборка, так и несколько файлов. В связи с этим пришлось научить билд-сервер паковать плагины в архивы, а основное приложение — разархивировать их в нужное место. В общем-то задача на 10 строк кода. Ничто не предвещало беды. И вот скачиваю я с билд-сервера собранный архив с плагином, разархивирую его в нужную папку, запускаю приложение, и… не работает! Стоп, как не работает? Это ведь тот же плагин!

          Дальше — больше. Прошу проделать ту же самую процедуру моего коллегу, на его компьютере. Он пробует — и у него всё работает! Но как же так? Одна версия приложения, один и тот же файл с билд-сервера. Какая-то разница в окружении? Сажусь за компьютер коллеги, пробую ещё раз — не работает! Он в этом время пробует на моём — работает! То есть получается, что файл «помнит», кто его разархивировал! Зовём третьего коллегу понаблюдать этот цирк. Последовательно, на одном и том же компьютере, по очереди делаем одни и те же действия: скачиваем архив с плагином, разархивируем в нужную папку, запускаем приложение. Когда это делаю я — программа не видит плагин, когда это делает коллега — всё работает. На третьем круге этих интересных экспериментов вдруг замечаем разницу в действиях: я разархивировал плагин стандартными средствами Windows, а мой коллега — с помощью 7-Zip. И то и другое вызывалось нами из контекстного меню архива, так что разницу в клик по не тому пункту вначале никто не замечал. Ну ок. Получается, файл, извлечённый из zip-архива с помощью 7-zip, отличается от того же файла из того же архива, извлечённого с помощью стандартного архиватора Windows?

          Кстати, пока вы не открыли статью под катом, ответьте-ка сами для себя на вопрос, может ли такое быть, что содержимое файлов валидного zip-архива при разархивации 7-zip и через проводник Windows будет разным?
          Читать дальше →
        • Реклама помогает поддерживать и развивать наши сервисы

          Подробнее
          Реклама
        • Математическая задача о 100 коробках и спасении заключенных

          Предлагаю читателям «Хабрахабра» перевод публикации «100 Prisoners Escape Puzzle», которую я нашел на сайте компании DataGenetics. Все ошибки по данной статье присылайте, пожалуйста, в личные сообщения.

          По условию задачи в тюрьме находится 100 заключенных, каждый из которых имеет личный номер от 1 до 100. Тюремщик решает дать заключенным шанс на освобождение и предлагает пройти придуманное им испытание. Если все заключенные справятся, то они свободны, если хотя бы один провалится — все умрут.


          Читать дальше →
        • Задача о 64 монетах, двух заключённых и одной шахматной доске

          • Перевод


          Примечание переводчика: я заменил оригинальные обозначения сторон монеты head/tail на аверс/реверс, чтобы не вносить путаницу русскоязычными орёл/решка. На иллюстрации выше слева аверс (head), справа реверс (tail).

          Спасение невозможно?


          Это одна из тех типичных загадок о заключённых, в которых вы приговорены к смерти и можете спастись, только если докажете свои умственные способности тюремщику. Вы и ваш друг были заключены в тюрьму. Ваш тюремщик предлагает вам испытание. Если вы его выполните, вы оба будете освобождены.
          Читать дальше →
        • Алгоритм поиска неисправности в драйвере LED лампы или Эркюль Пуаро отдыхает

            Недавно один знакомый попросил меня помочь с проблемой. Он занимается разработкой LED ламп, попутно ими приторговывая. У него скопилось некоторое количество ламп, работающих неправильно. Внешне это выражается так – при включении лампа вспыхивает на короткое время (менее секунды) на секунду гаснет и так повторяется бесконечно. Он дал мне на исследование три таких лампы, я проблему решил, неисправность оказалась очень интересной (прямо в стиле Эркюля Пуаро) и я хочу рассказать о пути поиска неисправности.
            Читать дальше →
          • Исследование причин аномального голосования на сайте РОИ или особенности электронной демократии в России

              За сайтом «Российские общественные инициативы» я наблюдаю давно, примерно с 29 мая 2013 года. Как и другие наблюдатели, я замечал аномалии в ходе голосований за различные инициативы. Но это мало кого беспокоило, пока аномалии приводили по нашим оценкам к росту числа голосов. Видимо, никто не считал чем-то плохим, если очередная инициатива наберет 100 000 голосов раньше срока. Всё изменилось, когда аномалии стали замедлять голосование.

              Отзывы голосов на РОИ

              Это началось 24 ноября в 13:35 по московскому времени. Счетчик голосов за принятие инициативы 9376 уменьшился на 2. Потом еще на 1 и еще на 2. Вечером уменьшение значения счетчика стало происходить всё чаще и чаще. Кто-то заметил это и сообщил автору инициативы. С этого момента начался тщательный мониторинг хода голосования.

              Я расскажу про некоторые странности голосования, которые мы (наблюдатели) заметили за последнюю неделю. Также я попытаюсь сделать предположения о причинах некоторых из них. Выводов довольно мало, т.к. не всегда есть возможность получить нужные данные о ходе голосования.
              Читать дальше →
            Самое читаемое