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

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

Предлагаю прочитать Hacker's Delight . Он описывает очень быстрые алгоритмы остатка для постоянных делителей. Они почти наверняка превзойдут общий алгоритм.

Обновление: вот пример кода ... Его, вероятно, можно переработать, чтобы избежать временного длинного long.

unsigned mod25(unsigned n)
{
    unsigned reciprocal = 1374389535; // 2^35 / 25
    unsigned div25 = ((unsigned long long)n * reciprocal) >> 35;
    return n - div25 * 25;
}

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

Как насчет:

int y = 0, x = (x & 0x7f); 
while (x > 25) { x -= 25; y++; }

Обновление: это в корне неверно :) Но идея есть.

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

int a = x % 25;

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

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

Скажем так - I '

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

РЕДАКТИРОВАТЬ: Вот алгоритм, который, по крайней мере, может дать некоторые идеи:

256 = 6 (mod 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-битным числом соответственно. Один из этих размеров может быть достаточно мал, чтобы составить таблицу поиска.

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

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

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 жестко запрограммированной константой.)

Возможно, не самый быстрый, но достаточно эффективный. У меня нет времени на тестирование, но я использую поисковую таблицу (степени 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;
}

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

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

О, мое <божество выбора>. Я не могу поверить в некоторые из этих ответов.

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

20 % 25

это легко и быстро с использованием повторного вычитания, но:

65535 % 25

будет ужасно медленным, 600+ итераций. Это в среднем 300 итераций для 16-битных чисел. Что касается 32-битного числа, ну просто туда даже не ходи.

Самый быстрый способ сделать это - использовать длинное деление. См. Ответ Ники.

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

Лучший способ ускорить это - вообще не использовать модуль.

Если ваш компилятор C нацелен на ЦП без инструкции деления, вы можете изменить свой код следующим образом:

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

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

Это должно заставить ваш код работать примерно в четыре раза быстрее (при условии, что 4 * b не выходит за пределы диапазона ваших целых чисел). Вы даже можете вставить больше циклов (скажем, 8 * b ) перед 4 * b для еще большей скорости.

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

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

int mod25 (int a) {                // a has maximum value of 2^15-1 = 32767
    while (a >= 15625) a-= 15625;  // at most 2 times.
    while (a >= 625) a-= 625;      // at most 24 times.
    while (a >= 25) a-= 25;        // at most 24 times.
    return a;
}

Выполняя тест, я обнаружил, что вам нужно сделать 10 миллионов итераций, прежде чем заметный разница появляется между этим кодом по модулю и использованием оператора % (2 секунды против 0 секунд). До этого момента они оба были 0 секунд, хотя это выполнялось на быстрой машине (лучше для mod25 ) и с инструкцией div (лучше для % оператор), поэтому вам нужно будет протестировать его на собственном оборудовании.

Это примерно так быстро, как вы, вероятно, получите, не делая ваш код нечитаемым (хотя даже это не должно останавливать вы, если хотите, добавить много комментариев, объясняющих, как это работает).

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

int mod (int n, int d) {
    /* dx is the adjusted denom, don't let it overflow though. */
    int dx = d;
    while (((dx << 1) >>1) == dx)
        dx <<= 1;

    /* This loop processes the dx values until they get too small. */
    while (dx >= d) {
        /* This loop subtracts the large dx value. */
        while (n >= dx)
            n -= dx;
        dx >>= 1;
    }
    return n;
}

Это фактически работает на уровне оптимизированной версии mod25 выше, в то время как предлагая более общее решение.

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

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

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

Вот лучшее, что я мог придумать:

int mod25(int x)
{
    while((x = (x & 31) + 7 * (x >> 5)) >= 25)
        x -= 25;

    return x;
}

Это приблизительно x% 25 с x% 32 + 7 * (x / 32) . Значение будет превышать значение, кратное 25 , что позволяет использовать рекурсию.

Производительность кажется адекватной: значение x = 2147483647 (также известное как INT_MAX ]) требуется 11 итераций.

Проблема с вашим циклом в том, что он O (n) - он будет очень медленным для больших значений r. Я бы предложил что-то вроде этого:

for (int s = MAX_SHIFT; s>=0; s--)
  if (r > (b<<s)) r -= (b<<s);

Но я сомневаюсь, что ваш компилятор делает что-то намного более затратное, чем это.

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

Вот другое решение, которое я придумал:

int mod25(int x){
  /* 25 * (all powers of 2 <= INT_MAX), descending */
  if (x >= 1677721600) x -= 1677721600;
  if (x >=  838860800) x -=  838860800;
  if (x >=  419430400) x -=  419430400;
  if (x >=  209715200) x -=  209715200;
  if (x >=  104857600) x -=  104857600;
  if (x >=   52428800) x -=   52428800;
  if (x >=   26214400) x -=   26214400;
  if (x >=   13107200) x -=   13107200;
  if (x >=    6553600) x -=    6553600;
  if (x >=    3276800) x -=    3276800;
  if (x >=    1638400) x -=    1638400;
  if (x >=     819200) x -=     819200;
  if (x >=     409600) x -=     409600;
  if (x >=     204800) x -=     204800;
  if (x >=     102400) x -=     102400;
  if (x >=      51200) x -=      51200;
  if (x >=      25600) x -=      25600;
  if (x >=      12800) x -=      12800;
  if (x >=       6400) x -=       6400;
  if (x >=       3200) x -=       3200;
  if (x >=       1600) x -=       1600;
  if (x >=        800) x -=        800;
  if (x >=        400) x -=        400;
  if (x >=        200) x -=        200;
  if (x >=        100) x -=        100;
  if (x >=         50) x -=         50;
  if (x >=         25) x -=         25;
  return x;
}

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

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

Приведенный выше код действительно является развернутой версией этого:

int mod25(int x){
  int divisor;
  for(int divisor = 1677721600; divisor >= 25; divisor >>= 1) {
    if (x >= divisor) x -= divisor;
  }
  return x;
}

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

Вот как это работает: каждое неотрицательное целое число x может быть выражено как (n * 25) + k, где n - неотрицательное целое число, а k - целое число от 0 до 24. k также является желаемым результатом, поэтому если бы мы могли вычислить x - (n * 25), мы бы получили наш ответ. Однако мы хотим иметь возможность делать это, не зная заранее n.

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

У Аарона Сконнарда из PluralSight есть куча отличных маленьких скринкастов на Channel9, и это, вероятно, лучшее вступление, которое я когда-либо видел. Вам, вероятно, будет хорошо, если вы сначала получите некоторый опыт WCF мир SOAP воспримет это проще.

http://channel9.msdn.com/shows/Endpoint/endpointtv-Screencast-Building-RESTful-Services-with-WCF/

Также вставьте это в Bing

спокойный сайт: msdn.com

ОБНОВЛЕНИЕ

Этот ответ все еще получает голоса, поэтому я подумал, что было бы неплохо обновить его, добавив последние изменения. По сути, команда WCF объединила усилия с сообществом ASP.NET MVC, чтобы перенести REST в стек Microsoft через веб-API ASP.NET MVC 4, поэтому я полагаю, что с 2012 года материал WCF REST разрабатываться не будет.

http : //wcf.codeplex.com/wikipage? title = WCF% 20Web% 20API% 20is% 20now% 20ASP. В более «разговорном стиле» делать что-то с вещью, а не с самой вещью.

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

s = 112 / 2 = 56, r = 100 - 56 = 44
s = 56 / 2 = 28, r = 44 - 28 = 16
s = 28 / 2 = 14, r = 16 - 14 = 2

s = 112 / 2 = 56, r = 100 - 56 = 44
s = 56 / 2 = 28, r = 44 - 28 = 16
s = 28 / 2 = 14, r = 16 - 14 = 2

s = 112 / 2 = 56, r = 100 - 56 = 44
s = 56 / 2 = 28, r = 44 - 28 = 16
s = 28 / 2 = 14, r = 16 - 14 = 2

Вот идея

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;
}