Форум русскоязычного сообщества Ubuntu


Считаете, что Ubuntu недостаточно дружелюбна к новичкам?
Помогите создать новое Руководство для новичков!

Автор Тема: Умножение в Си, как избежать переполнения  (Прочитано 2378 раз)

0 Пользователей и 1 Гость просматривают эту тему.

Оффлайн __v1tos

  • Автор темы
  • Участник
  • *
  • Сообщений: 105
  • Ubuntuu 10.10 x86-64
    • Просмотр профиля
Вообщем задача простая, нужно выполнить умножение и взять результат по модулю
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.
Решение должно быть достаточно быстрым
AMD Phenom II 945, GA-MA790GPT-UD3H (HD 3300), 5 GiB ram

Оффлайн Lion-Simba

  • Старожил
  • *
  • Сообщений: 1126
    • Просмотр профиля
Re: Умножение в Си, как избежать переполнения
« Ответ #1 : 28 Сентябрь 2011, 09:50:16 »
Например, библиотека http://gmplib.org/
Оказываю индивидуальную платную техподдержку широкого профиля. Обращаться в ЛС или Jabber.

Оффлайн __v1tos

  • Автор темы
  • Участник
  • *
  • Сообщений: 105
  • Ubuntuu 10.10 x86-64
    • Просмотр профиля
Re: Умножение в Си, как избежать переполнения
« Ответ #2 : 28 Сентябрь 2011, 11:35:52 »
Ну вообще, я пишу что то вроде длинной арифметики на СОК (система остаточных классов), так вот сейчас я пытаюсь если не "победить" gmp то хотя бы приблизится к ней. Использование же gmp в этом участке кода означает значительный проигрыш по быстродействию.
AMD Phenom II 945, GA-MA790GPT-UD3H (HD 3300), 5 GiB ram

andrey_p

  • Гость
Re: Умножение в Си, как избежать переполнения
« Ответ #3 : 28 Сентябрь 2011, 16:05:23 »
gcc имеет __uint128_t и __int128_t целые.

Оффлайн __v1tos

  • Автор темы
  • Участник
  • *
  • Сообщений: 105
  • Ubuntuu 10.10 x86-64
    • Просмотр профиля
Re: Умножение в Си, как избежать переполнения
« Ответ #4 : 28 Сентябрь 2011, 19:32:27 »
Спасибо! Самое то, быстродействие падает самую малость, вообщем то что доктор прописал :D
И еще вопрос, есть ли такие, встроенные в gcc функции, которые при умножении двух операндов возвращают результат удвоенного размера.
Скажем long long mul(int a, int b) ???
« Последнее редактирование: 29 Сентябрь 2011, 10:30:41 от __v1tos »
AMD Phenom II 945, GA-MA790GPT-UD3H (HD 3300), 5 GiB ram

 

Страница сгенерирована за 0.093 секунд. Запросов: 25.