Знаковое деление с беззнаковым числителем

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

unsigned int AverageUsage;
unsigned int TotalUsage;
unsigned int incCount;

    AverageUsage = (TotalUsage - AverageUsage)/++incCount + AverageUsage;

Среднее использование всегда будет положительным, но когда общее использование упадет ниже среднего, я не уверен, чего ожидать от деления.

    AverageUsage = (signed int)(TotalUsage - AverageUsage)/++incCount + AverageUsage;

Установит числитель со знаком, но я не уверен, как будет происходить деление.

    AverageUsage =  (signed int)((signed int)(TotalUsage - AverageUsage)/++incCount) + AverageUsage;

Должен работать (я могу гарантировать, что результат этой полной операции никогда не будет отрицательным), но меня беспокоят случаи, когда значение incCount достигает значения, которое «выглядит» отрицательным.

Есть ли простое решение для этого, которое, надеюсь:

  • Не нуждается в операторе if
  • Не требует QWORD

Спасибо!


c signed embedded
person Gdogg    schedule 27.05.2011    source источник
comment
Было бы полезно, если бы вы включили объявление всех этих переменных. Правила продвижения C зависят от типов различных подвыражений. Например, является ли AverageUsage целым числом? беззнаковое целое? короткое без подписи? и Т. Д.   -  person Nemo    schedule 28.05.2011
comment
Я с подозрением отношусь к этому коду; Вы уверены, что это арифметически правильно и вычисляет скользящее среднее, а не кумулятивное среднее? Для скользящего среднего потребуется буфер последних значений.   -  person Clifford    schedule 28.05.2011
comment
@Клиффорд. Это базовый IIR. Вы, вероятно, думаете о FIR-интеграторе; что эквивалентно среднему значению статистической выборки (бег/катка). Несмотря на это, они оба верны; как фильтры нижних частот и аппроксимации среднего значения населения.   -  person Tyson Hilmer    schedule 11.09.2017

Ответы (5)


arrow_upward
4
arrow_downward

У вас есть 2 варианта.

Использовать вычисления с плавающей запятой

Я думаю, вы хотите сделать это, чтобы получить правильное среднее значение в любом случае.

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

Знаковый или беззнаковый числитель или знаменатель не имеет значения. Не существует такой вещи, как беззнаковая плавающая точка. Знаменатель incCount будет преобразован в число с плавающей запятой, и будет выполнено полное деление с плавающей запятой.

Используйте целочисленное деление и обрабатывайте особые случаи

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

И числитель, и знаменатель подписаны

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

И числитель, и знаменатель без знака

Вы должны сделать числитель беззнаковым и использовать оператор if() для обработки двух случаев: TotalUsage < AverageUsage и TotalUsage > AverageUsage. Здесь incCount может использовать весь диапазон целочисленных битов, поскольку он будет рассматриваться как число без знака.

person Himadri Choudhury    schedule 27.05.2011
comment
Ок имеет смысл. Мне нужно целочисленное деление, поскольку я отслеживаю использование памяти (в байтах), которое почти всегда будет в диапазоне 50+ МБ. Доли байтов не беспокоят. Я также работаю над ARM без FPU. - person Gdogg; 28.05.2011

arrow_upward
5
arrow_downward

Общее правило бинарных операций C (включая деление) заключается в том, что оба операнда будут преобразованы в один и тот же тип, который является одним из: int, unsigned int, long, unsigned long, intmax_t, uintmax_t, float, double, long double. Если оба операнда относятся к типам из этого списка, они оба будут преобразованы в более поздний тип. Если нет, они оба будут преобразованы в int.

Итак, в вашем примере:

AverageUsage = (signed int)(TotalUsage - AverageUsage)/++incCount + AverageUsage

если incCount равно unsigned int, то ваше приведение не имеет никакого эффекта - вычитание будет преобразовано в целое число со знаком, а затем обратно в целое число без знака, и будет выполнено беззнаковое деление. Если вы хотите подписанное подразделение, вам понадобятся:

AverageUsage = (int)(TotalUsage - AverageUsage)/(int)++incCount + AverageUsage

что, как вы заметили, может вызвать у вас проблемы, если incCount превысит INT_MAX.

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

person Chris Dodd    schedule 27.05.2011

arrow_upward
1
arrow_downward

Обратите внимание, конечно, что это не стандартный средний показатель. Стандартный средний показатель будет таким:

Averageusage = TotalUsage / ++incCount

Предполагая (в идеале), что incCount является некоторым полезным периодически увеличивающимся значением (например, секундами).

Затухание среднего значения обычно реализуется примерно так: 03%20Decay%20Ave/032.htm, если я правильно перевел:

AverageUsage = TotalUsage / (incCount+1) + incCount/(incCount+1) * AverageUsage;
incCount++;

Как упомянул Химадри, это, вероятно, следует делать в арифметике с плавающей запятой.

person Seth Robertson    schedule 27.05.2011
comment
Я пытался свести к минимуму необходимое количество дивизий. Моя формула является упрощением вашей. - person Gdogg; 28.05.2011
comment
@Gdogg: Если у вас нет экспериментальных данных, свидетельствующих о том, что это горячая точка, я настоятельно рекомендую вам выполнять преждевременную оптимизацию. Использование правильного стандартного алгоритма сделает ваших пользователей более счастливыми, поскольку он правильно отражает то, что люди ожидают, когда видят среднее значение. - person Seth Robertson; 28.05.2011
comment
Упрощение касается не только производительности. Ваше выражение этого плохо ломается на практике; (incCount/(incCount+1)) всегда равно нулю в целочисленной арифметике. Если вы переставите (incCount*AverageUsage)/(incCount+1), вы рискуете переполниться в числителе. - person Brooks Moses; 28.05.2011
comment
@Brooks Moses: я думаю, вы обнаружите, что я предложил использовать арифметику с плавающей запятой. - person Seth Robertson; 28.05.2011
comment
Я думаю, что TotalUsage здесь представляет собой текущую выборку, и в этом случае версия @Gdogg является стандартным средним значением, как и ваше (убывающее среднее значение будет использовать фиксированное значение вместо incCount - см. раздел B статьи, на которую вы ссылаетесь). Но ваша версия должна использовать числа с плавающей запятой - вряд ли! Даже в этом случае версия @Gdogg более стабильна в числовом отношении, она является достаточно правильной и стандартной, чтобы ее можно было найти в книге Кнута «Искусство компьютерного программирования», том 2 (уравнение (15) на стр. 232 3-го издания; метод приписывается Уэлфорду (1962). )). - person Matthew Slattery; 28.05.2011

arrow_upward
0
arrow_downward

Если это предсказуемо и допустимо для TotalUsage ‹ AverageUsage, то совершенно неуместно, чтобы эти переменные имели беззнаковый тип. TotalUsage ‹ AverageUsage будет означать, что AverageUsage может быть отрицательным (что было бы результатом, если TotalUsage ‹ AverageUsage. Если «усредняемые» данные никогда не бывают отрицательными, то TotalUsage ‹ AverageUsage арифметически невозможно быть истинным.

Если TotalUsage ‹ AverageUsage недействителен, то его истинность будет означать ошибку в вашем коде или арифметическое переполнение. Вы можете защититься от такой возможности с помощью assert; возможно, один из них реализован как макрос, который удаляется в сборке релиза. Если происходит утверждение, то либо входные данные были недействительны, либо произошло переполнение, в последнем случае тип данных слишком мал, и подходящим будет long long, unsigned long long или double.

Даже при приведении, если TotalUsage ‹ AverageUsage имеет значение true, результат выражения будет арифметически отрицательным, но в конечном итоге присваивается беззнаковому типу, поэтому результат все равно будет неверным.

Окончательный вывод состоит в том, что либо TotalUsage ‹ AverageUsage никогда не может быть истинным, либо ваши данные имеют неподходящий тип. Решение почти наверняка не в каком-либо типе.

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

person Clifford    schedule 28.05.2011

arrow_upward
0
arrow_downward

Вам действительно /нужно/ скользящее среднее, или вы можете использовать какой-то другой фильтр нижних частот? Вам может подойти однополюсный (иногда называемый «альфа») фильтр:

new_output = alpha * previous_output + (1-alpha)*new_input;
previous_output = new_output;

где alpha находится в диапазоне от 0 до 0,9999....

Чем ближе alpha к 1, тем "медленнее" фильтр

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

person Martin Thompson    schedule 28.05.2011