умножение int на 0.9999 без использования float

[Andrey_Kireew]

При расчёте рекурсивного цифрового фильтра удалось получить все целочисленные коэффициенты, кроме одного. Один коэффициент k= 0.99999999999. При его замене на 1 фильтр работает, но становится неустойчивым. Если на вход подать достаточно мощный полезный сигнал - фильтр возбуждается (при отключении источника сигнала, сигнал на выходе фильтра уже не спадает). Моделирование в matlab так же показывает, что для обеспечения устойчивости, этот коэффициент должен быть немного меньше единицы, причём - совсем чуть чуть.

Использовать операции float при реализации на микроконтроллере крайне не желательно, по понятным причинам. Использование
k=0.5 (с реализацией через битовый сдвиг) сводит качество фильтрации на нет.

Пришла такая идея:

Используется синтаксис C

int a=ADCW;   // переменная, умножаемая на коэффициент
int b=a>>10; // вспомогательная gременная b=a/1024

int res=a-b;  // приблизительный результат умножения res~a*0.999
 

Доведя эту идею до логического завершения, можно прийти к выводу, что достаточно проверять старший и знаковый биты в int a,
и по результатам сравнения инкрементировать, или декрементировать, либо не изменять умножаемую переменную.
Для int это будет эквивалентно умножению на 0.999969482421..., что очень даже не плохо, для моего приложения,
и главное, осуществляется это проще, чем через битовые сдвиги

Используется синтаксис C

iint a=ADCW;   // переменная, умножаемая на коэффициент
char* p=(char*)(&a)+1;               // адрес старшего байта a
char mHb=*p & 0b01000000;      //маска старшего бита   

if (*p & 0b10000000)&& (!mHb)   // если знак отрицательный и старший бит 0
                   a++;                         // инкремент
        else
                if mHb
                        a--;                     // декремент

....................................
 

Как Вы думаете, нет ли в моих рассуждениях ошибки? Действительно ли эти операции будут эквивалентны умножению на float 0.9999

[Dmitriy40]

Andrey_Kireew
Вопрос: А ADCW у Вас выравнен вправо или влево? Т.е. число будет 0..1023 или -32768..+32704? В последнем случае достаточно команды

Используется синтаксис C

int a = ADCW;
if (a != 0) if (a < 0) a++; else a--;

Заметьте, никаких магических битовых масок или ориентации на длину чисел в процессоре.

Если же ADCW выравнен вправо и в диапазоне всего лишь 0..1023, то достаточно команды (и тоже без всяких магических масок)

Используется синтаксис C

int a = ADCW;
if (a != 0) a--;

При этом будет странность для ADCW=1, результат после "умножения" обнулится, зато точно меньше исходного. Если обнуление изначально ненулевого значения недопустимо, то можно заменить условие на a > 1.

Ну и зря Вы беззнаковое число (а ADCW обычно беззнаковый, тем более в ATmega8) пишете в знаковую переменную, особенно если выравнивание влево, при увеличении входного сигнала получаете сначала увеличение кода, потом переход через плюс бесконечность и минус бесконечность в сильный минус и дальнейшее увеличение почти до нуля. В таких случаях заметно удобнее unsigned int и код по второму варианту (без проверки на 1, она невозможна). Или даже так если очень надо именно знаковый int

Используется синтаксис C

int a = (unsigned int)ADCW >> 1;
if (a != 0) a--;

[SergeyGubanov]

А так?

Используется синтаксис C

int a = ADCW;
if (a < -1000) {
    a++;
} else if (a > 1000) {
    a--;
}

[Andrey_Kireew]

Тут просто я для примера взял a=ADCW, чтобы не усложнять алгоритм, на самом деле, переменная a заполняется под "завязку", потому что в ней идёт накопление (часть кода убрал, поэтому и непонятно). В общем можно абстрагироваться от специфики ADCW.
То что Вы написали, мне не понятно:
если a не рано нулю и если она отрицательная то увеличиваем на 1, или, если строго положительная, то уменьшаем на 1,
и сами же пишите - если ADCW=1 то она обнулится.

Это совсем не то. Это не умножение на 0.9999 а обнуление последнего разряда. Операция эквивалентная сложению, но никак не умножению. Эффект будет не тот совсем.
Смысл весь в том, чтобы маленькие не трогать, а уменьшать только большие значения. Только тогда эта операция станет эквивалентной умножению. Ну насколько я это понимаю. К примеру, если ADCW=1, то старший разряд нулевой и никаких действий производиться не должно.

-- 25.05.2018, 16:00 --

SergeyGubanov в сообщении #1314856 писал(а):

А так?

Используется синтаксис C

int a = ADCW;
if (a < -1000) {
    a++;
} else if (a > 1000) {
    a--;
}

ну что то типа этого, если изменить пороги сравнения, то получится точно как у меня в последнем коде

Используется синтаксис C

int a = ADCW;
if (a < -16384) {
    a++;
} else if (a > 16384) {
    a--;
}

так как a двухбайтовая, то это будет помедленнее, но всего на 1-2 такта, может даже так и лучше ...

[Dmitriy40]

Ну и во всех случаях умножением на константу это не будет, будет именно что вычитанием константы. И похоже на умножение оно будет лишь для достаточно больших чисел, скажем в верхней трети полного диапазона. А в остальном диапазоне с приближением исходного числа к 0 "умножение" будет на всё более отличный от 1 коэффициент, вплоть до $1-1/128$ для ADCW=2 (из 1023). Для отображения на экране это не страшно, а вот для любой математики нестабильность коэффициента умножения - надо изучать как повлияет.
Если нужна лучшая точность, то переходите на 32-х битную арифметику, тогда погрешность не превысит $1/2^{21}$. Например:

Используется синтаксис C

int32_t a = 0; uint16_t b;
b = ADCW;//Тут для понимания удобнее выравнивание вправо, с диапазоном 0..1023
if (b != 0) a = ((uint32_t)(b << 5) << 16) - (int32_t)b;

В любом случае это гораздо быстрее умножения, хоть плавающего, хоть целочисленного.

-- 25.05.2018, 15:22 --

SergeyGubanov в сообщении #1314856 писал(а):

А так?

Точность всего $1/1000$ ... При -1000<a<+1000 умножения вообще не происходит и коэффициент становится равен строго $1$ что для ТС недопустимо.

Andrey_Kireew в сообщении #1314859 писал(а):

То что Вы написали, мне не понятно:
если a не рано нулю и если она отрицательная то увеличиваем на 1, или, если строго положительная, то уменьшаем на 1,
и сами же пишите - если ADCW=1 то она обнулится.

Что же здесь непонятного, всё в коде видно, это я к тому что предложенное Вами уменьшение на 1 не является именно умножением. Особенно для малых чисел.

Andrey_Kireew в сообщении #1314859 писал(а):

Смысл весь в том, чтобы маленькие не трогать, а уменьшать только большие значения. Только тогда эта операция станет эквивалентной умножению.

Не станет, ведь тогда для маленьких коэффициент станет равен строго $1$ и ваш фильтр сломается как Вы говорите.

-- 25.05.2018, 15:27 --

Andrey_Kireew в сообщении #1314859 писал(а):

Это совсем не то. Это не умножение на 0.9999 а обнуление последнего разряда.

Для положительных чисел - да, для отрицательных - нет: -1001 превратится в -1000, младшие 4 бита у них разные! Именно поэтому и нужна проверка знака, а не просто обнуления младшего бита.

[Andrey_Kireew]

Dmitriy40 в сообщении #1314864 писал(а):

Если нужна лучшая точность, то переходите на 32-х битную арифметику, тогда погрешность не превысит $1/2^{21}$. Например:

Используется синтаксис C

int32_t a = 0; uint16_t b;
b = ADCW;//Тут для понимания удобнее выравнивание вправо, с диапазоном 0..1023
if (b != 0) a = ((uint32_t)(b << 5) << 16) - (int32_t)b;

В любом случае это гораздо быстрее умножения, хоть плавающего, хоть целочисленного.

а что мы получаем возвращаясь в 16 битную арифметику? Вот так то ....
Я вообще подозреваю, что и после преобразования во float ничего другого не получится.

Dmitriy40 в сообщении #1314864 писал(а):

Точность всего $1/1000$ ... При -1000<a<+1000 умножения вообще не происходит и коэффициент становится равен строго $1$ что для ТС недопустимо.

Это не совсем так. Умножение - сохраняет относительную точность, а сложение абсолютную. Так уменьшение больших чисел и сохранение маленьких, это тоже попытка сохранить относительную точность результатов.

Dmitriy40 в сообщении #1314864 писал(а):

Что же здесь непонятного, всё в коде видно, это я к тому что предложенное Вами уменьшение на 1 не является именно умножением. Особенно для малых чисел.

Andrey_Kireew в сообщении #1314859 писал(а):

Смысл весь в том, чтобы маленькие не трогать, а уменьшать только большие значения. Только тогда эта операция станет эквивалентной умножению.

Не станет, ведь тогда для маленьких коэффициент станет равен строго $1$ и ваш фильтр сломается как Вы говорите.

Вот именно, смысл в том чтобы маленькие умножать строго на 1, а большие на 0.999. Смысл в том, что с маленькими числами этого сделать невозможно, при сохранении исходной разрядности, а с большими - можно.

К чему это всё приведёт - вопрос второй, собственно тема и создана для его обсуждения.

Мне вообще представляется так: пока на входе слабый сигнал, фильтр работает с коэффициентом 1. Он вообще так и работает. Так как я опробовал фильтр уже в железе. Как только сигнал возрастает, с определённого предела он немножко ослабляется, и есть надежда, что это предотвратит возбуждение.
Иначе, из за обратной связи амплитуда сигнала всё увеличивается и увеличивается - до бесконечности. А фактически, скорее всего просто происходит переполнение переменных и фильтр уже сам не может вернуться в исходное состояние.

[Dmitriy40]

(Качество оптимизатора WinAVR2010)

Фиговое оно, это качество, когда в результате компиляции

uint16_t b = 11111;
int32_t a = (uint32_t)b << 16;

вижу кусок кода

   ldi r26,lo8(0)
   ldi r27,hi8(0) ;Нафига?!
   mov r26,r24 ;Нафига?!
   mov r27,r25 ;Нафига?!
   clr r25 ;Нафига?!
   clr r24 ;Нафига?!
   sts a,r24
   sts (a)+1,r25
   sts (a)+2,r26
   sts (a)+3,r27

вместо боле оптимального

   clr R26
   sts a,r26
   sts (a)+1,r26
   sts (a)+2,r24
   sts (a)+3,r25

хочется ругаться, причём матом.
При том что код

Используется синтаксис C

uint16_t b;
b = b * 32;

оптимизирован очень даже неплохо, один сдвиг и полдесятка логических операций.

[Andrey_Kireew]

Вообще самая первая идея, которая пришла мне в голову,после наблюдения за работой фильтра - это вообще обнулять все переменные, после приближения их абсолютного значения к некоторому порогу.

Но потом подумал, что не надо так радикально, а достаточно просто при достижении некоторого порога, просто их немножко уменьшать. Так они и никогда не переполнятся, и фильтр будет продолжать работать, может не совсем идеально, но по крайней мере лучше чем после полного обнуления.

А потом уже пришла идея, что это и есть эквивалент умножения на 0.9999 в целочисленной арифметике

[Dmitriy40]

Простите, но вот эти слова

Andrey_Kireew в сообщении #1314835 писал(а):

Один коэффициент k= 0.99999999999. При его замене на 1 фильтр работает, но становится неустойчивым. Если на вход подать достаточно мощный полезный сигнал - фильтр возбуждается (при отключении источника сигнала, сигнал на выходе фильтра уже не спадает). Моделирование в matlab так же показывает, что для обеспечения устойчивости, этот коэффициент должен быть немного меньше единицы, причём - совсем чуть чуть.

я понял так что коэффициент никогда не должен стать равным строго $1$, для любых сигналов на входе. Именно так и пытался сделать.
Если условие другое - описывайте задачу точнее. Не просто "умножение на 0.9999", а с какой точностью, для какой разрядности, какое округление (не)допустимо, ...
Разговор про абсолютную и относительную погрешности имеет смысл только для бесконечной точности представления чисел, при конечно умножение дробных чисел может давать разную относительную погрешность для разных величин чисел (но часто можно оценить погрешность сверху и успокоиться если точности достаточно).

-- 25.05.2018, 16:07 --

Ну то есть задача не умножить целочисленно, а построить фильтр в целочисленной арифметике. И будут ли там умножения или вычитания или вообще XOR-ы - вопрос другой.
Простите, самоустраняюсь, до нормального формулирования задачи.

[Andrey_Kireew]

Ну сдвиг на 16 позиций это 16 операций. Компилятор не догадался, что пора переходить на работу с байтами

-- 25.05.2018, 17:26 --

Формулировка задачи нормальная. Но если нужно - более строго она такова:

Используется синтаксис C

float k=0.9999;
int a=ADCW;

int res=k*a;
 

но это сложно в вычислительном отношении, поэтому, ту же самую операцию можно реализовать так:

Используется синтаксис C

int a = ADCW;
if (a < -16384) {
    a++;
} else if (a > 16384) {
    a--;
}
 

Собственно и вопрос - дадут ли они идентичный результат? я подозреваю, что да, но неуверен

-- 25.05.2018, 17:36 --

Dmitriy40 в сообщении #1314877 писал(а):

Разговор про абсолютную и относительную погрешности имеет смысл только для бесконечной точности представления чисел, при конечно умножение дробных чисел может давать разную относительную погрешность для разных величин чисел (но часто можно оценить погрешность сверху и успокоиться если точности достаточно).

Ну это Вы "загнули". Смысл есть, да ещё какой. Тип int сохраняет абсолютную погрешность, и действительно при умножении, погрешность станет не понять какая, так как операция умножения сохраняет только относительную погрешность. В это смысле умножать желательно переменные float - тогда относительная погрешность результатов будет гарантированной.
Кстати тоже самое, будет при сложении переменных float - не пойми какая погрешность, потому что операция сложения сохраняет абсолютную погрешность, а float - относительную. В int, в общем случае, строго корректно только сложение и вычитание. Тогда гарантирована абсолютная погрешность.

[Dmitriy40]

Andrey_Kireew в сообщении #1314878 писал(а):

Собственно и вопрос - дадут ли они идентичный результат?

Разумеется нет.
Их результаты будут совпадать при числах менее (по модулю) примерно 5000 (и тот и другой оставят число без изменений). От 5000 до 15000 первый уменьшит число на 1, второй оставит без изменений. От 15000 до 16384 первый уменьшит на 2, второй же оставит без изменений. Больше 16384 первый уменьшит на 2 или 3, второй - лишь на 1.
Как видно для чисел больше 5000 совершенно не идентично.
Если хочется совсем уж идентичного результата без умножений и плавающей арифметики, то как-то так:

Используется синтаксис C

if (a > 25000) a --;
if (a > 15000) a --;
if (a > 5000) a --;
if (a < -5000) a++;
if (a < -15000) a++;
if (a < -25000) a++;

И под каждую константу (а не 0.9999) пороги пересчитывать и их количество тоже.

Andrey_Kireew в сообщении #1314878 писал(а):

Ну сдвиг на 16 позиций это 16 операций. Компилятор не догадался, что пора переходить на работу с байтами

Нет, лишь команды пересылки, т.е. догадался.

[Andrey_Kireew]

Dmitriy40 вот об этом я. собственно и спрашивал.
Спасибо! теперь понятно - в идеале надо 3 порога делать. Ну и всё равно быстрее чем через float получится

[Dmitriy40]

На ассемблере ещё можно умножить на 16 бит константу $65536\cdot0{,}9999$ со взятием старших 16 битов произведения, будет сравнимо по скорости, но морочиться со знаками. На С же я советовать такое не буду, неизвестно во что превратится умножение (да и нет обычно операций умножения 16х16 со взятием лишь старших 16 битов результата), конечно на порядки быстрее float, но может оказаться в разы медленнее полдесятка if. Зато намного универсальнее.

[realeugene]

Andrey_Kireew в сообщении #1314835 писал(а):

Один коэффициент k= 0.99999999999

$k=1 - 0.00000000001$. Подставьте и преобразуйте вашу расчётную формулу. Не думаю, что вам нужно, чтобы этот коэффициент был точный. Скорее всего, он нужен слегка меньше единицы, чтобы исправить погрешности округления других ваших коэффициентов.

[realeugene]

А вообще, ТС стоит прочитать Оппенгейм, Шафер "Цифровая обработка сигналов".