Если это ваш первый визит, рекомендуем почитать справку по форуму. Для размещения своих сообщений необходимо зарегистрироваться. Для просмотра сообщений выберите раздел. |
остаток от деления |
Философия, технологии, алгоритмы! |
|
Опции темы |
16.09.2005, 07:22 | #1 |
Форумец
Сообщений: 526
Регистрация: 21.06.2004
Не в сети |
остаток от деления
читаем внимательно до конца!
как получить остаток от деления без опперации деления на 3,7,11,13,17,19,23,29,31 и от константы, которая получится от такого произведения 3*7*11*13*17*19*23*29*31 нужно для аппаратной реализации (синтез) |
16.09.2005, 20:24 | #2 |
Форумец
Сообщений: 263
Регистрация: 18.04.2003
Возраст: 43
Не в сети |
Либо я что-то не понял либо все элементарно:
1. Остатка не будет в любом случае т.к. делимое делится на делитель без остатка. 2. Если ты имеешь в виду частное (результат от деления одного числа на другое) то перемнож все числа кроме того на которое ты собираешься делить свою "константу", это и будет ответ. |
19.09.2005, 07:56 | #4 |
Форумец
Сообщений: 526
Регистрация: 21.06.2004
Не в сети |
черный ящик (не делитель!) на входе любое число от 0 до 131071 (делимое). как получить от этого числа остаток от деления на любое из чисел 3,7,11,13,17,19,23,29,31 (делители)
и точно такаяже ситуация для чисел от 0 до 549755813887 (делимое), а делитель: 3*7*11*13*17*19*23*29*31=20056049013 в первом посте указаны только делители 10 штук! |
19.09.2005, 11:52 | #5 |
Registered User
Сообщений: 67
Регистрация: 08.07.2003
Возраст: 43
Не в сети |
Решение, что называется в лоб:
int d = 3; // 3,7,11,13,17,19,23,29,31 int x = 55555; // 0...131071 int remainder = x >= d ? 0 : x; for (int v = d; v < x; v += d) if (v < x && v + d > x) reminder = x - v; и точно такое же решение во втором случае. |
20.09.2005, 10:44 | #7 |
Registered User
Сообщений: 67
Регистрация: 08.07.2003
Возраст: 43
Не в сети |
Надо было жирным выделять не "без операции деления", а "за один такт", т.к. даже с операцией деления, за один такт остаток от деления не вычислишь (сама операция деления несколько тактов занимает).
|
21.09.2005, 07:35 | #10 | |
Форумец
Сообщений: 526
Регистрация: 21.06.2004
Не в сети |
Цитата:
а целочисленный хардварный делитель делает остаток автоматически. |
|
22.09.2005, 08:08 | #11 |
Лентяй
Сообщений: 5,456
Регистрация: 23.03.2005
Возраст: 51
Не в сети |
meddle А как это? к примеру, 32 и 64 - последние 5 бит одинаковые, а остаток от деления на 3 разный.
Luke не могу представить реализации, как сделать меньше тактов, чем (число значащих разрядов делимого - число значащих разрядов делителя). Если умножение можно через кучу параллельных сумматоров пропустить, то при делении каждый результат зависит от предыдущего. |
22.09.2005, 09:32 | #12 |
Registered User
Сообщений: 288
Регистрация: 11.05.2004
Не в сети |
Balrog согласен, слегка погорячился надо преобразовывать (дешифровать) в код 2-n, где n - делитель.
пример для n=3: 1 : 0001 -> 00001 2 : 0010 -> 00010 3 : 0011 -> 00100 4 : 0100 -> 00101 5 : 0101 -> 00110 6 : 0110 -> 01000 7 : 0111 -> 01001 8 : 1000 -> 01010 9 : 1001 -> 01100 10: 1010 -> 01101 11: 1011 -> 01110 12: 1100 -> 10000 13: 1101 -> 10001 14: 1110 -> 10010 15: 1111 -> 10100 В данном случае остаток - последние 2 бита. Для n=31 - будут последние 5. Расчёт дешифратора, видимо, будет весьма сложен... |
23.09.2005, 07:50 | #13 | |
Форумец
Сообщений: 526
Регистрация: 21.06.2004
Не в сети |
Цитата:
делит за такт. так, что не в этом проблема. вот свернуть бы его! как умножитель по Буту. |
|
23.09.2005, 07:56 | #14 |
Форумец
Сообщений: 526
Регистрация: 21.06.2004
Не в сети |
для остатков есть такая формула:
(a*b+c) mod d = ((a mod d)*(b mod d)+(c mod d)) mod d проверял: работает! есть ли другие фформулы? чему равно выражение: a mod (b*c) =? этим хочу сказать, что для 9 младших делителей найдено некое решение (может быть не оптимальное), которое не приемлемо для последнего делителя (самого большого) |