Перейти к содержанию
    

Одним делением вычислить два

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

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

 

X=(a mod k1) mod k2

Y = (a mod k1)/k2

 

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

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

 

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

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

 

Спасибо!

 

 

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

Господа математики, подскажите, можно ли вычислить одним делением 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.

post-14377-1305868569_thumb.jpg

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

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

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

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

 

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

...

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).

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

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

 

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

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

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

 

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

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

 

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

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

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

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

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

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

Вполне очевидно, что "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)

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

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

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

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

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

 

 

 

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

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

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Присоединяйтесь к обсуждению

Вы можете написать сейчас и зарегистрироваться позже. Если у вас есть аккаунт, авторизуйтесь, чтобы опубликовать от имени своего аккаунта.

Гость
К сожалению, ваш контент содержит запрещённые слова. Пожалуйста, отредактируйте контент, чтобы удалить выделенные ниже слова.
Ответить в этой теме...

×   Вставлено с форматированием.   Вставить как обычный текст

  Разрешено использовать не более 75 эмодзи.

×   Ваша ссылка была автоматически встроена.   Отображать как обычную ссылку

×   Ваш предыдущий контент был восстановлен.   Очистить редактор

×   Вы не можете вставлять изображения напрямую. Загружайте или вставляйте изображения по ссылке.

×
×
  • Создать...