32-битное целочисленное масштабирование без переполнения

Question

Привет У меня есть следующие значения:

uint32_t value = 1230000;
uint32_t max_value = 1234567;

Теперь я бы хотел выполнить масштабирование:

uint32_t scaled = value * 1000000 / max_value;

Проблема в том, что если я использую 32-битное целое число, оно будет переполнено для таких больших чисел. С другой стороны, я не могу использовать 64 бит. Есть идеи, как правильно реализовать упомянутое масштабирование?

EDIT

Просто упомяну, что я работаю над STM32 - 32-битным микроконтроллером, где выполнение 64-битного умножения и деления чрезвычайно затратно. Поэтому я бы хотел их избежать.

Answer 1

Проблема в форме: value/max_1 = x/1000000.

Без решения этой проблемы в закрытом виде, ближайший x может быть вычислен итеративно с помощью деления пополам.

 uint32_t step=max_value>>1;
 uint32_t v=0, x=0, step2=1000000/2 << 12;
 // step2 has been scaled to add extra precision
 while(step) {
    if (value > v+step) { v+=step; x+=step2; }
    step>>=1; step2>>=1;
 }
 x=(x+2048)>>12; // scale down and round

Результат будет завершен за 32 итерации.

Answer 2

Вы можете сделать это, увидев шкалу как число базы-1000: value = value_high*1000 + value_low. Рассчитайте вклад value_high и value_low в масштабированное значение отдельно, сохранив промежуточные значения в виде дроби: scaled = scaled_int + scaled_remainder/max_value

uint32_t value_low = value%1000;
uint32_t value_high = value/1000;
uint32_t scaled_int, scaled_remainder;

uint32_t low = value_low * 1000000;
scaled_int = low / max_value;
scaled_remainder = low % max_value;

scaled_int += value_high * 810;  // pre-calculated 1000*1000000 / max_value
scaled_remainder += value_high * 730;  // pre-calculated 1000*1000000 % max_value
scaled_int += scaled_remainder / max_value;
scaled_remainder = scaled_remainder % max_value;

Кроме того, вам не нужно использовать базу 1000, база 1024 может быть немного быстрее. Пока 4-я, 7-я и 8-я строки не переполняются при максимальном значении, это должно работать.

Answer 3

если ваш переводчик может поддерживать 64 бита, то

uint32_t scaled =(uint32_t)((uint64_t)value * 1000000 / max_value);

если поддержка float, то

uint32_t scaled =(uint32_t)(value *1.0 / max_value* 1000000);

Будет небольшая потеря точности.

Answer 4

Самый быстрый способ масштабирования - использование 2 коэффициентов масштабирования мощности.

Даже если у вас есть два числа, масштабированных с использованием различных масштабных коэффициентов - арифметика тривиальна.

пример:

uint32_t scaledDiv(uint32_t a, uint32_t b, uint32_t *sclef)
{
    *sclef = __builtin_clz(a);
    a <<= *sclef;
    return a/b;
}

Answer 5

вы можете объявить scaled как unsigned long long тип, как показано ниже, а затем сделать явное приведение типа соответственно.

unsigned long long scaled = (unsigned long long)value * 1000000 / max_value; /* make either operand of unsigned long long type explicitly */
printf("%llu\n",scaled);