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

[alexPec]

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

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

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

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

Спасибо!

[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