Математика, стоящая за оптимизацией модуля gcc9 + - PullRequest
Новая
       9

Математика, стоящая за оптимизацией модуля gcc9 +

0 голосов
/ 21 ноября 2018

Фон

Я играл с простыми числами в c, когда наткнулся на новую оптимизацию в стволе gcc (будет версия 9.x), которая оптимизирует сравнение модуля до 0в целое умножение и сравнение с использованием магических чисел.Другими словами x%prime==0 становится x*Magic_mul<=Magic_cmp

_Bool mod(unsigned x){return x % Constant == 0;}

mod:
  imul edi, edi, Magic_mul
  cmp edi, Magic_cmp
  setbe al

Подробно

На основе просмотра вывода asm он выполняет эти оптимизации для всех целых чисел (ну, простых чисел).по крайней мере) Я преобразовал их в шестнадцатеричное, чтобы помочь увидеть шаблоны, но это не сразу очевидно в данный момент. 

//32bit examples for _Bool mod_n(unsigned x){return x%n==0;};
//note: parameter is unsigned but it becomes a signed multiply
x%3==0;  // x*0xAAAAAAAB <= 0x55555555
x%5==0;  // x*0xCCCCCCCD <= 0x33333333
x%7==0;  // x*0xB6DB6DB7 <= 0x24924924
x%11==0; // x*0xBA2E8BA3 <= 0x1745D174
x%13==0; // x*0xC4EC4EC5 <= 0x13B13B13
x%17==0; // x*0xF0F0F0F1 <= 0x0F0F0F0F
x%19==0; // x*0x286BCA1B <= 0x0D79435E
x%23==0; // x*0xE9BD37A7 <= 0x0B21642C
x%29==0; // x*0x4F72C235 <= 0x08D3DCB0
x%31==0; // x*0xBDEF7BDF <= 0x08421084
x%37==0; // x*0x914C1BAD <= 0x06EB3E45
x%41==0; // x*0xC18F9C19 <= 0x063E7063
x%43==0; // x*0x2FA0BE83 <= 0x05F417D0
x%47==0; // x*0x677D46CF <= 0x0572620A
x%53==0; // x*0x8C13521D <= 0x04D4873E
x%59==0; // x*0xA08AD8F3 <= 0x0456C797
x%61==0; // x*0xC10C9715 <= 0x04325C53
x%67==0; // x*0x07A44C6B <= 0x03D22635
x%71==0; // x*0xE327A977 <= 0x039B0AD1
x%73==0; // x*0xC7E3F1F9 <= 0x0381C0E0
x%79==0; // x*0x613716AF <= 0x033D91D2
x%83==0; // x*0x2B2E43DB <= 0x03159721
x%89==0; // x*0xFA3F47E9 <= 0x02E05C0B
x%97==0; // x*0x5F02A3A1 <= 0x02A3A0FD
///...and even up to 64bit
x%4294967291==0; //x*0x70A3D70A33333333 <= 0x100000005

Я проверил восторг хакера "INTEGER DIVISION BY CONSTANTS" и этопохоже, что это может быть особый случай остатка при умножении и сдвиге вправо , но я не уверен.Существует форма на восторге хакера , которая вычисляет те же самые константы множителя, что выглядит многообещающе.Я предполагаю, что волшебная константа сравнения заменяет сдвиг и сравнивает с нулем, но у меня возникают проблемы с визуализацией дополнения 2s и является ли сдвиг арифметическим или логическим.

Вопрос

Есть ли какая-то математика за этим или числа были определены каким-то другим способом с использованием двоичного представления?

Последствия

Поскольку это просто целочисленное умножение и сравнение этогоможет значительно ускорить (или уменьшить объем памяти) проверку на простое использование векторных расширений / встроенных функций.Если бы математика могла быть расширена за пределы 64 бит, это могло бы значительно ускорить поиск больших простых чисел?

1 Ответ

0 голосов
/ 21 ноября 2018

Взять, к примеру, 3.

0xAB * 3 = 0x201, таким образом, по модулю 0x100, 0xAB равно 1/3 и, наоборот, 0xAB * 3 ≡ 1.

Any 8-битное целое число без знака n может быть представлено как n = 3 * k + r, r <3, а n не более 0x55 (десятичное 85, неотъемлемая часть 255/3). </p>

Итак, у нас есть варианты:

  1. r = 0 ⇒ n * 0xAB = 3k * 0xAB = k * (3 * 0xAB) ≡ k * 1 = k ≤ 0x55.

  2. r = 1 ⇒ n * 0xAB = 3k * 0xAB + 0xAB;поскольку 3k * 0xAB не более 0x55 (мод 0x100), добавление его в 0xAB не будет переполнено, поэтому 3k * 0xAB + 0xAB ≥ 0xAB> 0x55.

  3. r = 2 ⇒ n* 0xAB = 3k * 0xAB + 0x156 ≡ 3k * 0xAB + 0x56 ≥ 0x56> 0x55 (аналогично 2).

...