Я ж говорю 256/255 = 1.0039 Точнее - 4 промилле.

Сишка:

Добавляете в проект файл fast_out.S


Уже в таком виде должно собраться.
В данном примере precomputed - это Ваше С'
Но, скорее всего, Вам придется эту часть, с предварительными вычислениями тоже в асм внести.
Успехов!

В догонку.
Деление на 255 в данном случае можно заменить делением на 256 и учетом одного исключения:

Просьба не воспринимать это как сишный текст

И как паскалевский, и как ассемблерный... ясен перец

За быстрое деление на 255 - всем спасибо.
Работает. Быстро работает

Сообщение отредактировал n_bogoyavlensky - Dec 3 2008, 09:47

Вы не правы, это НЕ эквивалентно C2/256, это примерно эквивалентно C2/257. Судите сами, C2/255 = C2/(65536/257)=С2*257/65536=(С2*257)>>16. А примерно эквивалентно потому, что вы делите на 65536/257=255.0039, а не точно на 255.

Что касается вашей формулы (С2*257) >> 16 =( (С2 <<8) + C2)>>16 = ((C2<<8)>>16) + (C2>>16) = C2>>8 = C2/256, то она неверна. Два слагаемых перекрываются на 8 бит, и меньшее слагаемое нельзя просто отбросить, поскольку при суммировании оно может дать перенос в старший байт, который и будет окончательным результатом.

Вот пример. Пусть С2=0x8899=34969, тогда C2*256=0x889900,
C2*257=C2*256+C2=0x889900+0x8899=0x892199
и, наконец, С=C2*257>>16=0x89=137. Простая проверка: С=34969/255=137.1

По вашей формуле С=С2>>8=0x88=136

Вывод такой. Если хотите поделить на 255, то лучше делить на 255.0039, чем на 256. Всяко точнее будет. Вообще такой подход хорош при делении на константу.

Вот ещё одна задача.
Как аналогичным образом целочисленно поделить одно 8-битное число на другое 8-битное число?
Более конкретно - деление на 10.

Дык все точно так же,
умножте на 26(~256/10) или на 6554(~65536/10) ну и если нужно скоректируйте...

Для диапазона A=[0..255): (unsigned char)(А+1)*51>>9

Для диапазона A=[0..255] ((unsigned char)(А*51) + 51)>>9

или на асме соответственно

Спасибо!
Кстати, откуда вы с такой лёгкостью извлекаете эти волшебные выражения?
Они где-то перечислены или их можно достаточно просто придумать самому? Каков принцип?

А для диапазона A=[0..65535]?




Всмысле?
Что умножить и как скорректировать?

Именно так как в посте №21

51 ~= 256 * 2 / 10

+ 51 корректировка

Всё равно пока не пойму каков принцип?

x/10 = x*(1/10) = x*(205/2048) = (x*205)>>11
x/10 = x*(1/10) = x*(52429/524288) = (x*52429)>>19

x/10 ~= x*51/512 = (x*51)>>9
или x/10 ~= x*26/256 = (x*26)>>8
или ...
подберите что-нибудь, устраивающее по точности.
Для корректного целочисленного округления все-таки д.б. ((x*51)+51/2)>>9 ~= ((x*51)+26)>>9

Дык, a/b преобразуется в a*(N/b) / N, при подходящем выборе N (степень двойки) выражение N/b вычисляется ещё на этапе компиляции, а умножение и последующее деление на N (сдвигами или отбрасыванием младших байтов результата) выполняется быстрее чем просто деление на b, особенно при наличии аппаратного умножителя.

Добавлю ещё, что если b не константа то подобный метод тоже срабатывает - есть достаточно эффективные алгоритмы вычисления 1/b (или N/b). Всё из-за того, что аппаратный делитель выходит заметно сложнее умножителя, вот на нём и экономят, даже в суперкомпьютерах.

С делением теперь понятно. Спасибо
С округлением до ближайшего целого не понятно...

Спасибо, был неправ. Вместо
((x*51) + 51/2) >> 9 ~= ((x*51)+26)>>9
читать
((x*51) + 1<<8) >> 9 = (x*51)>>9 + 0.5

Правила округления до целого предполагают, что (н-р, применительно к десятичной системе счисления) если дробная часть = [0.0..0.4(9)], то число округляется "вниз" (дробная часть просто отбрасывается), если дробная часть = [0.5..0.9(9)], то число округляется "вверх" (дробная часть отбрасывается, к целой части добавляется 1).
Контроллер при целочисленных операциях может только отбросить дробную часть. Чтобы заставить его округлять "по-человечески", нужно перед целочисленными операциями с потерей точности (типа деление/сдвиг) добавить к операнду половину разряда, который станет младшим значащим разрядом после выполнения операции (== половину делителя).

Округляем до целого в десятичной системе:
половина значащего разряда = 0.5
trunc(31.49 + 0.5) = 31
trunc(31.5 + 0.5) = 32

Округляем до целого в двоичной системе:
пусть 0b10100101 (= 165 дес.) хочется сдвинуть вправо на 3 разряда
половина делителя = 1 << (3 - 1) = 0b100
0b10100101 >> 3 = 0b10100 (= 20 дес.)
(0b10100101 + 0b100) >> 3 = 0b10101 (= 21 дес.)
165/8 = 20.625 ~= 21

на самом деле рассчет коррекции проще всего делать так:
- пример с домножением на 51
- пусть коррекция = A, те ((x * 51) + A) / 512 ~= x / 10
- тогда д.б.:
1.) 0 * 51 +A >= 0
2.) 9 * 51 +A < 1 * 512
3.) 10 * 51 + A >= 1 * 512
4.)250 * 51 + A >= 25 * 512
5.)255 * 51 + A < 26 * 512
- преобразуем
1.) A >= 0
2.) A < 53
3.) A >= 2
4.) A >= 50
5.) A < 307

-итого: 50<= A < 53

то есть нам подойдут 50, 51, 52

выбор чисел 0, 9, 10, 250, 255 надеюсь понятен