Существует ли метод модульного умножения БОЛЬШИХ чисел?
, экономим память и такты...
 |
Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
|
| ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
| [216.73.216.198] |
|
|
правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке
Модераторы: Akina, shadeofgray
Существует ли метод модульного умножения БОЛЬШИХ чисел?
, экономим память и такты...
Сообщ.
#1
,
|
|
 |
Возник вопрос: а существует ли алгоритм модульного умножения больших чисел?
Числа - допустим 1024 бита длинной. Можно реализовать топорную схему - просто умножить числа а потом взять модуль. Но для сохранения результата умножения нужно будет уже 2048 бит. Может есть более кошерное решение? Рыл Кнута, Уорена младьшего и Вельшенбаха - не нашел. Возможно не туда смотрел - тогда прошу ткнуть носом. А при последующем взятии модуля - извольте применять деление. Может есть что-нибуть хитрое для умножения? (Хотя метод Монтгомери позволяет выполнить приведение по модулю без деления, но это все равно обходные пути, хотя и "прямее"). |
|
Сообщ.
#2
,
|
 |
Самый быстрый алгоритм умножения 2 БОЛЬШИХ чисел это несомненно алгоритм Шенхаге—Штрассена(смотри в эту сторону),очень интересен метод Каратцубы.
MOD большого числа я реализовал на VB если что могу исходник выложить. А насчет Кнута ты сам себе задай вопрос: Я его смотрел? |
|
Сообщ.
#4
,
|
|
|
|
Цитата Koenig @ Посмотри эту книгу Это как раз Вельшенбах, спасибо :-) Штрассен со товарищи (в смысле Карацубы) идет ждать своей очереди. Ибо преимущества использования преобразований Фурье проявляются на числах длинной на порядок больше используемых мной. Как сделать алгоритм БЫСТРЫМ я знаю. Мой вопрос был: как сделать это избежав необходимости сохранения промежуточного результата во в два раза большей памяти. Модульное умножение. |
0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
0 пользователей:
[ Script execution time: 0,0168 ] [ 15 queries used ] [ Generated: 30.06.25, 06:18 GMT ]