Эффективный (циклично) алгоритм для вычисления по модулю 25?

Question

У меня есть код, в котором я вычисляю x% 25. x всегда принимает положительное значение, но его динамический диапазон велик.

Я обнаружил, что этот конкретный фрагмент кода вычисления x% 25 занимает большие циклы. Мне нужно оптимизировать его.

Предварительно вычисленная таблица поиска исключена из-за возможного большого объема памяти таблицы.

В качестве второго подхода я кодировал фрагмент ниже (код C) -

mod(a, b)
{   
    int r = a;  
    while(r >= b)
    {      
        r = r - b;
    }   
    return r;
}

1.) Как я могу оптимизировать этот код для циклов (сжать его до максимума)?

2.) Есть ли какой-то совершенно другой оптимизированный способ достижения x% 25 (я знаю, что это не обычная операция, но все же, в поисках умных входов, которые люди могли бы использовать в своем опыте, которые могли бы мне помочь.) *

Спасибо.

-AD

EDIT:

Я думаю, что при использовании собственного оператора по модулю% в C внутренне используется операция деления (/), которая является дорогостоящей на процессоре, который я использую. (Нет команды div). следовательно, пытаясь понять, может ли пользовательская реализация превзойти внутренние вычисления, используя оператор%.

-AD

Answer 1

int mod25(int x) {
  static int divisors[] = {2147483625, 244140625, 9765625, 390625, 15625, 625, 25};
  int i;
  for (i = 0; i < sizeof(divisors)/sizeof(int); i++) {
    int divisor = divisors[i];
    while (x >= divisor) {
      x -= divisor;
    }
  }
  return x;
}

Как это работает: мы хотим уменьшить x на большое число, кратное 25, чтобы уменьшить значение как можно быстрее. Когда делитель слишком большой, мы переключаемся на меньшее, кратное 25. Если делитель уже опустился до 25, то мы закончили.

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

• они спускаются
• они все кратны 25
• последнее значение 25

В приведенном выше коде я использовал наибольшее 32-разрядное число со знаком, равное 25, плюс степень 25, что кажется разумным, хотя я должен признать, что не уверен, что это оптимально.

(Кстати: если ваш компилятор не выполняет постоянное свертывание - что было бы очень удивительным - тогда вы можете заменить верхний предел i жестко-закодированной константой .)

Answer 2

Если вы знаете, что b будет степенью 2, вы можете использовать побитовый AND вместо оператора по модулю. Однако страница в Википедии по модулю , похоже, указывает на то, что любой компилятор C заметит это и все равно оптимизирует модуль.

Answer 3

Возможно, не самый быстрый, но достаточно эффективный. У меня нет времени на тестирование, но я использую справочную таблицу (степени 2) * 25 до максимального диапазона / 2. Затем сделайте цикл. Например. диапазон до 3199 требует 7 итераций.

static int pow[] = {25, 50, 100, 200, 400, 800, 1600};

int mod25(int x)
{    
    int i = sizeof pow /sizeof pow[0];

    while (i--)
    {
        if (x >= pow[i])
            x -= pow[i];    
    }    
    return x;
}

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

Answer 4

Если вам не нравится % оператор:

int mod(int a, int b) {
    int integral = a / b;
    return a - (b*integral);
}

Answer 5

Почему вы не можете просто использовать оператор %? Если это код C, а числа обычные "нативные" int: s, то это, безусловно, самый быстрый способ.

Answer 6

Вот идея

static int table0[256];
static int table1[256];
static int table2[256];
static int table3[256];

// ran just once to initialize the tables
void initialMod25Tables() {
    for (int i = 0; i < 256; ++i) {
        table0[i] = i % 25;
    }
    for (int i = 0; i < 256; ++i) {
        table1[i] = (i << 8) % 25;
    }
    for (int i = 0; i < 256; ++i) {
        table2[i] = (i << 16) % 25;
    }
    for (int i = 0; i < 256; ++i) {
        table3[i] = (i << 24) % 25;
    }
}

int mod25(int x) {
    int y = table0[x & 0xFF];
    x >>= 8;
    y += table1[x & 0xFF];
    x >>= 8;
    y += table2[x & 0xFF];
    x >>= 8;
    y += table3[x & 0xFF];
    y = table0[y];
    return y;
}

Answer 7

Есть ли причина, по которой вы не можете использовать встроенный оператор модуля C?

int a = x % 25;

После вашего редактирования;

Если ваш rpocessor не имеет встроенной поддержки по модулю, я все равно использовал бы оператор% по той простой причине, что ваш компилятор будет знать, что у рассматриваемого процессора нет нативной функции%, и, скорее всего, будет генерировать asm-код для оптимальной работы. подражать.

Скажем так: я был бы восхищен, если бы вы могли придумать алгоритм genarl, который превосходит все, что компилятор производит при использовании встроенного оператора, независимо от конкретных случаев (таких как простое взятие 2 младших цифр для модуля 100 и т.д.)

Answer 8

Если вы храните свои числа в BCD или байтовом массиве цифр, это будет довольно просто. К сожалению, я понятия не имею, что еще вы делаете в своей программе с этими числами. Иногда стоит взглянуть на то, как вы представляете свои данные, а не просто отмахиваться от алгоритмов.

Answer 9

Я нахожу довольно странным, что операция x % 25 занимает так много времени (то есть, если вы используете встроенный оператор %). Большинство современных процессоров должны делать это в одной инструкции. Я бы искал другие причины, по которым этот код занимает так много времени.

EDIT: Вот алгоритм, который может хотя бы дать некоторые идеи:

256 = 6 (мод 25)

Это означает, что если мы напишем число x в виде байтов x3 x2 x1 x0, то получим x = 6^3*x3 + 6^2*x2 + 6*x1 + x0 (mod 25)

Это дает алгоритм для уменьшения размера x:

int x0 = x & 0xFF, x1 = (x>>8) & 0xFF, x2 = (x>>16) & 0xFF, x3 = (x>>24) & 0xFF;

int y = x4;
y = (y << 2) + (y << 1) + x3;
y = (y << 2) + (y << 1) + x2;
y = (y << 2) + (y << 1) + x1;
y = (y << 2) + (y << 1) + x0;

(здесь (y << 2) + (y << 1) = 4*y + 2*y = 6*y)

После этого y будет иметь тот же остаток, что и x mod 25. Повторение этого 1, 2 или 3 раза сделает y 17, 11 или 9-битным числом, соответственно. Один из этих размеров может быть достаточно мал, чтобы составить справочную таблицу.

Я СЕРЬЕЗНО сомневаюсь, что это будет быстрее, чем встроенный оператор %.

Answer 10

Если вы рассматриваете только число 25, вы можете использовать тот факт, что 25 делит целое число тогда и только тогда, когда последние две цифры целого числа равны 00, 25, 50 или 75. Таким образом, чтобы получить модуль по модулю, вы считаете последнее две цифры, а затем вычесть ближайшее из 00, 25, 50 или 75.