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

[alexPec]

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

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

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

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

Спасибо!

[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]

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

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