Как быть если остаток от деления не помещается в беззнаковый тип?

#алгоритм

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

Ответы

Ответ 1

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

Пусть имеются два беззнаковых числа x и y и делитель d. Тогда остаток r от деления
x + y на d можно вычислить так.

r1 = x % d;
r2 = y % d;

r = r1 < ( d - r2 ) ? r1 + r2 : r1 - ( d - r2 );


Вот пример функции для типа unsigned int на C/C++

unsigned int remainder(unsigned int x, unsigned int y, unsigned int d)
{
    unsigned int r1 = x % d;
    unsigned int r2 = y % d;

    return r1 < (d - r2) ? r1 + r2 : r1 - (d - r2);
}


Ответ 2

Просто складываете остатки от деления и еще раз применяете к ним операцию получения
остатка. На C/C++

unsigned r = (x %d + y %d) %d;


На Pascal

r = (x mod d + y mod d) mod d;


Судите сами:
пусть x = kd+r1, y=md+r2. Тогда (x+y)%d = ((k+m)d + (r1+r2))%d = (r1+r2)%d. Очевидно,
что это соответствует (x%d + y%d) %d = (r1+r2)%d...

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

P.S. Есть, правда, один нехороший случай - если d больше половины представимого диапазона,
и сумма остатков переваливает за диапазон. Этот случай надо рассматривать отдельно,
с вычитанием половины d из каждого из остатков. Но это уже экзотика :)

Вот примерный код:

unsigned mod(unsigned x, unsigned y, unsigned d)
{
    x = x % d;
    y = y % d;
    if (x+y < x) // Overflow
    {
        x -= d/2;
        y -= (d-d/2);
    }
    return (x+y)%d;
}


Работать будет корректно даже при, скажем, x < d/2. Но если кого смущает - вот еще
один вариант:

unsigned mod(unsigned x, unsigned y, unsigned d)
{
    x = x % d;
    y = y % d;
    if (x+y < x) // Overflow
    {
        if (x < y)
        {
            y -= (d-x);
            x = 0;
        }
        else
        {
            x -= (d-y);
            y = 0;
        }
    }
    return (x+y)%d;
}


P.P.S. Спасибо @PavelMayorov за подсказку:

unsigned mod(unsigned x, unsigned y, unsigned d)
{
    x = x % d;
    y = y % d + x;
    if (y < x) y-=d;
    return y%d;
}