Умножение по модулю (в C)

В частности: у меня есть два целых числа без знака (a,b), и я хочу вычислить (a*b)%UINT_MAX (UINT_MAX определяется как максимальное целое число без знака). Как лучше всего это сделать?

Предыстория: мне нужно написать модуль для linux, который будет эмулировать геометрическую последовательность, чтение из нее даст мне следующий элемент (по модулю UINT_MAX), единственное решение, которое я нашел, это добавить текущий элемент к самому себе раз, пока добавление выполняется используя следующую логику: (которую я использую для арифметической последовательности)

for(int i=0; i<b; ++i){
  if(UINT_MAX - current_value > difference) {
    current_value += difference;
  } else {
    current_value = difference - (UINT_MAX - current_value);
  }

когда current_value = a в первой итерации (и обновляется на каждой итерации, а разность = a (всегда). Очевидно, это не разумное решение. Как разумный человек может этого добиться?

Спасибо!


c math multiplication modulo
person Gilgr    schedule 14.01.2012    source источник
comment
вам не разрешено использовать оператор модуля или 8-байтовые целые типы?   -  person davogotland    schedule 14.01.2012
comment
Очень простое глупое решение, где long long является более длинным типом, чем int. длинный длинный результат = ((длинный длинный)a) * ((длинный длинный)b) % ((длинный длинный)UINT_MAX);   -  person Joachim Isaksson    schedule 14.01.2012
comment
Тогда результат @JoachimIsaksson не должен быть длинным, верно?   -  person davogotland    schedule 14.01.2012
comment
Вы, вероятно, можете использовать китайскую теорему об остатках. См. эти вопросы Восстановить число из нескольких его остатков и Сумма и умножение по модулю   -  person ypercubeᵀᴹ    schedule 14.01.2012
comment
Я ищу решение, которое также будет работать для самого большого типа данных в системе, поэтому использование long long не подходит. @ypercube CRT в этом случае сложно использовать, так как UINT_MAX=(2^n)-1, не так ли?   -  person Gilgr    schedule 14.01.2012
comment
Выполнение арифметических вычислений по модулю 2^64-1 в 64 битах может быть проще, чем по модулю 2^32-1 в 32 битах: 2^64-1 = 3 x 5 x 17 x 257 x 641 x 65537 x 6700417   -  person ypercubeᵀᴹ    schedule 14.01.2012
comment
У старшего простого множителя 23 бита, меньше половины от 64. У старшего множителя 2^32-1 17 бит, всего на один больше половины от 32, и это все усложняет.   -  person ypercubeᵀᴹ    schedule 14.01.2012
comment
См. также это: Эффективная реализация VLSI по модулю 2 ^n+-1 Сложение и умножение   -  person ypercubeᵀᴹ    schedule 14.01.2012
comment
Если a=2^n, то XY mod(a-1) = ((XY mod a) + (XY div a)) mod (a-1)   -  person ypercubeᵀᴹ    schedule 14.01.2012

Ответы (2)


arrow_upward
2
arrow_downward

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

(unsigned int)(((unsigned long long)a * b) % UINT_MAX)

если int составляет 32 бита, а long long 64 (или больше). Если у вас нет более крупного шрифта, вы можете разбить множители на половину разрядности, умножить и уменьшить части, наконец, собрать его. Проиллюстрировано для 32-битного беззнакового здесь:

a_low = a & 0xFFFF;  // low 16 bits of a
a_high = a >> 16;    // high 16 bits of a, shifted in low half
b_low = b & 0xFFFF;
b_high = b >> 16;
/*
 * Now a = (a_high * 65536 + a_low), b = (b_high * 65536 + b_low)
 * Thus a*b = (a_high * b_high) * 65536 * 65536
 *          + (a_high * b_low + a_low * b_high) * 65536
 *          + a_low * b_low
 *
 * All products a_i * b_j are at most (65536 - 1) * (65536 - 1) = UINT_MAX - 2 * 65536 + 2
 * The high product reduces to
 * (a_high * b_high) * (UINT_MAX + 1) = (a_high * b_high)
 * The middle products are a bit trickier, but splitting again solves:
 * m1 = a_high * b_low;
 * m1_low = m1 & 0xFFFF;
 * m1_high = m1 >> 16;
 * Then m1 * 65536 = m1_high * (UINT_MAX + 1) + m1_low * 65536 = m1_high + m1_low * 65536
 * Similar for a_low * b_high
 * Finally, add the parts and take care of overflow
 */
m1 = a_high * b_low;
m2 = a_low * b_high;
m1_low = m1 & 0xFFFF;
m1_high = m1 >> 16;
m2_low = m2 & 0xFFFF;
m2_high = m2 >> 16;
result = a_high * b_high;
temp = result + ((m1_low << 16) | m1_high);
if (temp < result)    // overflow
{
    result = temp+1;
}
else
{
    result = temp;
}
if (result == UINT_MAX)
{
    result = 0;
}
// I'm too lazy to type out the rest, you get the gist, I suppose.

Конечно, если вам действительно нужно сокращение по модулю UINT_MAX + 1, как предполагает @Toad, то это именно то, что делает умножение unsigned int.

person Daniel Fischer    schedule 14.01.2012
comment
Сокращение unsigned long long mod MAX_INT можно упростить, применив уравнение (a*N+b)%(N-1) = (a + b)%(N-1). - person Raymond Chen; 14.01.2012
comment
Верно, но если a+b переполняется, приходится подстраиваться. И если доступен более крупный тип, преобразование вверх и вниз решает проблему без разделения продукта на старшие и младшие биты, так что это концептуально проще. - person Daniel Fischer; 14.01.2012
comment
Согласитесь, что это концептуально проще, но трюк позволяет избежать дорогостоящего разделения на двойные слова. - person Raymond Chen; 14.01.2012
comment
Конечно. Хотя я не уверен, что деление будет медленнее, чем сдвиг, добавление и проверка переполнения на современных процессорах. Но поскольку вы знаете о таких вещах гораздо больше, чем я, я поверю вам на слово. - person Daniel Fischer; 14.01.2012
comment
Здесь нет внутренних знаний. Но большинство 32-разрядных процессоров не имеют собственного 64 деления на 32, что дает 64 инструкции. (Они могут иметь 64 деления от 32 до 32.) Случай 64 деления от 32 до 64 обычно реализуется в программном обеспечении. - person Raymond Chen; 14.01.2012
comment
Но, надеюсь, инженерами, которые лучше разбираются в алгоритмах и конкретном оборудовании, чем Joe Random User. Поскольку это не слишком экзотическая инструкция, я ожидаю, что она будет достаточно хорошо оптимизирована. Так что я бы не стал спорить навскидку, что его можно победить, используя особую структуру задачи. Но и я бы не стал ставить против этого. - person Daniel Fischer; 15.01.2012
comment
Это решение не будет работать, если компилятор не совместим с C99 или если он (частично), но long long имеет ширину как unsigned int. - person SquareRootOfTwentyThree; 16.09.2012
comment
@SquareRootOfTwentyThree Для короткого и быстрого пути с актерским составом я специально сказал, если. Долгий и утомительный способ работает - с небольшими изменениями - для всех значений ширины unsigned int (если ширина нечетная, изменение должно быть немного менее незначительным). Он использует только свойства целых чисел без знака, гарантированные начиная с C89. Итак, можете ли вы уточнить, каким образом это решение не будет работать...? - person Daniel Fischer; 16.09.2012

arrow_upward
0
arrow_downward

РЕДАКТИРОВАТЬ: Как указано в комментариях... этот ответ относится к модулю MAX_INT+1. Я оставлю его здесь для дальнейшего использования.

Это намного проще:

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

см. пример здесь

 #include <stdio.h>

 void main()
 {
     unsigned int a,b;
     a = 0x90000000;
     b = 2;

     unsigned int c = a*b;

     printf("Answer is %X\r\n", c);
 }

ответ: 0x20000000 (так что это должно было быть 0x120000000, но ответ был усечен, именно то, что вы хотели с операцией по модулю)

person Toad    schedule 14.01.2012
comment
Похоже, вы неправильно прочитали вопрос вместе с первым ответом. (который теперь удален) ОП хочет по модулю UINT_MAX, а не UINT_MAX + 1. - person Mysticial; 14.01.2012