Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 218, средняя оценка - 5.00
Ninasky
0 / 0 / 0
Регистрация: 29.05.2010
Сообщений: 12
#1

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

29.05.2010, 01:44. Просмотров 43397. Ответов 26
Метки нет (Все метки)

Подскажите, pls, как осуществить операцию m mod n (вычисление остатка) не используя операцию деления в процессе вычисления?

http://www.cyberforum.ru/cpp-beginners/thread442872.html

0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.05.2010, 01:44
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Операция mod() (C++):

mod (на C)
нужно проверить число на нечётность я сделал так: if (k mod 2 == 1) ...

A^B mod C
Найти A^B mod C. Тут как-то надо использовать рекурсию. Кто может помочь?

mod и div ??
Подскажите пожалуйста как будет mod и div в С++? Очень нужно)) Добавлено...

div и mod
Помогите, пожалуйста: вводимое с клавиатуры число n нужно разделить следующим...

DIv MOD в С++
не подскажете как описать оператор ДИВ в С++? суть такова а=5 b=2 x=a DIV 2...

26
fasked
Эксперт С++
4976 / 2556 / 241
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
30.05.2010, 20:31 #21
Evg, здесь требуется деление длинных чисел, которые не укладываются в стандартные типы данных, то есть явно больше 64 бит, а ты предлагаешь деление 32-битных чисел.
Тут надо бы число представить в виде массива (или строки, как говорил Кнут) и работать частями. То есть поделить младшую часть, посмотреть есть ли перенос в следующий разряд и т.д. Только вот проблема возникает от того, что "школьный" алгоритм деления столбиком будет 2 числа в 128 бит (еще только в 128) делить неимоверно долго. А вот над более сложными алгоритмами (один из них кстати очень и очень подробно описан у того же Кнута) придется думать. Тем более, если это задание институтское, то придется еще и объяснять как он работает о_О
0
Evg
Эксперт CАвтор FAQ
18937 / 6898 / 512
Регистрация: 30.03.2009
Сообщений: 19,432
Записей в блоге: 30
30.05.2010, 23:20 #22
Цитата Сообщение от fasked Посмотреть сообщение
Evg, здесь требуется деление длинных чисел, которые не укладываются в стандартные типы данных, то есть явно больше 64 бит, а ты предлагаешь деление 32-битных чисел.
Просто я поленился все посты читать...

Добавлено через 20 минут
В другой стороны, алгоритм он и в африке алгоритм. Если в таких магических числах есть возможность делать остальные операции, то указанным аглоритмом можно и делить
0
fasked
Эксперт С++
4976 / 2556 / 241
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
30.05.2010, 23:32 #23
Цитата Сообщение от Evg Посмотреть сообщение
В другой стороны, алгоритм он и в африке алгоритм. Если в таких магических числах есть возможность делать остальные операции, то указанным аглоритмом можно и делить
да никто же и не спорит, главное желание
0
Ninasky
0 / 0 / 0
Регистрация: 29.05.2010
Сообщений: 12
30.05.2010, 23:45  [ТС] #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)
________________________________________________________________________________________
Это неверно?
0
edd
37 / 37 / 2
Регистрация: 13.05.2010
Сообщений: 81
30.05.2010, 23:59 #25
а очень большое число на какое нужно делить тоже на оч большое или оно в рамках?
0
Ninasky
0 / 0 / 0
Регистрация: 29.05.2010
Сообщений: 12
31.05.2010, 00:08  [ТС] #26
m не ограничено, n 1024 бита ограничено, e 1024 бита ограничено
0
танкист34
-23 / 0 / 2
Регистрация: 15.03.2013
Сообщений: 328
25.04.2014, 19:42 #27
Roma_F,
Цитата Сообщение от Roma_F Посмотреть сообщение
и чем не устраивает 144976 % 26
на С++ ответ будет равным 0
0
25.04.2014, 19:42
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.04.2014, 19:42
Привет! Вот еще темы с решениями:

Div и mod в С++
Здравствуйте. Перехожу из паскаля в c++. Есть отрывок кода который проверяет...

mod и div
вообщем задачка такая. Нужно вычислить сумму средних чисел четырёхзначного...

Что такое mod в с++ ?
что такое mod в с++ и как он работает? например, m=12*17^9 mod 23. (m должно...

mod и div (Чистый С)
Здравсвтуйте,как на чистом С описывать эти функции mod и div????


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

Или воспользуйтесь поиском по форуму:
27
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru