Г-н Фаршеклоакин (spamsink) wrote,
Г-н Фаршеклоакин
spamsink

Category:

Занимательная прикладная математика

Как известно™, в современных компьютерах операция целочисленного деления сильно медленнее, чем операция умножения, поэтому деление на известную константу K, отличную от степени двойки, современными компиляторами делается с помощью умножения на "обратную" величину (грубо говоря, на некоторое 2N / K), c коррекцией сложением-вычитанием и выделением нужного количества разрядов. Например:
Исходный кодРезультат
unsigned foo(unsigned a) { return a / 12345; } mov eax, edi imul rax, rax, 1405214493 shr rax, 32 sub edi, eax shr edi add eax, edi shr eax, 13

Более того, операция деления настолько медленная, что для вычисления остатка от деления на константу K оказывается быстрее делить описанным выше способом на K, умножать результат на K, и вычитать это дело из делимого, чем просто выполнять команду деления, которая вычисляет и частное, и остаток.
(Если попросить компилятор оптимизировать не только по скорости, но и по размеру кода, то кое-кого оказывается возможно уговорить всё же использовать команду деления.)
Исходный кодРезультатС оптимизацией по размеру кода
unsigned foo(unsigned a) { return a % 12345; } mov eax, edi mov ecx, edi imul rcx, rcx, 1405214493 shr rcx, 32 mov edx, edi sub edx, ecx shr edx add edx, ecx shr edx, 13 imul ecx, edx, 12345 sub eax, ecx mov ecx, 12345 mov eax, edi xor edx, edx div ecx mov eax, edx

Логично задаться вопросом: если нам не нужно знать точное значение остатков, а нужно только сравнивать целые неотрицательные (без знака) числа по модулю K, можно ли ускорить процесс? Ну да, очевидно, что (a % K == b % K) — это то же самое, что и (max(a,b) - min(a,b)) % K == 0, и всё?

Оказывается, не всё. Для упрощения дальнейшего объяснения вспомним, как оптимизируется проверка, что остаток от деления числа на 2M равен нулю: для этого мы смотрим, равны ли нулю все младшие M двоичных разрядов числа.

Рассмотрим гипотетическую ситуацию: у нас нет команды "логическое И", чтобы выделить эти M младших разрядов. Тогда мы можем пойти на хитрость: мы циклически сдвинем число вправо на M разрядов и проверим, что у получившегося числа старшие M разрядов равны нулю. Для этого не нужно ниоткуда ничего выделять, потому что достаточно проверить, что сдвинутое число меньше, чем 2N-M, где N - полная разрядность числа. Попробуем найти обобщённый аналог этого способа.

Нам нужно придумать функцию, которая бы все числа от 0 до 2N-1, кратные K, сколько их там будет, переводила бы в компактный диапазон от 0 до это самое количество-1, а остальные - в произвольные числа за пределами этого диапазона. Сначала рассмотрим для удобства только нечетные K и упростим задачу: пусть нам обещали, что на входе будут только числа от 0 до K включительно, т.е. что утвердительный ответ нам нужно давать только в двух случаях: для 0 и для K. Тогда мы хотим найти дешёвую функцию, которая 0 переводит в 0, а K - в 1 (или наоборот, если эту не сможем).

На первый взгляд, это напоминает деление на K (или вышеупомянутое умножение на "обратное" к K), но нам надо, чтобы никакие другие все остальные числа между 0 и K ни в 0, ни в 1 не переходили. Для этого найдем число, которое при честном машинном умножении N-разрядных чисел переводит K в 1.

Обратим внимание, что при возведении нечетного числа K в квадрат, в двоичном представлении результата количество нулей перед самой младшей единицей больше, чем у самого числа K. Действительно, если K = 2k+1, то K2 = 4k2+4k+1 — что-то, умноженное на 4 (c двумя младшими нулями помимо тех, которые уже были в представлении k) плюс 1, т. е. во втором справа разряде гарантирован дополнительный 0, и т.д.

Таким образом, при повторном возведении N-битного нечетного числа в квадрат мы рано или поздно получим 1, а возведя K в степень на 1 меньше, т.е. перемножив К и все промежуточные результаты, мы получим число L, которое, будучи умножено на К, даст 1. Нетрудно показать, что если на L умножать последующие кратные K, то будут получаться числа 2, 3 и т.п., т.е. ровно то, что надо.

Таким образом,
Исходный кодСтарый результатНовый результат
bool foo(unsigned a) { return a % 12345 == 0; } mov eax, edi mov edx, 1405214493 mul edx mov eax, edi sub eax, edx shr eax add edx, eax shr edx, 13 imul edx, edx, 12345 cmp edi, edx sete al imul edi, edi, 1440005641 cmp edi, 347911 setbe al


Для чётных чисел вида 2M*K объединим два способа: будем проверять, что число кратно K, умножением на обратное по модулю, а что оно еще и кратно 2M - циклическим сдвигом. И понятно, что все числа, делящиеся на K с данным остатком R будут превращаться в компактный диапазон (возможно, с перехлёстом через ноль), поэтому проверка на равенство по модулю не нулю, а R, делается с минимальными модификациями.
Так, например,
Исходный кодНовый результат
bool foo(unsigned a) { return a % 1000 == 123; } imul edi, edi, 652835029 add edi, 1305670057 ror edi, 3 cmp edi, 4294967 setbe al


Действительно, "нечетная часть" у 1000 - 125, 652835029*125 = 0x1300000001, т.е. 1 mod 232,
652835029*123 + 1305670057 = 0 mod 232, 3 - количество младших нулей в двоичном представлении 1000, а 4294967+1 - количество представимых чисел, равных 123 по модулю 1000, потому что 232 = 4294967296, где 296 > 123.

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

This entry was originally posted at https://spamsink.dreamwidth.org/1149116.html. Please comment there using OpenID.
Tags: tidbits
Subscribe

  • По следам наших выступлений, семантическое

    Рассмотрим формулировки задач: 1. Даны буквы В, Е, Ч, Н, О, С, Т, Ь. Составьте из них два разных слова. 2. Даны буквы В, Е, Ч, Н, О, С, Т, Ь.…

  • Простенькая задачка

    Бывший сослуживец-американец, ныне живущий в Неваде, на прошлой неделе посещал наши края, и на нашей с ним встрече-прогулке задал задачку: Даны 10…

  • Просто так, этимологическое

    Вдруг пришло в голову, что Empire State Building более последовательно было бы называть Empire State Edifice. Гугл находит мне 657 вхождений,…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 9 comments