|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
12.04.2012, 21:09 | #1 |
Пользователь
Регистрация: 14.07.2009
Сообщений: 30
|
Остаток от деления длинного числа на длинное число
Доброго времени суток, уважаемые форумчане!
Есть такая задача: Реализовать нахождение остатка от деления большого числа на большое число (оба числа представляют собой массив int где каждый элемент - разряд числа, младший разряд - нулевой элемент массива, старший разряд - последний элемент массива), известно что делимое по длине максимум в два раза больше делителя Решение задачи "в лоб", то есть вычитанием делимого из делителя в цикле пока не получим остаток мне кажется здесь жутко неудобным Что можете посоветовать? Какие мысли у вас есть на этот счет? Заранее спасибо! P.S. Проект разрабатывается в Visual Studio на C++, а ассемблерный код размещается во вставке после определения числовых массивов |
13.04.2012, 11:41 | #2 |
Форумчанин
Регистрация: 31.05.2009
Сообщений: 786
|
Вот, когда-то делал деление. Не оптимизировано.
|
14.04.2012, 10:19 | #3 |
Старожил
Регистрация: 20.04.2008
Сообщений: 5,526
|
( a x + b ) mod z == ( (a mod z) x + b ) mod z
делать аналогично делению в столбик но без хранения результата надеюсь будет понятно 1234 mod 11 =? 11 ---------------- _134 mod 11 =? _11 ----------------- __24 mod 11 =? __11 -------------- __13 mod 11 =? __11 mod 11 ---------------- ___2 <11 =2
программа — запись алгоритма на языке понятном транслятору
Последний раз редактировалось evg_m; 14.04.2012 в 10:22. |
14.04.2012, 11:04 | #4 |
Старожил
Регистрация: 08.02.2012
Сообщений: 2,173
|
как я понимаю, длина чисел должна быть произвольной?
на мой взгляд, самым быстрым решением будет вычитание с побитным сдвигом. т.е. если длина делимого(A) = m бит, а длина делителя (B) = n бит 1. создаём проверочный массив C = n+1 бит 2. копируем в младшие n бит массива C n старших бит из A 3. сравниваем B и C 4. если C > B, тогда C = C - B, а частное D = (D shl 1) + 1 5. иначе D = D shl 1 6. С = С shl 1 + следующий разряд из A 7. если в А разрядов больше не оставалось, тогда: D = частное C = остаток
Правильно поставленная задача - три четверти решения.
Последний раз редактировалось DiemonStar; 14.04.2012 в 11:23. |
14.04.2012, 11:55 | #5 | |
Пользователь
Регистрация: 14.07.2009
Сообщений: 30
|
Цитата:
У меня к вам вопрос по алгоритму: что изначально представляет из себя D? Должен быть заполнен нулями? А то просто от делимого и делителя он совсе получается независим изначально |
|
14.04.2012, 11:58 | #6 | |
Пользователь
Регистрация: 14.07.2009
Сообщений: 30
|
Цитата:
Если будут вопросы - я отпишу здесь |
|
14.04.2012, 13:10 | #7 | |
Старожил
Регистрация: 08.02.2012
Сообщений: 2,173
|
Цитата:
Правильно поставленная задача - три четверти решения.
|
|
14.04.2012, 13:50 | #8 | |
Пользователь
Регистрация: 14.07.2009
Сообщений: 30
|
Цитата:
|
|
14.04.2012, 14:03 | #9 |
Пользователь
Регистрация: 14.07.2009
Сообщений: 30
|
Кстати, забыл сказать, что делитель по которому берется модуль состоит в двоичной записи только из единиц, то есть представляет собой число 2^n-1, может это как-нибудь может упростить использование алгоритма
|
14.04.2012, 16:21 | #10 |
Старожил
Регистрация: 08.02.2012
Сообщений: 2,173
|
Всё от конкретной реализации зависит. Если на чистом ассемблере делать, то там ничего сложного я не вижу...
Правильно поставленная задача - три четверти решения.
|
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
остаток от деления | madman_34 | Общие вопросы C/C++ | 1 | 17.12.2011 00:37 |
Остаток от деления | Memfis_nya | Помощь студентам | 23 | 26.09.2010 14:58 |
Получить остаток от деления | Cpluser | Общие вопросы C/C++ | 18 | 26.02.2009 18:05 |
остаток от деления % | Division | Общие вопросы C/C++ | 5 | 25.12.2008 14:08 |