Одним делением вычислить два, можно ли? Опции

[alexPec]

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

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

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

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

Спасибо!

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

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

[Xenia]

Добрый день. Возникла задача, под которую у меня мозг не заточен, если не ошибаюсь, из математики конечных полей.
Господа математики, подскажите, можно ли вычислить одним делением 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/

[Волощенко]

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

Делимое/делитель дают частное и остаток от деления. Возможно, Вам нужны и частное, и остаток вместе....
Аппаратная реализация для этого - это матрица элементов, например в а.с. 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]

Делимое/делитель дают частное и остаток от деления. Возможно, Вам нужны и частное, и остаток вместе....
Аппаратная реализация для этого - это матрица элементов, например в а.с. 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]

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

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

[i-mir]

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

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

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

[ViKo]

Не совсем понятно что у вас за проблема.
...
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]

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

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

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

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

[scifi]

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

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

[alexPec]

Удивительно толкование. И совсем неверное.
Вполне очевидно, что "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]

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

[i-mir]

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

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

[Diusha]

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

[ViKo]

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

[alexPec]

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

Не, таблица не вариант, памяти в обрез

[Diusha]

Не, таблица не вариант, памяти в обрез

Так а чем умножение на константу вместо деления на константу не устраивает?

[ViKo]

Так а чем умножение на константу вместо деления на константу не устраивает?

Видимо, тем, что придется умножить на 1/k, затем из результата вычесть целую часть, оставить дробную, затем дробную умножить на k. Так получится остаток от деления на k.
P.S. Возможно, смайлик я поставил зря.

[Diusha]

Видимо, тем, что придется умножить на 1/k, затем из результата вычесть целую часть, оставить дробную, затем дробную умножить на k. Так получится остаток от деления на k.

Ну да, примерно так, но не совсем.
Умножить на (65536 div k) (целая константа), выкинуть (просто игнорировать) 2 мл. байта – и частное готово. Для получения остатка нужно еще одно умножение и одно вычитание. И соответственно вместо второго деления тоже 2 умножения и одно вычитание. Все в целых числах.
По-моему, этим должно не не_устраивать, а как раз устраивать , ибо

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

чтоб операция деления и (или) остатка от деления была одна, предпочтительнее вместо второй операции деления использовать несколько (может быть) умножений и сложений/вычитаний. Т.е вторая операция деления - это уже край.

Конечно, из слов автора буквоед может сделать вывод, что непременно должно быть одно и только одно деление, но мы же не такие
Хотя и в этом случае – пожалуйста: одно деление «честное», а вместо второго – как я сказал

Сообщение отредактировал Diusha - May 28 2011, 04:18

[ViKo]

... но мы же не такие

Мы не такие
Как не-буквоеды мы можем сказать - что-то нечисто в самой постановке задачи. Оно точно такое надо?

[alexPec]

Мы не такие
Как не-буквоеды мы можем сказать - что-то нечисто в самой постановке задачи. Оно точно такое надо?

Спасибо за ответы, попробую.
Да, и оно точно так надо.

[i-mir]

Вот интересен например сам факт задачи, где топикстартер
утверждает, что у него ресурсов хватает на одно деление и
там пару умножений, но никак не на два деления.
Но если уж из железа вытянули все что можно - то это
признак некорректной имплементации и такой проект
может не иметь будущего даже если вы засунете два
последних умножения в кристалл как предлагается.

Когда в свое время было мало ПЗУ и еще меньше ОЗУ на
борту 8-ми битного железа, то все делали на целочисленной
арифметике подогнанной под границы 2^n ... заменяли
все что можно сдвигами - и получали неплохие результаты.

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

[singlskv]

Видимо, тем, что придется умножить на 1/k, затем из результата вычесть целую часть, оставить дробную, затем дробную умножить на k. Так получится остаток от деления на k.

А если повезет с числами k1 и k2, то и этого не нужно будет
ТС, так какие там у Вас числа k1 и k2 ?

[alexPec]

А если повезет с числами k1 и k2, то и этого не нужно будет
ТС, так какие там у Вас числа k1 и k2 ?

k2 = {2,4,6}
k1 - 27 значений может принимать, ну вот некоторые: 4024, 4650, 4482, 3776, 2832.

[singlskv]

k2 = {2,4,6}
k1 - 27 значений может принимать, ну вот некоторые: 4024, 4650, 4482, 3776, 2832.

ну тогда первое получение (а mod k1) таки честное деление
ну а деление на {2,4,6} с остатком это жеж совсем просто,
для 2 и 4 все совсем очевидно,
для 6 решается ну совсем простым домножением