| Вопрос: Как распараллелить X = Y Mod 2^Z-1 ? | Добавлено: 05.05.07 01:04 |
Автор вопроса:  VisBas | Web-сайт: chipmicro.narod.ru
|
|
Нужен пример(С/VB/Delphi) редукции по модулю такого вида. |
| Ответы | Всего ответов: 6 |
|
Номер ответа: 1 Автор ответа:  Sharp Лидер форума ICQ: 216865379 Вопросов: 106 Ответов: 9979 |
Web-сайт: Профиль | | #1 | Добавлено: 05.05.07 04:17 |
| Какого размера X, Y и Z? Если небольшого, то какой смысл это параллелить? | ||
|
Номер ответа: 2 Автор ответа: HACKERРазработчик Offline Client Вопросов: 236 Ответов: 8362 |
Профиль | | #2 | Добавлено: 05.05.07 07:00 |
| А чем эта задача отличается от распараллеливания других задач? Определить диапазоны каждой переменной для каждого потока и вперёд... | ||
|
Номер ответа: 3 Автор ответа: VisBas Вопросов: 44 Ответов: 127 |
Web-сайт: Профиль | | #3 | Добавлено: 05.05.07 11:49 |
|
Y и 2^Z-1 - длинные числа. Диапазонов нет, есть конкретные длинные числа. К примеру умножение полиномов можно свести к свертке, а ее выполнить с помощью БПФ. Данный процесс можно распараллелить. Может быть можно свести деление к умножению полиномов или еще как распараллелить эту работу? |
||
|
Номер ответа: 4 Автор ответа: SharpЛидер форума ICQ: 216865379 Вопросов: 106 Ответов: 9979 |
Web-сайт: Профиль | | #4 | Добавлено: 05.05.07 18:10 |
|
Вроде как сложность этого вычисления log2(Y) / Z длинных сложений. Не представляю, какого размера числа нужно складывать, чтобы проблема памяти не возникла раньше, чем проблема скорости.
Пример: 10100111101 mod 2^5-1 Т.к. n*2^k + d = n*(2^k-1)+n+d = n+d (mod 2^k-1) 101001|11101
|11111 ------------ 101001 + 11101 ------- 1000110 10|00110 -> 00110 + 10 ----- 01000 - ответ |
||
|
Номер ответа: 5 Автор ответа: VisBasВопросов: 44 Ответов: 127 |
Web-сайт: Профиль | | #5 | Добавлено: 08.05.07 09:11 |
|
Проблема памяти вообще не возникает при грамотном использовании ресурсов. Нужна лишь память размером ~ Y. Спасибо, быстрый алгоритм! |
||
|
Номер ответа: 6 Автор ответа: SharpЛидер форума ICQ: 216865379 Вопросов: 106 Ответов: 9979 |
Web-сайт: Профиль | | #6 | Добавлено: 08.05.07 10:21 |
| Ну я о том и говорю, что даже операции с гигабайтными числами будут выполняться достаточно быстро, чтобы распараллеливание не имело смысла. | ||
Страница: 1 |