читаем внимательно до конца!
как получить остаток от деления без опперации деления
на 3,7,11,13,17,19,23,29,31 и от константы, которая получится от такого произведения 3*7*11*13*17*19*23*29*31
Либо я что-то не понял либо все элементарно:
1. Остатка не будет в любом случае т.к. делимое делится на делитель без остатка.
2. Если ты имеешь в виду частное (результат от деления одного числа на другое) то перемнож все числа кроме того на которое ты собираешься делить свою "константу", это и будет ответ.
[Ответ]
черный ящик (не делитель!) на входе любое число от 0 до 131071 (делимое). как получить от этого числа остаток от деления на любое из чисел 3,7,11,13,17,19,23,29,31 (делители)
и точно такаяже ситуация для чисел от 0 до 549755813887 (делимое), а делитель: 3*7*11*13*17*19*23*29*31=20056049013
в первом посте указаны только делители 10 штук!
[Ответ]
Fisher 11:52 19.09.2005
Решение, что называется в лоб:
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;
и точно такое же решение во втором случае.
[Ответ]
Luke 07:25 20.09.2005
Fisher нужно для аппаратной реализации (синтез) за один такт посчитать
[Ответ]
Fisher 10:44 20.09.2005
Надо было жирным выделять не "без операции деления", а "за один такт", т.к. даже с операцией деления, за один такт остаток от деления не вычислишь (сама операция деления несколько тактов занимает).
[Ответ]
meddle 13:35 20.09.2005
За 1 такт: для 1го случая - заранее просчитать и забить таблицы в ПЗУ. Для 2го случая тоже можно, но памяти многовато потребуется... [Ответ]
meddle 14:09 20.09.2005
По 1му случаю можно ещё проще: взять 5 последних бит делимого, расчитать 9 дешифраторов и в результате имеем сразу все остатки.
[Ответ]
Luke 07:35 21.09.2005
Сообщение от Fisher:
Надо было жирным выделять не "без операции деления", а "за один такт", т.к. даже с операцией деления, за один такт остаток от деления не вычислишь (сама операция деления несколько тактов занимает).
делают хардварные делители с плавающей запятой, которые делят за один такт.
а целочисленный хардварный делитель делает остаток автоматически.
[Ответ]
Balrog 08:08 22.09.2005
meddle А как это? к примеру, 32 и 64 - последние 5 бит одинаковые, а остаток от деления на 3 разный.
Luke не могу представить реализации, как сделать меньше тактов, чем (число значащих разрядов делимого - число значащих разрядов делителя). Если умножение можно через кучу параллельных сумматоров пропустить, то при делении каждый результат зависит от предыдущего.
[Ответ]
meddle 09:32 22.09.2005
Balrog согласен, слегка погорячился надо преобразовывать (дешифровать) в код 2-n, где n - делитель.
пример для n=3:
В данном случае остаток - последние 2 бита. Для n=31 - будут последние 5.
Расчёт дешифратора, видимо, будет весьма сложен... [Ответ]
Luke 07:50 23.09.2005
Сообщение от Balrog: Luke не могу представить реализации, как сделать меньше тактов, чем (число значащих разрядов делимого - число значащих разрядов делителя). Если умножение можно через кучу параллельных сумматоров пропустить, то при делении каждый результат зависит от предыдущего.
у меня реально есть модель целочисленного делителя.
делит за такт. так, что не в этом проблема. вот свернуть бы его! как умножитель по Буту.
[Ответ]
Luke 07:56 23.09.2005
для остатков есть такая формула:
(a*b+c) mod d = ((a mod d)*(b mod d)+(c mod d)) mod d
проверял: работает!
есть ли другие фформулы? чему равно выражение:
a mod (b*c) =?
этим хочу сказать, что для 9 младших делителей найдено некое решение (может быть не оптимальное), которое не приемлемо для последнего делителя (самого большого)
[Ответ]
