Умножение в Си, как избежать переполнения

[__v1tos]

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

Код: [Выделить]

unsigned long a, b, c, res;
......
res = (a * b) % c;

При этом a * b может быть достаточно большим и не поместится в unsigned long.

известно также что

Код: [Выделить]

a % c == a
b % c == b


Что бы избежать переполнения на 32 разрядной машине можно сгородить:

Код: [Выделить]

unsigned long a, b, c, res;
......
res = ( (unsigned long long)a * (unsigned long long)b) % (unsigned long long)c;

1). Но как быть на 64 разрядной машине?
2). Есть ли в gcc встроенные функции, хотелось бы что-нибудь типа MulDiv на винде, только делает mulmod

P.S.
Решение должно быть достаточно быстрым

[Lion-Simba]

Например, библиотека http://gmplib.org/

[__v1tos]

Ну вообще, я пишу что то вроде длинной арифметики на СОК (система остаточных классов), так вот сейчас я пытаюсь если не "победить" gmp то хотя бы приблизится к ней. Использование же gmp в этом участке кода означает значительный проигрыш по быстродействию.

[andrey_p]

gcc имеет __uint128_t и __int128_t целые.

[__v1tos]

Спасибо! Самое то, быстродействие падает самую малость, вообщем то что доктор прописал
И еще вопрос, есть ли такие, встроенные в gcc функции, которые при умножении двух операндов возвращают результат удвоенного размера.
Скажем long long mul(int a, int b)