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

С++ для начинающих

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

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

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

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

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

mod - C++
Здравствуйте! У меня вопрос наверное глупый. Препод для выбора курсовой поставил следующие условия: Вариант задания выбирается по формуле...

mod (на C) - C++
нужно проверить число на нечётность я сделал так: if (k mod 2 == 1) <действия> но компилятор выдал ошибку типа:syntax error...

Div и mod в С++ - C++
Здравствуйте. Перехожу из паскаля в c++. Есть отрывок кода который проверяет есть ли в числе N цифра 3 и есть ли в числе вводимое с...

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

DIv MOD в С++ - C++
не подскажете как описать оператор ДИВ в С++? суть такова а=5 b=2 x=a DIV 2 y=5/2 printf(...x) (y) мне нужно...

26
fasked
Эксперт С++
4945 / 2525 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
30.05.2010, 17:09 #16
Цитата Сообщение от Ninasky Посмотреть сообщение
с математикой проблем нет, а вот с программированием есть
из программирования здесь надо знать как строится цикл for
Цитата Сообщение от Ninasky Посмотреть сообщение
Я так поняла надо искать программиста который будет за деньги это делать...
ну да... или же начинать самому, а с небольшими проблемами обращаться на форум
0
Ninasky
0 / 0 / 0
Регистрация: 29.05.2010
Сообщений: 12
30.05.2010, 17:38  [ТС] #17
ок, спасибо
0
Evg
Эксперт CАвтор FAQ
18032 / 6264 / 427
Регистрация: 30.03.2009
Сообщений: 17,219
Записей в блоге: 27
30.05.2010, 19:27 #18
Цитата Сообщение от Ninasky Посмотреть сообщение
Подскажите, pls, как осуществить операцию m mod n (вычисление остатка) не используя операцию деления в процессе вычисления?
Небольшой вопрос. Это институтское задание или нужно реализовать деление на архитектуре, где аппаратное деление отсутствует? Если второе - то завтра с работы могу кинуть исходник, если первое - то не факт, что такой вариант устроит преподавателей (потому как скорее всего требуется некоторый конкретный алгоритм)
0
Ninasky
0 / 0 / 0
Регистрация: 29.05.2010
Сообщений: 12
30.05.2010, 20:14  [ТС] #19
какой то определенный алгоритм не нужен.
Буду очень благодарна если скините!
0
Evg
Эксперт CАвтор FAQ
18032 / 6264 / 427
Регистрация: 30.03.2009
Сообщений: 17,219
Записей в блоге: 27
30.05.2010, 20:23 #20
Завтра скину, если не забуду

Добавлено через 7 минут
Совсем забыл, что оно уже есть на форуме
Реализация целочисленного беззнакового деления
0
fasked
Эксперт С++
4945 / 2525 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
30.05.2010, 20:31 #21
Evg, здесь требуется деление длинных чисел, которые не укладываются в стандартные типы данных, то есть явно больше 64 бит, а ты предлагаешь деление 32-битных чисел.
Тут надо бы число представить в виде массива (или строки, как говорил Кнут) и работать частями. То есть поделить младшую часть, посмотреть есть ли перенос в следующий разряд и т.д. Только вот проблема возникает от того, что "школьный" алгоритм деления столбиком будет 2 числа в 128 бит (еще только в 128) делить неимоверно долго. А вот над более сложными алгоритмами (один из них кстати очень и очень подробно описан у того же Кнута) придется думать. Тем более, если это задание институтское, то придется еще и объяснять как он работает о_О
0
Evg
Эксперт CАвтор FAQ
18032 / 6264 / 427
Регистрация: 30.03.2009
Сообщений: 17,219
Записей в блоге: 27
30.05.2010, 23:20 #22
Цитата Сообщение от fasked Посмотреть сообщение
Evg, здесь требуется деление длинных чисел, которые не укладываются в стандартные типы данных, то есть явно больше 64 бит, а ты предлагаешь деление 32-битных чисел.
Просто я поленился все посты читать...

Добавлено через 20 минут
В другой стороны, алгоритм он и в африке алгоритм. Если в таких магических числах есть возможность делать остальные операции, то указанным аглоритмом можно и делить
0
fasked
Эксперт С++
4945 / 2525 / 180
Регистрация: 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
36 / 36 / 0
Регистрация: 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
-62 / 0 / 0
Регистрация: 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
Привет! Вот еще темы с ответами:

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

div и mod - C++
Помогите, пожалуйста: вводимое с клавиатуры число n нужно разделить следующим образом (n, n1, n2 - целые ): если n четное, то n1 = n2 =...

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

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


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

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

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