[alexPec 3]

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

Господа математики, подскажите, можно ли вычислить одним делением X и Y:

 

X=(a mod k1) mod k2

Y = (a mod k1)/k2

 

k1, k2 - константы, 16 бит.

а- переменная, 32 бит.

 

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

Нужна реализация с одним делителем + умножители и сумматоры/вычитатели если нужно.

 

Спасибо!

 

 

[Сергей Борщ 119]

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

[Xenia 35]

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

Господа математики, подскажите, можно ли вычислить одним делением X и Y:

 

X=(a mod k1) mod k2

Y = (a mod k1)/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/

[Voloshchenko 0]

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

Нужна реализация с одним делителем + умножители и сумматоры/вычитатели если нужно.

Делимое/делитель дают частное и остаток от деления. Возможно, Вам нужны и частное, и остаток вместе....

Аппаратная реализация для этого - это матрица элементов, например в а.с. 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.

[Visk 0]

Делимое/делитель дают частное и остаток от деления. Возможно, Вам нужны и частное, и остаток вместе....

Аппаратная реализация для этого - это матрица элементов, например в а.с. 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 ( функция вычисляет частное и остаток одновременно). Так вот как-то может преобразовать выражение чтоб операция деления и (или) остатка от деления была одна, предпочтительнее вместо второй операции деления использовать несколько (может быть) умножений и сложений/вычитаний. Т.е вторая операция деления - это уже край.

[alexPec 3]

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

 

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

 

[i-mir 0]

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

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

 

Тогда:

1. Напишите свою простенькую процедуру деления одновременно двух делимых - задача тривиальная

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

 

Но честно - я бы просмотрел все остальное и попробовал оптимизировать там. Не верится что

ресурсы кристалла уже вами использованы на 95% и все уперлось здесь. Посмотрите тайм-ауты

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

это вершина оптимального кодирования под заданный кристалл.

 

[ViKo 1]

Не совсем понятно что у вас за проблема.

...

1. Напишите свою простенькую процедуру деления одновременно двух делимых - задача тривиальная

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

Я понял так, что нужно вычислить последовательно два остатка от деления.

Например, для 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).

[i-mir 0]

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

Поясню подробней x и y - остаток и частное от деления.

 

Я понял исходные данные вот так:

X=(a mod k1) mod k2 - частное от деления а на k1*k2

Y = (a mod k1) div k2 - остаток от деления а на k1*k2

 

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

переменных x и y- то вопрос остается открытым

 

[scifi 1]

Я понял исходные данные вот так:

X=(a mod k1) mod k2 - частное от деления а на k1*k2

Y = (a mod k1) div k2 - остаток от деления а на k1*k2

Удивительно толкование. И совсем неверное.

Вполне очевидно, что "mod" означает остаток от деления. Как оператор % в языке Си.

Что касается самого вопроса, то мне с моим ограниченным опытом (когда-то прослушал курс лекций по криптографии) кажется, что в общем случае эти операции не упрощаются.

[alexPec 3]

Удивительно толкование. И совсем неверное.

Вполне очевидно, что "mod" означает остаток от деления. Как оператор % в языке Си.

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

 

Я понял исходные данные вот так:

X=(a mod k1) mod k2 - частное от деления а на k1*k2

Y = (a mod k1) div k2 - остаток от деления а на k1*k2

 

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

переменных x и y- то вопрос остается открытым

 

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

(a mod k1) mod k2 совершенно не обязательно равно a mod (k1*k2)

[des00 25]

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

[i-mir 0]

Удивительно толкование. И совсем неверное.

Совершенно верно, и только благодаря этому, я вынудил

топикстартера самому ответить на свой вопрос - нельзя одним

длением получить искомые три переменные

(по крайней мере в рамках кристалла).

 

 

 

[Diusha 0]

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

Изменено 25 мая, 2011 пользователем Diusha

[ViKo 1]

Если k1 не очень большое число (а k2 должно быть еще меньше, естественно), то второе деление можно заменить поиском по таблице, общим размером k1:

[0, 1, 2... k2-1], [0, 1, 2... k2-1], [0, 1, 2... k2-1], ...0, 1, ... (на каком-то числе закончится)

Тогда сначала нужно поделить на k1 и найти остаток, а потом по таблице по этому остатку-индексу найти остаток от деления на k2.