Здравствуйте!

Использую WinAVR, ATmega88, сигнал синхронизации - внтутренняя RC-цепь (частота 8 МГц).
Необходимо как можно быстрее вычислить значение следующего выражения:

C = Y * C' / 255.
Причём:
C, Y, C' - unsigned char, т. е., действительные числа мне не нужны...

В данный момент вычисления производятся приблизительно за 92 мкс (в программе три выражения подряд).

Можно, конечно, кварц поставить на большую частоту, но хотелось бы пока без него

Фрагмент программы:




Спасибо заранее!

а если поделить на 256? Компилер должен превратить такое деление в сдвиг (или можно руками написать >>8).
Разница будет довольно мала...

А надо делить именно на 255? не на 256?
тогда было бы нужно просто выкинуть младший байт
Критичные ко времени места лучше делать на ассемблере.

Тут засада будет скорее именно в делении. И если от него не избавиться - врядли на асме получится сильно быстрее...

Используйте предварительно посчитанные значения K=M*dmx[0]/255
где М выбирается таким, чтобы получалось то, что делается быстрее, т.е. умножение на К и взятие старшего байта произведения.
асмовый текст, раз уж заговорили про скорость

Надеюсь, принцип понятен.

C=(Y*C1*257) >> 16;

Или совсем уж убыстрить

С2=Y*C1;
C=((C2 << 8)+С2) >> 16;

На асме просто взять два старших байта.

Тогда уж так

C=((unsigned long)Y*C1*257) >> 16;

- у топик стартера Y и С1 - unsigned char

Кстати, классное решение

А то! Но всё-ж-таки, нормальный компилер должен сам типы приводить.

Не могли бы вы пояснить эту мысль? К зависит от двух 1-байтных чисел, объем таблицы получится 65536 байт... Или я вас не так понял?



А кстати, нифига

(С2*257) >> 16 =( (С2 <<8) + C2)>>16 = ((C2<<8)>>16) + (C2>>16) = C2>>8 = C2 / 256 ...

сдвиг на 16 - это ж деление на 65536, а не на 65535

Я обратил внимание на то, что эта часть dmx[0] / 255; должна быть вычислена один раз и больше не участвовать в окончательных выражениях. Таблицей, конечно, не получится
ЗЫ - наверное, автору все-таки нужно сразу делить на 256, потому что разница в 3 промилле, наверняка, не важна.

Вот что нагуглилось: http://www.sharpthinking.net/cv/div255.pdf
Быстрое деление на 255. Вкратце: a/255 = ((a>>8)+a+128)>>8 с округлением к ближайшему целому.

Так и задумывалось, делить на 65536, чтобы был сдвиг на 16 бит, а не деление на 65535.

Вот здесь ошибочка у вас ((C2<<8)>>16) + (C2>>16) = C2>>8+(C2>>16).

Округление можно так сделать C=((C2 << 8)+С2+32768) >> 16;

Человек скорее всего управляет RGB-светодиодом, а деление на 255 - это соответственно "нормализация в восьмибитное число" после умножения на коэффициент яркости. В таком случае, деление на 255 - ошибка. На 256 надо делить, или как выше сказали - взять HIBYTE.

С2 = У * С1

У и С1 - unsigned char, т.е. их произведение <=65535. Сдвиг на 16 влево такого числа даст 0. Поэтому (C2>>16) == 0



Ну просто это получается эквивалентно C2/256. Просто малость замаскировано

Понятно, что на ассемблере быстрее будет работать...
Но я не знаю как сопрячь WinAVR C и ассемблер



К сожалению принцип не понятен пока.
Сколько нужно памяти для предварительно посчитанных значений?



f = dmx[0] / 255 делается действительно 1 раз.
Я вынес эту операцию в другое место.
Теперь делаю только С = C' * f.
Время выполнения сократилось приблизительно на 10 мкс (кстати, я ещё кварц на 20 МГц поставил).
Но хотелось бы ещё побыстрее...




Ими и управляю. Поясню.

Регулирую яркость 8-битным ШИМом микроконтроллера.
Имеем 4 внешних контролла, от которых зависит результирующий цвет луча и его интенсивность.

1 - Общая световая интенсивность dmx[0].
2 - Интенсивность красного n_red.
3 - Интенсивность зелёного n_green.
4 - Интенсивность синего n_blue.

Т. е., моя задача - вычислить значение 8-битного регистра сравнения OCR микроконтроллера, которое зависит от dmx[0] и n_red/n_green/n_blue.

Придумал управлять так:


Но подвело меня деление...

Почему надо делить на 256?
Ясное дело, это сдвиг вправо на 8 - выполняется молниеносно, но почему 256?
Т. е., просто согласиться с появляющейся ошибкой?

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

Сишка:

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


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

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

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

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

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

Вы не правы, это НЕ эквивалентно 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 надеюсь понятен

Вы абсолютно правы - я забыл про исходную постановку задачи и плавно на простое округление.

Действительно, простой расчет .
Но A = [50..52] (как и приведенная мной формула, где А=51)- это для случая деления с отбрасыванием дробной части, т.е для выражения X div 10.

Для деления с округлением, воспользовавшись Вашей методикой, получаем
1.) 0 * 51 +A >= 0
2.) 4 * 51 +A < 1 * 512
3.) 5 * 51 + A >= 1 * 512
4.)254 * 51 + A < 26 * 512
5.)255 * 51 + A >= 26 * 512
- преобразуем
1.) A >= 0
2.) A < 308
3.) A >= 257
4.) A <358
5.) A >= 307

Откуда A = 307.

P.S. Существуют ли алгоритмы для быстрого получения остатка от деления на 10, 100 (кроме варианта X - (X div 10)*10 )?


Здесь A = 1<<8 = 512. При x=11 получаем в результате 2.

Так, что бы во всём диапазоне 0...255 / 10 выполнялось с округлением правильно:

У меня получилось только с множителем >= 205 по формуле (1+(x*205)>>10)>>1

Тоже самое на асме:

Кстати, а что за метод в 11 посте?
Там логика другая...

Кстати, для делимого, находящегося в диапазоне unsigned long деление на 255 как будет выглядеть?

Там используют известное разложение в ряд 1/(1+x) ~ 1-x для x много меньше 1.
Получается
a/(256-1) = a/256 * 1/(1-1/256) ~ a/256 * (1 + 1/256) = (a + a/256)/256,
а 128 там прибавляют для правильного округления до ближайшего целого.