alexPec 3 19 мая, 2011 Опубликовано 19 мая, 2011 · Жалоба Добрый день. Возникла задача, под которую у меня мозг не заточен, если не ошибаюсь, из математики конечных полей. Господа математики, подскажите, можно ли вычислить одним делением X и Y: X=(a mod k1) mod k2 Y = (a mod k1)/k2 k1, k2 - константы, 16 бит. а- переменная, 32 бит. Нужна аппаратная реализация этого, если в лоб - два делителя подряд - задержка большая, скорость снижается, да и ресурсов делитель немало ест. Нужна реализация с одним делителем + умножители и сумматоры/вычитатели если нужно. Спасибо! Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Сергей Борщ 134 19 мая, 2011 Опубликовано 19 мая, 2011 · Жалоба Или я чего-то не понимаю, или X и Y - это остаток и частное от деления a mod k1 на k2, т.е. получаются одновременно в процессе деления на k2. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Xenia 43 19 мая, 2011 Опубликовано 19 мая, 2011 · Жалоба Добрый день. Возникла задача, под которую у меня мозг не заточен, если не ошибаюсь, из математики конечных полей. Господа математики, подскажите, можно ли вычислить одним делением 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 20 мая, 2011 Опубликовано 20 мая, 2011 · Жалоба Нужна аппаратная реализация этого, если в лоб - два делителя подряд - задержка большая, скорость снижается, да и ресурсов делитель немало ест. Нужна реализация с одним делителем + умножители и сумматоры/вычитатели если нужно. Делимое/делитель дают частное и остаток от деления. Возможно, Вам нужны и частное, и остаток вместе.... Аппаратная реализация для этого - это матрица элементов, например в а.с. 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 20 мая, 2011 Опубликовано 20 мая, 2011 · Жалоба Делимое/делитель дают частное и остаток от деления. Возможно, Вам нужны и частное, и остаток вместе.... Аппаратная реализация для этого - это матрица элементов, например в а.с. 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 20 мая, 2011 Опубликовано 20 мая, 2011 · Жалоба Напишу то же самое от себя... Поясню подробней x и y - да, остаток и частное от деления. Использую алтеровскую мегафункцию деления, она дает одновременно частное и остаток от деления. Но проблема в том, что сначала первым делителем надо найти a mod k1, а вторым уже x и y ( функция вычисляет частное и остаток одновременно). Так вот как-то может преобразовать выражение чтоб операция деления и (или) остатка от деления была одна, предпочтительнее вместо второй операции деления использовать несколько (может быть) умножений и сложений/вычитаний. Т.е вторая операция деления - это уже край. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
i-mir 0 23 мая, 2011 Опубликовано 23 мая, 2011 · Жалоба Не совсем понятно что у вас за проблема. Не укладываетесь в максимальное время цикла? И эти два деления являются самыми проблемными из всей цепочки? Тогда: 1. Напишите свою простенькую процедуру деления одновременно двух делимых - задача тривиальная 2. Или в начале умножьте k1*k2, а потом делите штатной функцией - получите два искомых значения Но честно - я бы просмотрел все остальное и попробовал оптимизировать там. Не верится что ресурсы кристалла уже вами использованы на 95% и все уперлось здесь. Посмотрите тайм-ауты и другие цепочки использующие время. Если критичным осталось именно деление, то это вершина оптимального кодирования под заданный кристалл. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
ViKo 1 24 мая, 2011 Опубликовано 24 мая, 2011 · Жалоба Не совсем понятно что у вас за проблема. ... 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 24 мая, 2011 Опубликовано 24 мая, 2011 · Жалоба Вопрос как обычно звучит так - чего хочет топикстартер? :) Поясню подробней x и y - остаток и частное от деления. Я понял исходные данные вот так: X=(a mod k1) mod k2 - частное от деления а на k1*k2 Y = (a mod k1) div k2 - остаток от деления а на k1*k2 Но судя по тому что автор дал взаимоисключающие толкования переменных x и y- то вопрос остается открытым Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
scifi 1 24 мая, 2011 Опубликовано 24 мая, 2011 · Жалоба Я понял исходные данные вот так: X=(a mod k1) mod k2 - частное от деления а на k1*k2 Y = (a mod k1) div k2 - остаток от деления а на k1*k2 Удивительно толкование. И совсем неверное. Вполне очевидно, что "mod" означает остаток от деления. Как оператор % в языке Си. Что касается самого вопроса, то мне с моим ограниченным опытом (когда-то прослушал курс лекций по криптографии) кажется, что в общем случае эти операции не упрощаются. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
alexPec 3 24 мая, 2011 Опубликовано 24 мая, 2011 · Жалоба Удивительно толкование. И совсем неверное. Вполне очевидно, что "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 25 мая, 2011 Опубликовано 25 мая, 2011 · Жалоба никак, делайте два деления на одном блоке %) Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
i-mir 0 25 мая, 2011 Опубликовано 25 мая, 2011 · Жалоба Удивительно толкование. И совсем неверное. Совершенно верно, и только благодаря этому, я вынудил топикстартера самому ответить на свой вопрос - нельзя одним длением получить искомые три переменные (по крайней мере в рамках кристалла). Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Diusha 0 25 мая, 2011 Опубликовано 25 мая, 2011 (изменено) · Жалоба 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 26 мая, 2011 Опубликовано 26 мая, 2011 · Жалоба Если k1 не очень большое число (а k2 должно быть еще меньше, естественно), то второе деление можно заменить поиском по таблице, общим размером k1: [0, 1, 2... k2-1], [0, 1, 2... k2-1], [0, 1, 2... k2-1], ...0, 1, ... (на каком-то числе закончится) Тогда сначала нужно поделить на k1 и найти остаток, а потом по таблице по этому остатку-индексу найти остаток от деления на k2. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться