Форум программистов, компьютерный форум CyberForum.ru

Операция mod() - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 218, средняя оценка - 5.00
Ninasky
0 / 0 / 0
Регистрация: 29.05.2010
Сообщений: 12
29.05.2010, 01:44     Операция mod() #1
Подскажите, pls, как осуществить операцию m mod n (вычисление остатка) не используя операцию деления в процессе вычисления?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.05.2010, 01:44     Операция mod()
Посмотрите здесь:

mod (на C) C++
C++ mod и div
mod и div ?? C++
div и mod C++
A^B mod C C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
fasked
Эксперт C++
 Аватар для fasked
4924 / 2504 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
30.05.2010, 20:31     Операция mod() #21
Evg, здесь требуется деление длинных чисел, которые не укладываются в стандартные типы данных, то есть явно больше 64 бит, а ты предлагаешь деление 32-битных чисел.
Тут надо бы число представить в виде массива (или строки, как говорил Кнут) и работать частями. То есть поделить младшую часть, посмотреть есть ли перенос в следующий разряд и т.д. Только вот проблема возникает от того, что "школьный" алгоритм деления столбиком будет 2 числа в 128 бит (еще только в 128) делить неимоверно долго. А вот над более сложными алгоритмами (один из них кстати очень и очень подробно описан у того же Кнута) придется думать. Тем более, если это задание институтское, то придется еще и объяснять как он работает о_О
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Evg
Эксперт С++Автор FAQ
 Аватар для Evg
16821 / 5242 / 318
Регистрация: 30.03.2009
Сообщений: 14,118
Записей в блоге: 26
30.05.2010, 23:20     Операция mod() #22
Цитата Сообщение от fasked Посмотреть сообщение
Evg, здесь требуется деление длинных чисел, которые не укладываются в стандартные типы данных, то есть явно больше 64 бит, а ты предлагаешь деление 32-битных чисел.
Просто я поленился все посты читать...

Добавлено через 20 минут
В другой стороны, алгоритм он и в африке алгоритм. Если в таких магических числах есть возможность делать остальные операции, то указанным аглоритмом можно и делить
fasked
Эксперт C++
 Аватар для fasked
4924 / 2504 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
30.05.2010, 23:32     Операция mod() #23
Цитата Сообщение от Evg Посмотреть сообщение
В другой стороны, алгоритм он и в африке алгоритм. Если в таких магических числах есть возможность делать остальные операции, то указанным аглоритмом можно и делить
да никто же и не спорит, главное желание
Ninasky
0 / 0 / 0
Регистрация: 29.05.2010
Сообщений: 12
30.05.2010, 23:45  [ТС]     Операция mod() #24
m^e mod n
а если разбить число m на блоки? или как в алгоритме быстрого возведения сразу брать по модулю(вычислять остаток )?
_______________________________________________________________________________________
В алгоритме RSA очень много возведений в степень по модулю натурального числа. Конечно же, не нужно производить триллиарды умножений, а затем брать остаток от деления числа из миллиардов цифр. Остаток от деления берется после каждого умножения. Таким образом, при перемножении двух чисел, состоящих из k бит потребуется 2 * k-битное число, которое затем делится на модуль и получается остаток, опять же состоящий из k бит (если модульное число состоит из k бит).

Сложность этого алгоритма может быть оценена как O(ln m), где m - модуль, по которому производится умножение. Запись O(ln m) означает, что для реализации алгоритма потребуется порядка ln m операций. Например, если число имеет разрядность 1024 бит (при этом длина m не менее 1024 бит), то умножение по модулю необходимо будет провести порядка ln m = ln 21024 = 710 раз, что относительно немного.

Алгоритм вычисления ad (mod m):

1. Число d представить в двоичной системе счисления: d = d0 * 2r + ... + dr - 1 * 2 + dr, где di - цифры в двоичном представлении, равные 0 или 1, d0 = 1
2. Положить a0 = a, затем для i = 1, ... , r вычислить ai = (ai - 1) 2 * adi (mod m)
3. ar есть искомое число ad (mod m)
________________________________________________________________________________________
Это неверно?
edd
36 / 36 / 0
Регистрация: 13.05.2010
Сообщений: 81
30.05.2010, 23:59     Операция mod() #25
а очень большое число на какое нужно делить тоже на оч большое или оно в рамках?
Ninasky
0 / 0 / 0
Регистрация: 29.05.2010
Сообщений: 12
31.05.2010, 00:08  [ТС]     Операция mod() #26
m не ограничено, n 1024 бита ограничено, e 1024 бита ограничено
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.04.2014, 19:42     Операция mod()
Еще ссылки по теме:

C++ mod
DIv MOD в С++ C++
Div и mod в С++ C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
танкист34
-62 / 0 / 0
Регистрация: 15.03.2013
Сообщений: 328
25.04.2014, 19:42     Операция mod() #27
Roma_F,
Цитата Сообщение от Roma_F Посмотреть сообщение
и чем не устраивает 144976 % 26
на С++ ответ будет равным 0
Yandex
Объявления
25.04.2014, 19:42     Операция mod()
Ответ Создать тему
Опции темы

Текущее время: 04:42. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru