Как переполнение int (или long long) в С++ влияет на модуль?

Предположим, у меня есть два long long, a и b, которые мне нужно умножить, а затем получить значение mod k для некоторого большого k, такого, что a, b и k находятся в диапазоне long long, но не int. Для простоты a, b ‹ k.

Таким образом, код будет:

long long a, b, k;
cin >> a >> b >> k;
cout << (a * b)%k << "\n";

Однако, поскольку a и b такие большие, если вы умножаете, как указано выше, и оно переполняется и становится отрицательным, тогда mod k будет отрицательным числом и неправильным.

Как убедиться, что значение mod k правильное?

Изменить: в качестве бонуса, как это работает на Java? Это то же самое, что и ожидалось? Или нужен BigInteger?


c++ long-integer integer-overflow modulus
person John Targaryen    schedule 14.06.2015    source источник
comment
См. раздел stackoverflow.com/questions/4240748/< /а>   -  person juanchopanza    schedule 14.06.2015
comment
a,b ‹ k, так что это не помогает.   -  person nneonneo    schedule 14.06.2015
comment
Попробуйте использовать тот факт, что (a * b) % k == ((a % k) * (b % k)) % k . Если k меньше, чем long, это сработает. Если нет, вам нужно будет выполнить простую множественную точность.   -  person Richard Critten    schedule 15.06.2015
comment
С технической точки зрения, все после переполнения является неопределенным поведением при работе со значениями со знаком; вообще всякое может случиться,   -  person    schedule 15.06.2015
comment
@RichardCritten, пожалуйста, прочитайте вопрос и комментарии, прежде чем отвечать. nneonneo уже указал, что a,b ‹ k в комментарии прямо над вашим, а мое второе предложение в вопросе говорит a, b ‹ k. Таким образом, ваш метод ничем не лучше моего, как было указано ранее.   -  person John Targaryen    schedule 15.06.2015

Ответы (2)


arrow_upward
1
arrow_downward

Многие компиляторы предлагают 128-битный целочисленный тип. Например, с помощью g++ вы можете сделать функцию

static inline int64_t mulmod(int64_t x, int64_t y, int64_t m)
{
    return ( (__int128_t)x * y) % m;
}

Кроме того: если вы можете, попробуйте придерживаться беззнаковых целых типов, когда вы выполняете модульную арифметику. Поведение округления при целочисленном делении делает использование % очень неудобным, когда задействованы значения со знаком.

person Community    schedule 14.06.2015

arrow_upward
1
arrow_downward

Если вы знаете, что значения меньше ULONGLONG_MAX/2 (поэтому добавление не будет переполняться), вы можете выполнять умножение по одному биту за раз:

unsigned long long mulmod(unsigned long long a, unsigned long unsigned long b, long long m) {
    unsigned long long rv = 0;
    a %= m;
    b %= m;
    while (b) {
        if (b&1) { rv += a; if (rv >= m) rv -= m; }
        a += a; if (a >= m) a -= m;
        b >>= 1; }
    return rv; }

Если вы знаете, что работаете на gcc/x86_64, вы можете попробовать:

unsigned long mulmod(unsigned long a, unsigned long b, unsigned long m) {
    unsigned long rv;
    asm ("mulq %2; divq %3" : "=d"(rv), "+a"(a): "S"(b), "c"(m));
    return rv;
}

который будет работать до ULONG_MAX

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

person Chris Dodd    schedule 14.06.2015
comment
Будет ли один бит за раз означать дополнительный логарифмический коэффициент для умножения? - person John Targaryen; 15.06.2015
comment
Поскольку максимально возможный размер здесь составляет 63 или 127 бит (в зависимости от размера long long на вашем компьютере), асимтотическая производительность на самом деле не применяется. - person Chris Dodd; 15.06.2015