| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Как в целочисленной арифметике / заменить * |
| Автор: ANTON_AL 16.11.2007, 18:34 |
| Доброго дня! Я пишу JPEG кодек, который повязан на целочисленной арифметике. На стадии квантования требуется разделить каждый член блока 8x8 на коэффициент квантования. Этот этап и породил сию тему. Задача: есть целое число, например 140, его надо разделить на другое число, например 7 и получить соответственно 20. Надо найти некое число R (эквивалент 1/7), умножив которое на 140 мы получим 20(т.е. результат "деления") 140 * R = 20; ( R - ? ). Числа представлены в бинарном виде, и они целые. Разрядность - 16 бит. Ещё раз в бинарном виде: 10001100 / 111 = 10100 А надо так: 10001100 * R = 10100; R - ? |
| Автор: maxim1000 16.11.2007, 18:47 |
| тут в пределах 16 бит, наверное, не получится... |
| Автор: ANTON_AL 16.11.2007, 18:48 |
| Язык C++. Но дело не в нём, я использую SSE2, а там нет операции деления, есть только умножение. |
| Автор: maxim1000 16.11.2007, 18:50 |
| если, конечно, числа могут занимать все 16 бит если у нас 8-битные числа, и допустима 16-разрядная арифметика, то можно так: x/y=x*(1/y)=x*(A/y)/A вместо A можно взять степень двойки заранее посчитать A/y а при вычислении x*(y/A)/A деление на A заменять сдвигом |
| Автор: stab 17.11.2007, 02:03 | ||
Для 7 тогда максимум точности без переполнений даст 146 / 1024, но ошибка уже в четвёртом знаке будет. Ещё тонкий момент со знаками, так что осторожно надо сдвигать. |
| Автор: maxim1000 17.11.2007, 12:15 |
| не уверен, что получится найти множитель, который давал бы точный результат деления... |
| Автор: stab 17.11.2007, 23:09 |
| maxim1000, если арифметику на 32 бита перевести для байтовых операндов, то 9586981 / 67108864 (2^26) даёт уже неплохой результат с ошибкой только в девятом знаке. |
