За время существования индустрии разработки игр формул разных механик, способных развлечь нас, придумали не одну сотню. Что-то умерло засветившись в паре игр, что-то ушло со временем, какие-то существуют до сих пор. Есть и такие, которые не просто выжили, но стали мейнстримом, хотя только портят нервы игрокам. Игровой дизайн большинства старых игр, от второго фолыча до первого FarCry и пятью активными перками, пусть и не был вершиной искусства — затягивал не хуже современных песочниц с миллионом активностей. Редкую игру захочется пройти второй раз, а как вспомню, что на прохождение можно потратить под сотню и больше часов — думаю, а оно мне действительно было надо? Можно же было заняться чем-то более интересным. Я знаю, чем закончился второй фолыч, знаю это уже четвертый раз, но каждый раз игра удивляет меня чем-то новым. А вот нового «Аватара» бросил на половине, слишком много всего и все недоделанное, и прозрачные стены… просто бич игры. И тут вопрос, чего-то не хватает в этой раздутой, перекачанной сотней механик игре? Только задумайтесь — в аватаре больше сотни основных механик, которые влияют на окружение. Может в играх что-то потерялось? Хотя «потерялось» — звучит странно — за столько лет индустрия только создала просто море всего нового. Статья ориентирована на «побурчать», так что не ждите каких-то великих секретов и тонкостей мастерства.

Четкие цели

У всех игр (что я играл) где-то до конца 10-х была цель. Тот же Fallout 2(1998), Assassin’s Creed(2007), S.T.A.L.K.E.R(200x), не водит игрока за ручку, показывая маркером на карте, куда надо бежать. Скажу больше, вы сами пробуете понять куда идти, как выполнять квесты разговаривая с жителями, взламывая терминалы, читая заметки и дневники. И это интересно, погружает в лор игры покруче любых катсцен. А основная цель все равно всплывает в разговорах, какой бы квест не надо было выполнять. Мorrowind(2002), главный герой — перерождение легендарного героя Неревара, цель — выполнить пророчество и победить великого злодея — вампира Даготу, который планирует использовать какое-то старинное оружие массового поражения, это становится известно в первые пару часов игры. Что еще отличает эти игры, они давали возможность создавать собственные цели и добиваться их, и это было наиболее интересным времяпрепровождением. В 2009 появляется Minecraft, вот он наверное всех и сломал 🙂 поставив несюжетную составляющую игры во главу всего. И другие разработчики, хотели или не хотели, тащили эти идеи в свои игры, вот только не всегда это полезно.

Первый ассасин был прекрасен: отличный, атмосферный сеттинг, законченная история. Почти полная свобода действий, можно забраться куда угодно и пробежать по крышам с одного конца города до другого. Вторая часть, тоже не отставала и поражала своими историческими видами и локациями, можно было просто бродить по узким венецианским улицам, потратив на это не один час игры — настолько они были классные. Не было желания побыстрее проскочить open world между миссиями.

Системный дизайн

Размытие или отсутствие целей в играх, привело к тому, что стало возможным делать игры неполностью, перейти на так называемый несистемный дизайн — это когда вы создаете механики в отрыве друг от друга, и надеетесь, что ближе к релизу оно срастется в одно целое.

Хороший системный дизайн конфликтует с dlc, потому что вам сразу надо сделать целостную игру, а dlc — самое злое, что могло случиться с индустрией. Но не путайте с сюжетными и покрасочными dlc, которые получились когда покатили фишки игры, потому что не успевали к релизу. Это относится к запланированному отрезанию частей, чтобы потом срубить еще деньжат после выхода, превращая полноценную игру в игру-сервис. Сама суть проблемы — разделение игру на такие части ломает игру, ломает сюжет, ломает механики, ломает активности. Зато это дает возможность выпускать «незаконченную» версию под видом полноценной игры, делая поток финансов более контролируемым и понятным во времени, это именно то, что надо менеджменту. В среднем игры с dlc зарабатывают в два раза больше денег на копию. Вы знаете сколько раз Fallout2 был под угрозой закрытия? Из официальных источников — 8. А может вам интересно сколько дополнений вышло для Fallout76? 7 крупных и больше сотни мелких. Несистемный дизайн позволяет делать игру частями, но при этом теряется целостность игры и её приходится делать проще. Простые игры, любого размера проще контролировать, студия дружно отчитывается о сделанных уровнях, все идет по плану, майлстоуны сдаются и бета версии играются — но «игры» нет, потому что там только половина игры, а вторая половина в dlc, которые будут выпущены после, генерируя контролируемый кеш-флоу.

Миссии и открытый мир

Эта потерянная механика вытекает из предыдущей, если нет системного дизайна и положенного на него сюжета, то вам не надо думать о создании интересных миссий. Где-то после начала 10-х разработчики почему-то решили, что создавать хорошо поставленные, интересные, продуманные и сложные миссии — это лишнее. А про двойное дно и серую мораль с разными концовками в квестах (в квестах, не в игре) и подавно забыли. Но взамен мы получили открытый мир и зачистку территорий. У вас прекрасный сюжет, прописанный конфликт и отличный нарратив? Давайте разбавим всё это десятками однотипных заданий подай-принеси-заруби. Смотрите сюжетный ролик и бегом зачищать карту. И так раз за разом, в каждом втором проекте. Давно ли вам приходилось прыгать по плиткам с именем умершего бога, притом что книга с именем находится в библиотеке у черта на куличках, или помогать ангелу в расследовании пропажи сестры с 8 разными концовками в отдельном квесте? Даже в последних частях Hitman, уж насколько эта игра отлично ложится на подобные песочницы, дается только 2-3 варианта решения на уровне и только специальными предметами, хотя даже в первых частях было возможно использовать все что было в инвентаре, от удавки и яда до упавшего лифта. Есть такое понятие в дизайне уровней как behavior base — это когда уровень строится так чтобы в любую есть часть можно было попасть минимум тремя путями, родоначальником таких дизайна уровней был DeusEx — сами уровни закрытые и не особо большие, но ощущаются как огромные песочницы, именно по этой причине. И даже спустя дцать лет после выхода первой части, там находят новые пути прохождения квестов. О том, что можно нанять почти любого компаньона для прохождения миссий (через консоль и читы, в оригинальной игре этой возможности нет), я узнал только в прошлом. Но сама такая возможность закладывалась. A c помощью пары модов, можно играть кооп по сети в сингл, будут бегать два JC Dentonа, причем каждый может выполнять свои квесты, что неудивительно для изначально сетевого Unreal Engine.

Уровень врагов

Повсеместно избавляясь от системного дизайна, в плане создания игры как единой целой системы, а не множества мелких с попытками подружить их перед релизом, многие разработчики столкнулись с тем, что приходится убирать систему уровней врагов, потому что получившегося монстра забалансить практически невозможно, и тут кому в голову приходит идея, а давайте поднимать уровень врагов вместе с уровнем игрока. После «практически идеальной и вылизанной» системы уровней, как игрока так и врагов, в Morrowind, выходит TES4 c автоматическим ростом «дамага» противников параллельно развитию главного героя. Блин, да чтобы убить какую-то завалящую крысу приходилось сказать вокруг неё две минуты в топовых шмотках.

Ладно крысы, другой вариант — «решительно» отыгрываем роль вора в старых свитках, наваливаем экспу в скрытность больше, чем на меч и щит. На раз обносим все дома в городе все из себя такие невидимые и беспощадные Робингуды, растем в уровнях. А потом «внезапно» начинаем проходить сюжетный боевой квест, помним при этом, что миссии уже «исправили», и банально не можем его пройти стелсом. Вояка из нашего каджита хуже чем никакой, а врагов в квесте много и они хорошего такого уровня, если бы виртуоз отмычек и ловких рук был воином. Пока качали вора, воины качали воинов, всё — приехали. В итоге на поздних стадиях игры всякий зачуханный грабитель-каджит начинал щеголять даэдрическими доспехами, таская параллельно еще одёжу для «небоевых операций» и «магических квестов». Многие просто создавали нового героя, потому что ветки прохождения за небоевые билды были банально сломаны. Другие разработчики смотря на космические продажи четвертых свитков, начинали думать, что автолевелинг не такая уж и плохая штука. Чтобы понять ущербность такого подхода в сюжетных играх, понадобилось больше 10 лет и дцать крупных проектов с плохим рейтингом, да и сейчас во многих играх автолевелинг остался, пусть и в гибридном виде, ведь это намного проще чем балансить игру.

Обучение через взаимодействие

Стремление показать каждый уголок игры, каждую механику приводит к тому, что обучение перегружено. Начиная от контекстных подсказок и заканчивая маркером на карте, указания предельно четкие, разбиты на мелкие шаги, чтобы даже трехлетний ребенок смог их понять, и это происходит почти во всех играх. Постановка четких целей конечно важна, но она не должна превращаться в путь от одного вейпоинта к другому. В старых играх тоже было обучение, обучающие миссии, но они были выстроены так, чтобы игрок додумался до использования конкретной вещи, системы или механики. И это делало обучение более ценным, чем простые подсказки или явные миссии, которые учат таким навыкам. В первом Thief игрок просто находил водяную стрелу, как её применять он постигал на уровне: можно затушить факел, можно выстрелить в пол и пройти тише, можно выстрелить в кувшин с маслом, и тогда площадь его растекания будет больше, и его не будут замечать стражники. К сожалению технологии древних по созданию такого вида обучения утеряны в конце десятых.

Почему делают всплывающие подсказки или явные миссии? Во первых создание обучения откладывается на самый последний момент, или даже на этап финальных правок за месяц до релиза. Иногда это вызвано меняющимся концептом, но основная причина это презентабельность, обучение почти всегда идет в начале игры, ощущение от небрежно созданных миссий, пусть даже и обучающих, остается потом на всю игру. Выделять на обучающие миссии целого дизайнера, а то и не одного, становится слишком дорого. Остается использовать универсальные и простые инструменты для обучения вроде попапов, они не требуют контекста. Пусть это и воспринимается как вытаскивание игрока из процесса, зато не вызывает негатива по отношению к остальной игре. Это слова из интервью с Шери Грейнер Рэй, если коротко, то нормальное внутриигровое обучение — долго, дорого и немодно.

Хороший пример обучения — Half-Life2, я не помню были ли там всплывающие окошки (скорее всего нет), но вот что уровни построены так, что на обучении враги физически не могут вам причинить вред, но показывают при этом большинство свой возможностей помню хорошо.

Награда и Наказание

Остались только награды за прогресс: новые предметы, опыт, сюжетные элементы и т.д. А такой важный мотиватор как наказание пропал, это не ошибка дизайнеров, люди расстраиваются, если не выигрывают. Расстроенный игрок пишет плохой отзыв об игре, его читают другие люди и не покупают игру. Наказание убрали, потому что это ведет к меньшим продажам. Давно ли вы видели аптечки в играх, а не просто посидеть в углу? В первых двух BG поведение с компаньонами влияло на шанс выпадения предметов в сундуках, в TES3/4 неправильно собранный билд закрывает квестовые ветки и возможность пройти целые квесты, Half-Life 2 — заставляет решать физические головоломки, чтобы пройти по сюжету. Первые Thief — штрафуют игрока за убийства, применение водяных стрел и громкие кражи, а потом продавцы дают меньше денег за хабар и едко комментируют приключения шумного вора. Это одна из немногих игр, которая честно использует звук окружения для нпс. Персонажи вокруг используют туже систему обнаружения, которая доступна игроку. Каждая поверхность имеет свою характеристику “шумности”. Самая шумная — металлическая, быстро выдаст вас всем стоящим рядом. Ковры заметно глушат шаги настолько, что по нему можно побегать и попрыгать, стражники кстати тоже. Каменный пол — звучит по разному, если вы до этого были в воде. А зеленая поверхность растительности шумит если вы там ходите. А еще звук — это не только шаги, но и стук тела упавшего солдата, прыжки с какой-либо высоты, звяканье брошенной тарелки или кружки, ваши и чужие действия.

Современные игры не наказывают за такое, потому что это снижает продажи: «Players money first’ что называется. M&M3 — Не знаете особенностей монстров? Карту скорее всего сольете даже на среднем уровне AI, за красивой картинкой скрываются подсчеты на листе бумаги.

Не уважаете механику стрельбы в Max Payne? Добро пожаловать на чек-поинт. И так пока не научитесь стрелять. Игра не прощает промахов даже на самом простом уровне, и никакой помощи на gamepad.

Система кармы

А эта проблема вытекает из отсутствия наказания, если нет наказания, то назаканием становится уменьшение награды. В большинстве современных игр есть фракции, отношения с персонажами, формально и карма в большинстве игр осталась, вот только она практически ни на что не влияет. А ведь раньше поступки действительно влияли на сюжет, в том же фолыче — вырезав как-то рандомную деревню бандитов на карте мира (случайно вышло, слово за слово, ежик и получил по морде) и вернувшись туда через какое-то время, обнаружил там людей из случайно каравана, встреченного на другом конце карты. И только потом вспомнил, что в беседе упомянул про свободную деревню в диалоге. Выполнил какой-то мелкий квест. А проходя New Reno, встретил жителя той деревни, который помог с квестом на ликвидацию одного из мафиозных кланов города. Да, наверное это был выписанный линейка квестов, которая хорошо ложится на случайные события, но какова её вероятность при отыгрыше, чтобы его специально так задизайнили? А в конце показали зарисовку с этой деревней. И это только одна из мелочей c кармой, сколько их было в каждом прохождении наверно и не вспомнить.

В Fable (2004) вам даже дом не везде продадут, а жители будут отказываться разговаривать если им не нравится ваше поведение. Причем есть два типа кармы, локальная и глобальная, относительно каждого жителя. Локальная получается, когда местные жители видят или расшаривают информацию о ваших действиях в пределах деревеньки, и она «забывается» со временем. Глобальная влияет на общее впечатление и внешний вид.

И наверное одна из лучших реализаций кармы в Vampire: The Masquerade – Bloodlines (2004)
В игре у игрока есть параметр «человечности», он никак не отображается, и за ним надо следить самому. В безумие может впасть и самый добрый вампир на уровне, просто это очень маловероятно. При использовании некоторых действий и принятии злых решений повышается вероятность впасть в безумие, когда игрок теряет возможность управлять персонажем и последний устраивает массакр человекам вокруг без участия клавиатуры.

Видимые стены и ограничения

Разработчики стали бояться ограничения пространства, стремление показать насколько игра масштабная и открытая затмевает кажется всё остальное (опять спасибо майнкрафту). Если у вас нет открытого мира — фу-фу-фу, ждите в два раза меньше галочек в вишлисте. Поэтому и лепят его — кто во что горазд. Конечно игровой дизайнер должен держать игрока в определенных границах мира, но ограничения (невидимые стены) без уважительной причины вызывают очередные wtf!?. Худшее, что можно сделать здесь — это поставить невидимые стены, которые не позволят исследовать дальше. Проще всего поставить невидимую стену, чем вписать любое ограничение в игру. Но теперь показать стену считается чем-то постыдным, надо сделать отличный вид уходящий вдаль и не пускать туда.

Дизайн для игрока

Fallout — это круто. Давайте сделаем новый фолыч. Знаете почему фолыч крут? Он не пытался никого повторить. Не вижу ничего плохого в том, чтобы заимствовать идеи из великих игр, но заимствовать — не значит копировать. Иначе на выходе получится так же, как в той крутой игре, что вышла в прошлом году, но похуже и с обрезанными текстурами. И вместо того, чтобы задать себе вопрос «А чем эта фича это будет интересна людям?», дизайнеры начинают накручивать рюшечки к известным механикам. А на выходе получается непонимание почему вот эта мега-фича не вызвала интерес. Ну как же так? На тестах наши QA говорили что все мегакруто.

Разработчики Uncharted моделят уровни так, чтобы в них было интересно играть детям сотрудников компании, не знаю как называется этот подход, но он точно работает уже четвертую игру подряд.

Беда многих команд, что они перестали делать игру для себя, Игру Мечты. Смотрят на графики, аудиторию, не задумываясь о фане и интересности геймплея, накручивают рющечки. Смотрят в рот издателю, который говорит делай раз, не делай два, потому что в прошлый раз это не окупилось. Сделали, шипнули и заплакали, потому что люди пошли играть в какую-то индюшатину. Или другая крайность — слепо верить в какой-то принцип, например, в реализм, не задумываясь, что и так хватает реалистичности вокруг. Или модная сейчас вера в большие проекты — надо побольше механик, побольше реализма, побольше карту — добавим всего, только побольше, побольше, и шипнем в стиме, там людей побольше, авось кто и купит. Много оружия, много монстров, много нпс, много активностей — почему это все должно быть интересно игроку — тайна за семью печатями. Больше не значит лучше, больше это просто больше. Основной критерий оценки игры — удовольствие. Фраза «а вот также было в игре полгода назад» не дает проекту +2 к успеху, и уж точно эта механика будет менее интересна, чем в той игре полгода назад.

Сложность

Игры перестали делать сложными, потому что от аудитории нет запроса на такие игры. Сложность игры напрямую коррелирует с количеством текстовой информации в ней, в сложных и интересных играх всегда было много текста, который нужно найти, прочитать, осмыслить и найти еще где применить эти знания — это все время, и его надо много на все эти действия. Зато есть запрос на казуалки, и короткие сессионные игры на 15 минут. На «Казуальные игры» в «узких» девелоперских кругах под ПК и большие консоли, честно, смотрят свысока, и немножко завидуют деньгам, которые там крутятся. Но казуальные — не значит «для идиотов», это значит они сделаны так просто, что будет понятно даже детям. А объяснить и показать сложные вещи простыми и главное интересно — задачка далеко не для середнячков, попробуйте, даже 10-летнего, ребенка увлечь CK3, а вот Сiv6 запросто. Это все равно, что пробовать объяснить исходники PhysX джуну. А там куда идет основная масса, там деньги. Дальше приходит издатель и спрашивает — «$$$ ???», остальные аргументы придумайте сами.

Размеры дистрибутива

Сaesar III в 98 году я пару дней носил на домашний комп такими флешками, потому что CD-привод был один на весь подъезд у соседа на пятом. А размер игры был что-то около 100Мб.

Оставлю тут, может кому интересно будет, закон Мура от разработчиков игр — размеры дистрибутива средней игры увеличивается вдвое каждые три года, и пусть вас не обманывает затишье в размерах дистрибутивов последние пару лет, часть размера просто ушло в онлайн. Примерно от 50% от размера дистрибутива на локальной машине, теперь шарится на CDN для доступа по запросу, но психологический барьер в 100Gb не за горами, и я верю скоро он будет преодолен, а там он снова уйдет на новый виток размеров.

Побурчать

Это не все потерянные знания древних, и наверное не большая их часть. Но остались еще ортодоксальные студии, которые знают как собирать «сложные и неудобные» игры, правда становится их все меньше. Понятно, что раньше и смузи был зеленее, и флешки квадратнее. Может еще игр было меньше, аудитория умнее и разработчики покруче. Но посмотрите на сложившуюся ситуацию с другой стороны, возможно мы находимся просто в начале подъёма качества, забыл как этот термин называется: ожидаемое качество проектов растет от года к году, вместе с этим неизбежно растет и накопленный опыт команд и индустрии в целом, а кто не осилил оказывается за бортом достаточно быстро. И когда-то это количество должно перерасти в качество я надеюсь, может и chatGPT скоро подтянется.

Через официальный каталог приложений Ubuntu Snap некоторое время распространялся фейковый криптокошелёк, средства с которых сразу переводились на сторонний адрес. У одного из пользователей удалось увести 9,84 BTC.

Это типичная supply chain attack, один из самых опасных видов атак. Он предполагает внедрение зловредов в официальные каналы поставки ПО. Например, в прошивки от производителя оборудования, официальные обновления программ, которые распространяются через официальные сайты, и т д.

Фальшивый криптокошелёк Exodus в официальном каталоге Snap компании Canonical был опубликован 6 февраля 2024 года (скриншот) и продержался там шесть дней.

12 февраля один из пользователей на форуме Snapchat рассказал о странном баге: после восстановления доступа к кошельку тот оказался пустым, а из истории кошелька следовало, что все средства перечислены на посторонний адрес.

Изучение софта в виртуальной машине с Wireshark показало, что пропажа средств из кошелька — не баг, а фича. Само приложение было мошеннической подделкой под оригинальный кошелёк Exodus.

От оригинального кошелька он отличался необычно малым размером бинарника, Фальшивая программа была создана с помощью фреймворка Flutter в отличие от оригинала на Electron.

При первом запуске приложение сразу спрашивало сид-фразу для восстановления доступа к онлайн-кошельку, после чего тот сразу опустошался.

В результате программа была удалена из каталога Snap.

Основатель Canonical и руководитель разработки Ubuntu Марк Шаттлворт признал, что вредоносных приложений с трюками социальной инженерии становится больше. Он сказал, что «мы живём во всё более опасном мире» и пообещал принять дополнительные меры безопасности для каталога программ Ubuntu, хотя компания тут мало чем может помочь.

Приём приложений в каталог автоматизирован, а опубликовать своё приложение довольно легко. Это уже не первый фальшивый криптокошелёк или майнер, опубликованный в каталоге Ubuntu за последние несколько лет. А некоторые из зловредов до сих пор работают на компьютерах пользователей. Для Ubuntu есть однострочник, который позволяет удалить сразу весь «криптомусор» из системы:

for s in 2048buntu hextris freecraft bip-web bitwallet btcwal btcwallet coinbase cryptowal electrum-wallet2 exodus exoduswal exoduswalet exodwallet guarda komodo ledger-live-wallet ledger1 ledgerlive liveledger metamask new-electrum-wallet sparrow sparrow-wallet sparrowwalet sparrowwallet trezor-wallet trezorwallet trustwallet; do sudo snap remove --purge $s; done

Выводы

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

Поэтому важно следить за ситуацией, быть в курсе существующих угроз и ничего не принимать на веру. Например, скачивать бинарное приложение даже с официального сайта или каталога — уже определённый риск, потому что мы не видим исходного кода и не знаем, что внутри этого приложения. В этом смысле самостоятельная компиляция из исходников гораздо безопаснее.

Разработчики находятся в преимущественном приложении по сравнению с обычными пользователями, потому что могут не только скомпилировать программу из исходного кода (это доступно каждому), но и проверить код перед компиляцией. Более того, они могут самостоятельно написать приложение с нужным функционалом для себя и своих близких. Например, тот же биткоин-кошелёк написать относительно просто, поскольку системные API открыты и хорошо документированы. То же самое можно сказать о приложениях для видеосвязи и многих других, которые можно написать для себя буквально за несколько дней, если чужие приложения не вызывают доверия или там нет нужных функций (либо наоборот, много лишнего).

По итогам истории с Exodus можно сделать вывод, что опасность скачивания бинарных приложений даже из официальных каталогов никуда не исчезла. Вредоносный код распространяется с пакетами PyPi и через каталог App Store. Можно предположить, что мошенники продолжат придумывать новые способы, как внедрять вредоносный код в официальные каналы поставки ПО.

Проверка небольших чисел на простоту — популярная подзадача в спортивном программировании. И тест Миллера-Рабина, пожалуй, наиболее популярный из простых алгоритмов для этого.

У меня давно было желание с ним поиграться, стараясь оптимизировать различными способами. Например, векторизовать и посмотреть, станет ли быстрее.

Дисклеймер. Я — Java разработчик, на C++ писал в основном только в университете. Так что местами мой код мог вдруг получиться каким-нибудь странным.
Сразу отмечу, что у меня не было цели написать портируемый код. Моей целью было развлечься и посмотреть, что я смогу сделать, а не предложить миру универсальное решение.

Какую именно задачу решаем

Цель: уметь понимать, является ли знаковое 32-битное целое число простым, и желательно быстро.

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

Вообще, хочется иметь аналог такой функции, только быстрый:

bool testNaive(int32_t n) {
    if (n <= 2) return n == 2;
    for (int32_t m = 2, boundary = sqrt(n); m <= boundary; m++) {
        if (n % m == 0) return false;
    }
    return true;
}

В коде выше приведён классический тест на простоту, который перебирает потенциальных кандидатов в делители числа n. Работает он за, то есть медленно.

Тест Миллера-Рабина

Тест Миллера-Рабина — вероятностный тест для проверки чисел на простоту. Но заранее зная верхнюю границу для проверяемого числа, этот тест несложно превратить в детерминированный, об этом чуть позже.

Тест простоты числа n состоит из нескольких раундов. На каждом раунде мы получаем один из двух ответов:
— число составное;
— число может быть простое, фиг знает.
Чем больше раундов мы получаем ответ «может быть простое», тем больше шанс, что число действительно простое.

Сам же раунд состоит из следующих действий:
— взять число 1 < a < n, да такое, которое ещё не использовалось в предыдущих раундах;
— проверить, является ли a «свидетелем простоты» числа n. Если не является, то n — составное, а если является, то n называют сильно псевдопростым по модулю a.

Далее я буду использовать имена переменных, как на википедии, чтобы было проще сверять. Проверка свидетельства простоты в тесте Миллера-Рабина происходит по следующему алгоритму:

• В первую очередь нужно отсеять чётные числа, допустимы только нечётные n.

• n нужно представить в виде . Стоит заметить, что s всегда больше 0.

• Выполнить следующий код. Внешне он отличается от псевдокода с википедии, но делает ровно то же самое. true означает сильную псевдопростоту n по модулю a:

int32_t s = __builtin_ctz(n - 1); // Число нулей в младших битах.
int32_t t = (n - 1) >> s;
int32_t x = pow_mod(a, t, n);     // Возведение в степень по модулю n.
if (x == 1) return true;
for (int i = 1; x != n - 1; i++) {
    if (i == s) return false;
    x = mul_mod(x, x, n);         // Возведение в квадрат по модулю n.
    if (x == 1) return false;
}
return true;

По какому принципу выбирать числа a? Лично я поступлю очень просто, хотя не факт что эффективно. На википедии есть ссылки на списки сильно псевдопростых чисел по модулю 2 и по модулю 3, так что мы могли бы сделать проверку для 2 и 3, и среди чисел, прошедших обе проверки, отсеять те, которые содержатся в обоих списках…

Но нет, на самом деле таких чисел довольно таки много. А вот если взять 2, 3 и 5, то в диапазоне от 1 до 2³¹ останется только 4 сильно псевдопростых числа:

• 25326001

• 161304001

• 960946321

• 1157839381

Их уже легко можно захардкодить, получив в итоге следующий код:

bool testMillerRabinInteger(int32_t n) {
    if ((n & 1) == 0) return n == 2;
    if (n < 9) return n > 1; // 3, 5 и 7.
    int32_t s = __builtin_ctz(n - 1);
    int32_t t = (n - 1) >> s;
    int32_t primes[3] = {2, 3, 5};
    for (int32_t a : primes) {
        int32_t x = pow_mod(a, t, n);
        if (x == 1) continue;
        for (int i = 1; x != n - 1; i++) {
            if (i == s) return false;
            x = mul_mod(x, x, n);
            if (x == 1) return false;
        }
    }
    switch (n) {
        case 25326001:
        case 161304001:
        case 960946321:
        case 1157839381:
            return false;
        default:
            return true;
    }
}

Это уже полностью детерминированный тест на простоту, бери и пользуйся! Осталось расписать упомянутые тут mul_mod и pow_mod.

Для произведения по модулю достаточно расширить как множители, так и модуль, до 64-битных целых, чтобы защититься от переполнения в произведении, получив
(int32_t) (((int64_t) a * b) % m).

Для возведения в степень будем использовать разновидность быстрого возведения в степень, чуть более простую в реализации:

int32_t pow_mod(int64_t n, int32_t power, int64_t m) {
    int64_t result = 1;
    while (power) {
        if (power & 1) result = (result * n) % m;
        n = (n * n) % m;
        power >>= 1;
    }
    return (int32_t) result;
}

Включаем -O3, тестируем — всё работает! Рассчитываем на то, что компилятор хорошо оптимизировал этот код и самим ничего доделывать не придётся (если бы…).

База готова, вступление на этом закончено. Перейдём ко вкусненькому.

Что такое векторизация

Векторизация кода — это его параллелизация на уровне данных. Это примерно то, что делают видеокарты — один поток исполнения, но много независимых наборов данных, обрабатываемых одновременно.

Для CPU векторизация реализуется специальными наборами инструкций, например SSE и AVX. Обычно программистам не стоит об этом беспокоиться — всю работу на себя должен брать компилятор, главное указать ему ключи оптимизации. Основная цель компиляторной векторизации — циклы по большим массивам данных.

В нашем случае больших циклов нет, а данных мало, но зато есть тело цикла, которое выполняется до 3-х раз для 3-х различных значений параметра a. Такие паттерны компилятор сам векторизовать не будет, даже не надейтесь. Моя цель — убрать этот цикл, сделав «обычный» код, проводящий вычисления над всеми нужными значениями a одновременно.

Итого, нужно решить 2 подзадачи:

• возведение в степень по модулю;

• цикл с возведениями в квадрат.

Поскольку в среднем s сильно меньше t (), то можно сказать, что возведение в степень должно занимать гораздо больше времени исполнения, а значит сосредоточиться в первую очередь стоит на нём.

Векторные типы и инструкции

В более-менее современных CPU архитектуры x86 есть 2 набора векторных регистров — 128-битные XMM и 256-битные YMM. Бывают ещё 512-битные регистры в AVX-512, но они не так распространены.

Напрямую с регистрами мы работать не будем. C++ — язык высокоуровневый, в нём есть специальные типы данных для векторов, как и библиотечные функции на этих типах, которые соответствуют инструкциям процессора. Такие функции называются интринсиками. Чтобы почитать о них подробнее, придётся включать VPN, ведь документация запрещена на территории РФ (самим Intel, никакого экстремизма).

В рамках данной статьи я буду компилироваться GCC с 17-й версией языка (если это вдруг важно). Подключив immintrin.h, можно получить доступ ко множеству типов __m128* и __m256*, отвечающим различным типам векторов, например:

• __m128i — это вектор из 4-х значений типа int32_t;

• __m256i — это вектор из 4-х значений типа int64_t;

• __m256d — это вектор из 4-х значений типа double.

Здесь видно первое преимущество векторов перед нашим циклом — они способны одновременно обрабатывать не 3 единицы данных, а 4. Это здорово, мы без каких-либо потерь можем добавить 4-е значение a, например, проверяя 2, 3, 5 и 7. Если снова заглянуть в OEIS, то будет видно, что все сильно псевдопростые числа по этим модулям, вплоть до 2147483648 (2³¹), являются истинно простыми, т.е. тот switch в конце больше не будет нужен!

Для векторизованного возведения в степень нам нужно найти функции произведения и взятия остатка от деления, всё должно быть просто. Помним, что обе эти операции выполнялись над 64-битными целыми, а значит работать будем с __m256i.

И тут мы попадаем в первую серьёзную ловушку:

• _mm256_mullo_epi64 — интринсик для умножения длинных целых, не компилируется:
  error: inlining failed in call to 'always_inline' '__m256i _mm256_mullo_epi64(__m256i, __m256i)': target specific option mismatch.

  Упс, кажется он доступен только для AVX-512. Мой процессор такого не умеет. Так что не удивительно, да и компилировался я только с -mavx -mavx2.

• Векторизованного вычисления остатка от деления не существует в принципе. А обычное деление длинных целых, называемое _mm256_div_epi64, которое мне выдала документация — это даже не инструкция CPU, а кастомная функция, вообще отсутствующая в GCC. Придётся импровизировать.

Я не первый человек, который задался вопросом векторизованного деления целых чисел. Универсальный ответ, который дают люди из интернета — пользуйтесь делением с плавающей точкой, пока вам хватает точности. А когда перестанет хватать — напишите дополнительный код исправления ошибки. Так что отвлечёмся на минутку и подумаем, сколько точности нам даст double, если решить использовать именно его.

Числа с плавающей точкой

Как устроены числа типа double? Наверное не все хорошо помнят, так что освежим эту информацию. Любое такое число представлено в виде 3-х частей:

• 1 бит для знака;

• 52 бита для «мантиссы»;

• 11 бит для «порядка», или же смещения плавающей точки.

double — это 53 значащих бита (мантисса + всегда присутствующая рядом с ней единица) и известное положение плавающей точки, которое может быть далеко за пределами значащих бит. Если пробовать кодировать только целые числа, то становится видно, что любое 53-битное беззнаковое число (54-битное знаковое соотв.) можно закодировать без потери точности.

64-битный int64_t мы использовали для того, чтобы не было переполнения при умножении 32-битных целых. А значит double можно использовать для того, чтобы избежать переполнения при умножении 26-битных чисел (53 / 2). Если ограничиться проверкой на простоту только 26-битных чисел, то этого будет легко достичь арифметикой с плавающей точкой. Так и поступим. Будем работать с четвёрками значений типа double, то есть с __m256d.

Возведение в степень по модулю

Проблема с умножением решена. Что же с делением с остатком? Для него нам придётся воспользоваться следующей формулой:

Реализовав эту формулу, мы получим следующую функцию вычисления произведения по модулю, сразу для 4-х значений типа double (в комментариях — невекторизованный аналог):

__m256d mul_mod(__m256d a, __m256d b, __m256d m) {
    __m256d c = _mm256_mul_pd(a, b);     // double c = a * b;
    __m256d tmp = _mm256_div_pd(c, m);   // double tmp = c / m;
    tmp = _mm256_floor_pd(tmp);          // tmp = floor(tmp);
    tmp = _mm256_mul_pd(tmp, m);         // tmp = tmp * m;
    return _mm256_sub_pd(c, tmp);        // return c - tmp;
}

Код возведения в степень же почти не будет отличаться от невекторизованного варианта:

__m256d pow_mod(__m256d n, int32_t power, __m256d m) {
    __m256d result = _mm256_set1_pd(1);  // result = {1, 1, 1, 1};
    while (power) {
        if (power & 1) result = mul_mod(result, n, m);
        n = mul_mod(n, n, m);
        power >>= 1;
    }
    return result;
}

Цикл с квадратами

Если попробовать сейчас собрать воедино то, что есть, то получим следующий код:

bool testMillerRabinVectorized0(int32_t n) {
    if ((n & 1) == 0) return n == 2;
    if (n < 9) return n > 1;
    int32_t s = __builtin_ctz(n - 1);
    int32_t t = (n - 1) >> s;
    __m256d primes = _mm256_set_pd(2, 3, 5, 7);
    __m256d n_pd = _mm256_set1_pd(n);
    __m256d x = pow_mod(primes, t, n_pd);
    // ?
}

На месте вопроса раньше стоял цикл, внутри которого во первых встречаются выражения return / continue, а во вторых для разных a там может быть разное число итераций:

if (x == 1) continue;
for (int i = 1; x != n - 1; i++) {
    if (i == s) return false;
    x = mul_mod(x, x, n);
    if (x == 1) return false;
}

Нужно привести этот код к виду, пригодному для векторизации. Парадоксально, но для этого нам потребуется выбросить условие выхода при x == 1 внутри цикла, оставим только выход по числу итераций и по x == n - 1. Сейчас объясню.

Сделаем так: будем присваивать x = 0, если это псеводпростое по модулю a. Если x станет равным 0 для всех a, то число n — простое, иначе — нет. Опишем это следующим псевдокодом:

if (x == 1)     x = 0;
if (x == n - 1) x = 0;
if (x == 0 forall a)     // x - сильно псевдопростое по всем модулям a.
    return true;
for (int i = 1; i < s; i++) {
    x = mul_mod(x, x, n);
    if (x == n - 1) x = 0;
    if (x == 0 forall a) // x - сильно псевдопростое по всем модулям a.
        return true;
}
return false;

Если на какой-то итерации x стал равным 1, то он останется 1 и на следующих итерациях, ведь 1 * 1 = 1. То же самое с 0, так как 0 * 0 = 0. В итоге return false на последней строке сработает, если:

• для какого-то a мы получили x == 1;

• для какого-то a мы получили i == s.

Это именно те условия выхода, которые нам нужны. Векторизованная версия этого кода будет выглядеть так:

__m256d n_minus_one = _mm256_set1_pd(n - 1);
x = blend_zero(x, _mm256_set1_pd(1)); // if (x == 1)     x = 0;
x = blend_zero(x, n_minus_one);       // if (x == n - 1) x = 0;
if (all_zero(x)) return true;
for (int i = 1; i < s; i++) {
    x = mul_mod(x, x, n_pd);
    x = blend_zero(x, n_minus_one);   // if (x == n - 1) x = 0;
    if (all_zero(x)) return true;
}
return false;

Что делает all_zero должно быть понятно из названия. blend_zero же делает покомпонентное сравнение элементов первого вектора с элементами второго вектора и проставляет в первом 0 там, где совпало, иначе оставляет оригинальное значение, где не совпало. Реализуются эти методы следующим образом:

const __m256d ZERO = _mm256_setzero_pd();
bool all_zero(__m256d a) {
    __m256d mask_pd = _mm256_cmp_pd(a, ZERO, _CMP_NEQ_OQ);
    return 0 == _mm256_movemask_pd(mask_pd);
}
__m256d blend_zero(__m256d a, __m256d b) {
    __m256d mask_pd = _mm256_cmp_pd(a, b, _CMP_EQ_OQ);
    return _mm256_blendv_pd(a, ZERO, mask_pd);
}

Маска типа __m256d содержит единичные биты (64 штуки, на весь double) в тех элементах, для которых условие в cmp выполнилось (в частности _CMP_NEQ_OQ или _CMP_EQ_OQ).

movemask преобразует вектор-маску в обычную битовую маску, где каждому элементу уже будет соответствовать ровно один бит, а не 64. То есть all_zero буквально проверяет, что «нет элементов, не равных 0». Да, двойное отрицание, и что?

_mm256_blendv_pd — составляет вектор из двух, беря элемент второго вектора, если в маске 1, либо первого вектора если в маске 0. Думаю, должно быть понятно, а если непонятно, то в документации есть псевдокод.

Кажется, что первая версия должна быть готова:

bool testMillerRabinVectorized(int32_t n) {
    if ((n & 1) == 0) return n == 2;
    if (n < 9) return n > 1;
    int32_t s = __builtin_ctz(n - 1);
    int32_t t = (n - 1) >> s;
    __m256d primes = _mm256_set_pd(2, 3, 5, 7);
    __m256d n_pd = _mm256_set1_pd(n);
    __m256d x = pow_mod(primes, t, n_pd);
    __m256d n_minus_one = _mm256_set1_pd(n - 1);
    x = blend_zero(x, _mm256_set1_pd(1));
    x = blend_zero(x, n_minus_one);
    if (all_zero(x)) return true;
    for (int i = 1; i < s; i++) {
        x = mul_mod(x, x, n_pd);
        x = blend_zero(x, n_minus_one);
        if (all_zero(x)) return true;
    }
    return false;
}

Сравниваем производительность

Методика тестирования у меня будет максимально тупая. Берём большой массив целых чисел и для каждого из них проверяем, является ли оно простым. У меня вышел следующий код:

void measure(std::function<bool(int32_t)> test, uint32_t count) {
    auto start = std::chrono::high_resolution_clock::now();
    int32_t n = 0;
    for (uint32_t i = 1; i < count; i++) {
        n += test(i);
    }
    auto end = std::chrono::high_resolution_clock::now();
    std::cout << (end - start).count() * 1e-9d << " seconds" << std::endl;
    std::cout << n << " primes found" << std::endl << std::endl;
}

Запустим его для имеющихся реализаций, помня, что верхняя граница у нас — 2²⁶, и скрестим пальцы:

std::cout << "testNaive:" << std::endl;
measure(&testNaive, 1 << 26);
std::cout << "testMillerRabinInteger:" << std::endl;
measure(&testMillerRabinInteger, 1 << 26);
std::cout << "testMillerRabinVectorized:" << std::endl;
measure(&testMillerRabinVectorized, 1 << 26);

testNaive:
33.9298 seconds
3957809 primes found
testMillerRabinInteger:
4.77004 seconds
3957809 primes found
testMillerRabinVectorized:
4.74518 seconds
3957809 primes found

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

Потрясающее совпадение! Также это не плохая новость — ручное вычисление остатка от деления, оказывается, не слишком и медленное. Остановлюсь ли я на этом? Конечно же, нет, мне нужно однозначно обогнать невекторизованный код, так что начнём тюнинг.

Суперскалярность

Начну с оптимизации, которая принесёт не самый большой профит, но зато она очень показательна и больше её вставить некуда.

Суперскалярность — это тоже параллелизация на уровне данных, но уже не совсем явная в коде, а неявная в процессоре. Ядро CPU способно выполнять несколько инструкций одновременно, при условии, что они независимы. Так что код, который обрабатывает независимые данные, способен работать быстрее кода, который обрабатывает зависимые данные.

Рассмотрим пример — функцию pow_mod для целых чисел, повторю её код:

int32_t pow_mod(int64_t n, int32_t power, int64_t m) {
    int64_t result = 1;
    while (power) {
        if (power & 1) result = (result * n) % m;
        n = (n * n) % m;
        power >>= 1;
    }
    return (int32_t) result;
}

В этом коде есть независимые вычисления над result и n, но вот беда — они находятся в разных скоупах, поэтому и компилятору, и процессору было бы сложно что-то с этим сделать. Что если скоупы объединить?

int32_t pow_mod(int64_t n, int32_t power, int64_t m) {
    int64_t result = 1;
    while (power) {
        if (power & 1) {
            result = (result * n) % m;
            n = (n * n) % m;
        } else {
            n = (n * n) % m;
        }
        power >>= 1;
    }
    return (int32_t) result;
}

Запустим тест и проверим. Для testMillerRabinInteger до оптимизации было 4.78585 секунд, после стало 4.25464 секунд, то есть заметно быстрее. Хотя, может, дело и не только в суперскалярности, может, бранч-предиктор стал тоже себя иначе вести, кто его знает. Главное, что код стал быстрее.

Так стоп, что я наделал, я же должен был оптимизировать векторизованный код, теперь всё стало только хуже! Быстро делаем то же самое для векторизованной версии pow_mod, потирая руки:

__m256d pow_mod(__m256d n, int32_t power, __m256d m) {
    __m256d result = _mm256_set1_pd(1);
    while (power) {
        if (power & 1) {
            result = mul_mod(result, n, m);
            n = mul_mod(n, n, m);
        } else {
            n = mul_mod(n, n, m);
        }
        power >>= 1;
    }
    return result;
}

И… никакой заметной разницы. Вообще.

Почему? Может, компилятор не заинлайнил вызов mul_mod? Вроде бы нет, если сделать ручной инлайн, то производительность не меняется. Как было примерно 4.7 секунд, так и осталось.

Может, компилятор не захотел переупорядочить инструкции в коде во время компиляции? Проверим, вручную сгруппировав независимые операции:

__m256d pow_mod(__m256d n, int32_t power, __m256d m) {
    __m256d result = _mm256_set1_pd(1);
    while (power) {
        if (power & 1) {
            __m256d c1 = _mm256_mul_pd(result, n);
            __m256d c2 = _mm256_mul_pd(n, n);
            __m256d tmp1 = _mm256_div_pd(c1, m);
            __m256d tmp2 = _mm256_div_pd(c2, m);
            tmp1 = _mm256_floor_pd(tmp1);
            tmp2 = _mm256_floor_pd(tmp2);
            tmp1 = _mm256_mul_pd(tmp1, m);
            tmp2 = _mm256_mul_pd(tmp2, m);
            result = _mm256_sub_pd(c1, tmp1);
            n = _mm256_sub_pd(c2, tmp2);
        } else {
            n = mul_mod(n, n, m);
        }
        power >>= 1;
    }
    return result;
}

Невероятно, теперь я получаю примерно 4.22 — 4.28 секунд, примерно как в суперскалярной версии невекторизованного алгоритма! А значит, что компилятор не всегда способен эффективно переупорядочить инструкции. Особенно если речь идёт об интринсиках, но это так, скорее предположение.

Обе версии алгоритма теперь работают немного быстрее, при этом среди них всё ещё нет явного лидера.

Деление и умножение

Что проще, умножать или делить? Очевидно, что умножать. Но в нашем алгоритме очень много делений, нужно сократить их количество. Для этого вспомним весьма банальное свойство:

Деление — это умножение на обратное. Если посмотреть на код внимательно, то станет видно, что делим мы всегда на один и тот же вектор, а именно n_pd (внутри дополнительных функций встречается под именем m). Вместо этого предлагаю ввести второе значение:

__m256d n_pd  = _mm256_set1_pd(n);       // m
__m256d n_inv = _mm256_set1_pd(1.0 / n); // m_inv

И каждый раз, когда встречается _mm256_div_pd(c, m), писать вместо этого
_mm256_mul_pd(c, m_inv). Интуиция говорит, что должно стать быстрее, но насколько?

Сделаем и запустим. До исправления — 4.27096 секунды, после — 3.05808. Разница почти 30%, впечатляет! Вот уж действительно, деление — это очень дорого.

А знаете, какой алгоритм тоже использует деление? testMillerRabinInteger. Может если и в нём сделать умножение, то и он станет быстрее?

double mod_double(double n, double m, double m_inv) {
    double tmp = n * m_inv;
    tmp = floor(tmp);
    return n - tmp * m;
}
double pow_mod_double(double n, int32_t power, double m, double m_inv) {
    double result = 1;
    while (power) {
        if (power & 1) result = mod_double(result * n, m, m_inv);
        n = mod_double(n * n, m, m_inv);
        power >>= 1;
    }
    return result;
}
bool testMillerRabinDouble(int32_t n) {
    if ((n & 1) == 0) return n == 2;
    if (n < 9) return n > 1;
    int32_t s = __builtin_ctz(n - 1);
    int32_t t = (n - 1) >> s;
    double m = n,
           m_inv = 1.0 / m;
    int32_t primes[3] = {2, 3, 5};
    for (int32_t a : primes) {
        double x = pow_mod_double(a, t, m, m_inv);
        if (x == 1.0) continue;
        for (int i = 1; x != n - 1; i++) {
            if (i == s) return false;
            x = mod_double(x * x, m, m_inv);
            if (x == 1.0) return false;
        }
    }
    switch (n) {
        case 25326001:    // Остальные убрал, потому что они больше чем 1<<26.
            return false;
        default:
            return true;
    }
}

Тестируем:

testMillerRabinInteger:
4.2803 seconds
3957809 primes found
testMillerRabinDouble:
4.00873 seconds
3957809 primes found

Вот это поворот, вышло-то быстрее и для невекторизованного кода! То есть, это насколько целочисленные * и % долгие, если их можно заменить вещественными *, *, floor, ещё раз * и -, и всё равно окажется эффективнее.

У меня есть гипотеза. При умножении 64-битных целых чисел процессор фактически возвращает нам 128-битное произведение, разбитое на 2 регистра (старшая и младшая половины), один из которых нам не нужен. Аналогично с делением: процессор в один регистр кладёт частное, а в другой — остаток. Он просто делает много ненужной нам побочной работы. Уверен, есть и другие причины.

Итого, имеет векторизованный код, который проверяет «все» числа примерно за 3 секунды, и невекторизованный код, который делает то же самое примерно за 4 секунды. Кажется, что это победа. Для 26-битных чисел.

Как умножать если double недостаточно

Что делать для чисел, у которых от 27 до 31 значащих бит? Можно ли векторизовать их проверку на простоту, не прибегая к AVX-512? Конечно можно, но сразу скажу, что на эффективность этого решения рассчитывать не стоит. Тем не менее, я его реализую, чтобы хотя-бы узнать, насколько плохо всё выйдет.

Вся задача сводится к тому, чтобы реализовать функцию mul_mod, которая может перемножать 31-битные числа по модулю другого 31-битного числа, т.е. перестать ограничиваться 26-ю битами, как в текущей реализации:

__m256d mul_mod(__m256d a, __m256d b, __m256d m, __m256d m_inv) {
    __m256d c = _mm256_mul_pd(a, b);
    __m256d tmp = _mm256_mul_pd(c, m_inv);
    tmp = _mm256_floor_pd(tmp);
    tmp = _mm256_mul_pd(tmp, m);
    return _mm256_sub_pd(c, tmp);
}

Перед тем, как продолжить, я хочу немного отвлечься, вспомнив одну из своих любимых подзадач в спортивном программировании. Она здесь важна, правда:

Даны 2 числа a и b типа int64_t, нужно найти их произведение по модулю 10¹². Желательно эффективно.

Всем желающим предлагаю отвлечься и подумать — как бы вы написали подобный алгоритм? На всякий случай напомню, что верхняя граница знаковых 64-битных чисел равна примерно 9*10¹⁸, этот факт легко забыть.

Я бы решал следующим образом. Без ограничения общности допустим, что и a, и b меньше 10¹² (и неотрицательные). Если это не так, то вместо них можно взять соответствующие остатки от деления. В таком случае значение b всегда можно представить в виде
b = b1 * 1000000 + b2, где b1 < 1000000 и b2 < 1000000.

Чем хорош миллион, так это тем, что при перемножении числа <10¹² и числа <10⁶ мы получаем число <10¹⁸, то есть помещающееся в знаковое 64-битное. Такие произведения можно делать в коде без всяких опасений, главное, правильным образом преобразовать формулу для a * b:

В этой формуле ни одно из произведений не переполняет int64_t, а значит она годится для реализации в коде, и потребует это всего лишь нескольких строк.

Какое отношение это имеет к решаемой задаче? Прямое. Нам аналогично нужно перемножить два 32-битных числа, но для вычисления произведения есть всего-лишь 53 бита. И я предлагаю разбить один из множителей (b) на пару b_hi и b_lo — старшие и младшие 16 бит числа, если представлять его его в виде int32_t. А вместо миллиона тогда будет константа 1 << 16. В этом случае каждое произведение будет не более, чем 48-битным, то есть без потерь может быть вычислено с помощью произведения в double.

Полноценная векторизация

Введём вспомогательную функцию mod, тело которой нам уже должно быть знакомо:

__m256d mod(__m256d a, __m256d m, __m256d m_inv) {
    __m256d tmp = _mm256_mul_pd(a, m_inv);
    tmp = _mm256_floor_pd(tmp);
    tmp = _mm256_mul_pd(tmp, m);
    return _mm256_sub_pd(a, tmp);
}

Здесь всё то же самое, что раньше было в mul_mod, кроме собственно произведения. Теперь задача простая — как раз написать mul_mod, используя ранее выведенную формулу.

Смотрите внимательно, надеюсь не запутаетесь:

// Маска для извлечения 2-х младших байт для 32-битных целых.
const __m128i MASK = _mm_set1_epi32((1 << 16) - 1);
// Вектор, который содержит значения "2 в 16-й степени".
const __m256d K = _mm256_set1_pd(1 << 16);
__m256d mul_mod(__m256d a, __m256d b, __m256d m, __m256d m_inv) {
    // Конвертируем вектор [double] в вектор [int32_t].
    __m128i b_epi32 = _mm256_cvtpd_epi32(b);
    // Извлекаем старшие 2 байта через сдвиг вправо на 16 бит.
    __m128i b_epi32_hi = _mm_srli_epi32(b_epi32, 16);
    // Извлекаем младшие 2 байта через конъюнкцию с маской.
    __m128i b_epi32_lo = _mm_and_si128(b_epi32, MASK);
    // Конвертируем вектора [int32_t] обратно в [double].
    __m256d b_hi = _mm256_cvtepi32_pd(b_epi32_hi);
    __m256d b_lo = _mm256_cvtepi32_pd(b_epi32_lo);
    // tmp1 = ((a * b_hi) % m) * K;
    __m256d tmp1 = _mm256_mul_pd(a, b_hi);
    tmp1 = mod(tmp1, m, m_inv);
    tmp1 = _mm256_mul_pd(tmp1, K);
    // tmp2 = a * b_lo;
    __m256d tmp2 = _mm256_mul_pd(a, b_lo);
    // return (tmp1 + tmp2) % m;
    tmp2 = _mm256_add_pd(tmp1, tmp2);
    return mod(tmp2, m, m_inv);
}

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

Время финального теста. На этот раз я выставлю верхнюю границу проверяемого интервала в 1u << 31, чтобы проверить вообще все 31-битные целые. Вот сколько времени это заняло:

testMillerRabinInteger:
160.792 seconds
105097565 primes found
testMillerRabinVectorized:
408.16 seconds
105097565 primes found

В 2.5 раза дольше невекторизованного целочисленного алгоритма. Довольно таки позорно, но хотя-бы посчитанное количество простых чисел совпало, а значит код скорее всего верный.

Выводы

Если очень нужно, то из ручной векторизации кода можно выжать более высокую производительность. Но шансы этого становятся тем ниже, чем больше количество целочисленной арифметики в вашем коде. Всё-таки векторизация рассчитана, в первую очередь, либо на целочисленную агрегацию 32-битных чисел, либо на арифметику с плавающей точкой, и использование её не совсем по назначению (как делаю я) приведёт скорее к страданиям.

Также интересным оказалось то, насколько оператор % тормозной. То есть я и так знал, что он медленный, но не осознавал масштабов. The more you know.

«Поставщики будут отрабатывать реалистичный сценарий реагирования на угрозы».

Космические силы США объявили в четверг о сотрудничестве с двумя компаниями, Rocket Lab и True Anomaly, в рамках первой в своём роде миссии, призванной продемонстрировать, как военные могут противостоять «орбитальной агрессии».

В ходе этой миссии космический аппарат, созданный и запущенный Rocket Lab, будет преследовать другой спутник, созданный True Anomaly, стартапом из Колорадо. «Поставщики будут отрабатывать реалистичный сценарий под названием «Victus Haze», подразумевающий реагирование на угрозы в космическом орбитальном пространстве», — говорится в заявлении Командования космических систем Космических сил.

Этот сценарий может включать в себя выполнение спутником манёвров приближения к американскому космическому аппарату, или выполнение спутником других необычных или неожиданных действий. В таком случае Космические силы хотят иметь возможность отреагировать, чтобы либо удержать противника от действий, либо защитить американский спутник от нападения.

Поднимемся, чтобы взглянуть

«Когда другая страна выводит в космос объект, а мы не совсем понимаем, что это за объект, не знаем его намерений, не знаем его возможностей, нам нужна возможность подняться туда и выяснить, что это за штука», — сказал генерал Майкл Гетлейн, заместитель начальника Космических сил по космическим операциям.

Именно это Космические силы хотят продемонстрировать с помощью «Victus Haze». Для этой миссии космический аппарат True Anomaly будет запущен первым, выдавая себя за спутник потенциального противника, например Китая или России. В Rocket Lab будет находиться в режиме ожидания спутник, который поднимется и проверит космический аппарат True Anomaly, и запустит его, когда Космические силы дадут команду на запуск.

«Довольно интересное состязание», — говорит Эвен Роджерс, соучредитель и генеральный директор True Anomaly.

Затем, если всё пойдёт по плану, два космических аппарата поменяются ролями, и спутник «Jackal» компании True Anomaly будет активно маневрировать вокруг спутника Rocket Lab. По данным Space Force, True Anomaly и Rocket Lab предоставят свои космические аппараты не позднее осени 2025 года.

«Если ближайший конкурент совершает определённое действие, мы должны иметь в своём арсенале возможность совершить ответный манёвр, будь то демонстрация силы или осведомлённость о космическом пространстве, или понимание характеристик окружающей среды – понимание того, что происходит?» сказал Гетлейн.

«Victus Haze» — следующий в серии военных миссий, посвящённых проверке возможностей тактически оперативного использования космического пространства (TacRS). В ходе этих работ Космические силы и их коммерческие партнёры продемонстрировали, как они могут сократить время подготовки и запуска спутника.

В прошлом году Космические силы в сотрудничестве с компаниями Firefly Aerospace и Millennium Space Systems осуществили миссию «Victus Nox». Спутник «Victus Nox» был создан и испытан менее чем за год, а затем подготовлен к запуску менее чем за 60 часов. Компания Firefly успешно запустила космический аппарат на своей ракете Alpha через 27 часов после получения приказа на запуск от Космических сил. Это замечательное достижение в отрасли, где на создание спутников уходят годы, а кампании по запуску обычно длятся недели или месяцы.

«У нас больше нет такой роскоши, как возможность ждать годы, 10 или 15 лет, чтобы обеспечить себе некоторые из этих возможностей», — сказал Гетлейн в ходе дискуссии, состоявшейся в январе в Центре стратегических и международных исследований. «Тактически значимые сроки — это вопрос недель, дней или даже часов».

««Victus Haze» — это продолжение разрушения этих парадигм и демонстрация того, как мы можем быстро обеспечить себе осведомлённость о космической области и реагировать на угрозу в режиме реального времени», — сказал Гетлейн.

Миссия «Victus Haze» сложнее, чем «Victus Nox», в ней участвуют два основных подрядчика, два космических аппарата и два запуска ракет с разных космодромов, и всё это происходит в сжатые сроки, «чтобы демонстрация была как можно более реалистичной», сообщил Ars представитель Космических сил.

«Эта демонстрация в конечном итоге подготовит Космические силы США к предоставлению боевым командованиям будущих сил для проведения быстрых операций в ответ на агрессию противника на орбите», — говорится в заявлении Командования космических систем.

Вера в коммерческий космос

«Это действительно значительная оперативная демонстрация, которая действительно расширяет технологические возможности и демонстрирует веру в промышленную базу США», — сказал Роджерс.

«По сути, речь идёт о том, чтобы впервые охарактеризовать неизвестные возможности на низкой околоземной орбите», — сказал Роджерс в интервью Ars. «Есть целый ряд проблем, которые возникают в связи с этим: как отслеживать манёвры объекта на низкой околоземной орбите при ограниченных возможностях контроля космического пространства, каким будет правильный баланс между автономностью и взаимодействия с человеком».

Первые два спутника «Jackal» компании True Anomaly были запущены в рамках программы SpaceX rideshare в прошлом месяце, но через несколько недель компания объявила, что оба спутника не смогут завершить запланированную демонстрацию рандеву. Это было бы предвестником того типа активности, которую True Anomaly и Rocket Lab продемонстрируют на «Victus Haze».

По словам Роджерса, его компания работает ещё над двумя демонстрационными полётами, которые состоятся до «Victus Haze».

Военное подразделение оборонных инноваций США выделило Rocket Lab 32 миллиона долларов на свою часть миссии «Victus Haze». Контракт True Anomaly с SpaceWERX, инновационным подразделением Космических сил, оценивается в 30 миллионов долларов. True Anomaly вложит 30 миллионов долларов частного капитала в оплату миссии, в результате чего общая стоимость «Victus Haze» составит около 92 миллионов долларов. Space Safari, подразделение Командования космических систем, курирует весь проект.

«Мы видим прекрасную возможность использовать инновации коммерческой космической промышленности для противодействия Китаю как главной угрозе для Америки», — сказал полковник Брайон Макклейн, руководитель программы командования космических систем по осведомлённости о космическом пространстве и боевой мощи. «Соединённые Штаты обладают самой инновационной космической промышленностью в мире. «Victus Haze» продемонстрирует в оперативно реалистичных условиях нашу способность реагировать на безответственное поведение на орбите».

«После завершения этапа создания миссия перейдёт к нескольким последовательным этапам, включающим в себя фазы горячего резерва, активации, оповещения и запуска», — заявили представители Космических сил. «Хотя это скоординированная демонстрация, каждому поставщику будут предоставлены уникальные профили запуска и миссии».

Спутник «Jackal» компании True Anomaly, размером почти с холодильник, будет запущен в рамках «быстрой поездки» с космодрома на мысе Канаверал во Флориде или с базы космических сил Ванденберг в Калифорнии, сообщает командование Space Systems. Скорее всего, это будет запуск на борту ракеты SpaceX Falcon 9. Запуск по программе rideshare сопряжён с другими проблемами, чем запуск на специальной ракете, как это было в прошлом году с миссией «Victus Nox».

True Anomaly утверждает, что сможет достать свой спутник из хранилища и интегрировать его с ракетой за 12-84 часа, в зависимости от частоты полётов поставщика услуг по запуску. После запуска «Jackal» компании True Anomaly Космические силы дадут Rocket Lab 24-часовой запрос на запуск своего спутника, схожего по размерам с космическим аппаратом True Anomaly, на ракете Electron из Новой Зеландии или из Вирджинии. Запуск Rocket Lab должен быть точно рассчитан по времени, чтобы его спутник успел сблизиться с космическим аппаратом True Anomaly на орбите.

««Victus Haze» опирается на проверенный опыт Rocket Lab в области разработки решений для запуска и космических аппаратов, которые позволяют осуществлять передовые миссии в ускоренные сроки», — сказал в своём заявлении Питер Бек, основатель и генеральный директор Rocket Lab. «Возможность спроектировать, построить, запустить и эксплуатировать космический аппарат в рамках одной команды — редкое явление, которое обеспечит беспрецедентную скорость и ценность для нации».

Добиться такого сокращения времени запуска спутника было нелегко. Военная программа Operationally Responsive Space (ORS) ставила перед собой аналогичные цели в 2000-х и 2010-х годах, но она была направлена скорее на пополнение или замену потенциала, а не на реагирование на угрозы в космосе, говорит Гетлейн.

С тех пор коммерческие компании разработали собственный современный потенциал. Космическим силам доступны более совершённые технологии по более низкой цене. «В то время это было слишком дорого», — сказал Гетлейн.

Теперь более важной задачей является изменение культуры Космических сил и их коммерческих партнёров. Такие вещи, как согласование с регулирующими органами, оформление документов по безопасности и разрешение на использование воздушного пространства, должны проходить быстрее.

«Тактическое реагирование в космосе зависит не от аппаратуры», — говорит Гетлейн. «Дело не в спутнике, не в датчике, не в ракете. Дело в мышлении. Дело в культуре».