Добрый день. Возникла задача, под которую у меня мозг не заточен, если не ошибаюсь, из математики конечных полей.
Господа математики, подскажите, можно ли вычислить одним делением X и Y:

X=(a mod k1) mod k2
Y = (a mod k1)/k2

k1, k2 - константы, 16 бит.
а- переменная, 32 бит.

Нужна аппаратная реализация этого, если в лоб - два делителя подряд - задержка большая, скорость снижается, да и ресурсов делитель немало ест.
Нужна реализация с одним делителем + умножители и сумматоры/вычитатели если нужно.

Спасибо!

Или я чего-то не понимаю, или X и Y - это остаток и частное от деления a mod k1 на k2, т.е. получаются одновременно в процессе деления на k2.

Есть функция:
div_t div(int numer, int denom);
возвращающая структру:
typedef struct {
int quot;
int rem;
} div_t;

или функция
ldiv_t div (long numerator, long denominator);
возвращающая структру:
typedef struct {
long quot;
long rem;
} ldiv_t;

В возвращаемой структуре лежат сразу частное (quot) и остаток (rem).
Обе функции описаны в stdlib.h

http://www.cplusplus.com/reference/clibrary/cstdlib/div/

Делимое/делитель дают частное и остаток от деления. Возможно, Вам нужны и частное, и остаток вместе....
Аппаратная реализация для этого - это матрица элементов, например в а.с. 1462297 G 06 F 7/52 от 05.08.87 Матричное устройство для деления (деление в доп.кодах).
Подробней смотрите в http://electronix.ru/forum/index.php?showtopic=46469&hl=
Еще книга М.А.Карцев, В.А.Брик "Вычислительные системы и синхронная арифметика", 1981г.... см.рис.5.1.2, 5.4.1.

Спасибо за ответы!
Я alexpec, только пишу с другого компа...

Поясню подробней x и y - да, остаток и частное от деления. Использую алтеровскую мегафункцию деления, она дает одновременно частное и остаток от деления. Но проблема в том, что сначала первым делителем надо найти a mod k1, а вторым уже x и y ( функция вычисляет частное и остаток одновременно). Так вот как-то может преобразовать выражение чтоб операция деления и (или) остатка от деления была одна, предпочтительнее вместо второй операции деления использовать несколько (может быть) умножений и сложений/вычитаний. Т.е вторая операция деления - это уже край.

Напишу то же самое от себя...

Поясню подробней x и y - да, остаток и частное от деления. Использую алтеровскую мегафункцию деления, она дает одновременно частное и остаток от деления. Но проблема в том, что сначала первым делителем надо найти a mod k1, а вторым уже x и y ( функция вычисляет частное и остаток одновременно). Так вот как-то может преобразовать выражение чтоб операция деления и (или) остатка от деления была одна, предпочтительнее вместо второй операции деления использовать несколько (может быть) умножений и сложений/вычитаний. Т.е вторая операция деления - это уже край.

Не совсем понятно что у вас за проблема. Не укладываетесь в максимальное время цикла?
И эти два деления являются самыми проблемными из всей цепочки?

Тогда:
1. Напишите свою простенькую процедуру деления одновременно двух делимых - задача тривиальная
2. Или в начале умножьте k1*k2, а потом делите штатной функцией - получите два искомых значения

Но честно - я бы просмотрел все остальное и попробовал оптимизировать там. Не верится что
ресурсы кристалла уже вами использованы на 95% и все уперлось здесь. Посмотрите тайм-ауты
и другие цепочки использующие время. Если критичным осталось именно деление, то
это вершина оптимального кодирования под заданный кристалл.

Я понял так, что нужно вычислить последовательно два остатка от деления.
Например, для k1 = 10 и k2 = 3:
15 mod 10 = 5; 5 mod 3 = 2.
Автор хочет сразу из 15 получить 2. Я не вижу решения за одну операцию.

P.S. Может быть, поделить на сумму даст нужный результат? 15 mod 13 = 2. Верна ли такая математика?
P.P.S. Поправляю - нет, не верна... и это очевидно (взять по модулю 13 - может дать результат от 0 до 12).

Вопрос как обычно звучит так - чего хочет топикстартер?


Я понял исходные данные вот так:
X=(a mod k1) mod k2 - частное от деления а на k1*k2
Y = (a mod k1) div k2 - остаток от деления а на k1*k2

Но судя по тому что автор дал взаимоисключающие толкования
переменных x и y- то вопрос остается открытым

Удивительно толкование. И совсем неверное.
Вполне очевидно, что "mod" означает остаток от деления. Как оператор % в языке Си.
Что касается самого вопроса, то мне с моим ограниченным опытом (когда-то прослушал курс лекций по криптографии) кажется, что в общем случае эти операции не упрощаются.

Совершенно верно, mod - остаток от деления это где-то выше уже писал.



Что тут взаимоисключающего? Во-первых div - это частное, а mod - остаток, а не наоборот, а во-вторых, как правильно заметил Scifi,
(a mod k1) mod k2 совершенно не обязательно равно a mod (k1*k2)

никак, делайте два деления на одном блоке %)

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

1. Вот крутится такая мысля…
От деления a на k1 нужен только остаток. Значит прибавив к а любое целое число, умноженное на k1, мы ничего не изменим.
Допустим, при делении a на k1 мы получаем частное t и остаток r

a=k1*t+r

Во втором делении r делим на k2 и получаем Y и X.

a=k1*t+k2*Y+X

Возьмем в качестве «любого целого числа» Y–t

b = a+k1*(Y–t) = (k1+k2)*Y+X

Такое b можно подставить в Ваши формулы вместо а, и результат будет тот же.
Но самое интересное, что деление b на (k1+k2) даст сразу вожделенные X и Y… казалось бы. Но беда в том, что t мы не знаем. Мысля до конца не доведена, но я дал посыл, может быть кто-нибудь доведет.

2. Если k1 и k2 – константы, то вообще возможно обойтись без единого деления. Для простоты рассмотрю на примере деления 2-разрядных десятичных чисел. Пусть надо разделить 37 на 13.
37/13 = 37*100/13/100.
Берем число 100 div 13 =7 (константа). Вместо деления 37 (переменная) умножаем на 7 (константа). Получаем 259. Два младших разряда (добавленных выше) выкидываем и получаем частное =2.
Остаток находим как 37–13*2

Сообщение отредактировал Diusha - May 25 2011, 11:27

Если k1 не очень большое число (а k2 должно быть еще меньше, естественно), то второе деление можно заменить поиском по таблице, общим размером k1:
[0, 1, 2... k2-1], [0, 1, 2... k2-1], [0, 1, 2... k2-1], ...0, 1, ... (на каком-то числе закончится)
Тогда сначала нужно поделить на k1 и найти остаток, а потом по таблице по этому остатку-индексу найти остаток от деления на k2.