остаток от деления

[Luke]

читаем внимательно до конца!
как получить остаток от деления без опперации деления
на 3,7,11,13,17,19,23,29,31 и от константы, которая получится от такого произведения 3*7*11*13*17*19*23*29*31

нужно для аппаратной реализации (синтез)

[Server]

Либо я что-то не понял либо все элементарно:
1. Остатка не будет в любом случае т.к. делимое делится на делитель без остатка.

2. Если ты имеешь в виду частное (результат от деления одного числа на другое) то перемнож все числа кроме того на которое ты собираешься делить свою "константу", это и будет ответ.

[ОсТроУхий]

Подробнее что на что делить надо.

[Luke]

черный ящик (не делитель!) на входе любое число от 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]

Решение, что называется в лоб:
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]

Fisher нужно для аппаратной реализации (синтез) за один такт посчитать

[Fisher]

Надо было жирным выделять не "без операции деления", а "за один такт", т.к. даже с операцией деления, за один такт остаток от деления не вычислишь (сама операция деления несколько тактов занимает).

[meddle]

За 1 такт: для 1го случая - заранее просчитать и забить таблицы в ПЗУ. Для 2го случая тоже можно, но памяти многовато потребуется...

[meddle]

По 1му случаю можно ещё проще: взять 5 последних бит делимого, расчитать 9 дешифраторов и в результате имеем сразу все остатки.

[Luke]

Сообщение от Fisher

Надо было жирным выделять не "без операции деления", а "за один такт", т.к. даже с операцией деления, за один такт остаток от деления не вычислишь (сама операция деления несколько тактов занимает).

делают хардварные делители с плавающей запятой, которые делят за один такт.
а целочисленный хардварный делитель делает остаток автоматически.

[Balrog]

meddle А как это? к примеру, 32 и 64 - последние 5 бит одинаковые, а остаток от деления на 3 разный.

Luke не могу представить реализации, как сделать меньше тактов, чем (число значащих разрядов делимого - число значащих разрядов делителя). Если умножение можно через кучу параллельных сумматоров пропустить, то при делении каждый результат зависит от предыдущего.

[meddle]

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.
Расчёт дешифратора, видимо, будет весьма сложен...

[Luke]

Сообщение от Balrog

Luke не могу представить реализации, как сделать меньше тактов, чем (число значащих разрядов делимого - число значащих разрядов делителя). Если умножение можно через кучу параллельных сумматоров пропустить, то при делении каждый результат зависит от предыдущего.

у меня реально есть модель целочисленного делителя.
делит за такт. так, что не в этом проблема. вот свернуть бы его! как умножитель по Буту.

[Luke]

для остатков есть такая формула:
(a*b+c) mod d = ((a mod d)*(b mod d)+(c mod d)) mod d
проверял: работает!
есть ли другие фформулы? чему равно выражение:
a mod (b*c) =?

этим хочу сказать, что для 9 младших делителей найдено некое решение (может быть не оптимальное), которое не приемлемо для последнего делителя (самого большого)