Быстрое умножение

Question

Я пишу код для микропроцессора с быстрой целочисленной арифметикой и не так быстро float arithmetic. Мне нужно разделить целое число на число от 1 до 9 и преобразовать результат обратно в целое число.

Я сделал массив с плавающей точкой с элементами типа 0, 1, 0.5, 0.3333 и т. Д. Но я думаю, что есть числа MAGIC (например, 0x55555556) для чисел, кроме (1/3).

Что это за цифры?

Answer 1

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

Если ваша инструкция деления не достаточно быстрая, но инструкция умножения есть, вы можете использовать следующую технику (и это звучит так, как если бы это была ваша техника). В большинстве архитектур умножение 32-битного числа на другое 32-битное число приводит к 64-битовому результату; более значительная половина хранится в одном регистре, а менее значительная половина хранится в другом регистре. Вы можете воспользоваться этим, осознав, что деление на число n такое же, как умножение на (2^32)/n, а затем принятие более значительных 32 бит результата. Другими словами, если вы хотите разделить на 3, вы можете вместо этого умножить на 0x100000000/3 = 0x55555555, а затем взять более значимые 32 бита результата.

Что вы здесь делаете, это действительно форма арифметики с фиксированной точкой. Взгляните на Wikipedia article для получения дополнительной информации.

Answer 2

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

Хороший старт делится на 2, 4 и 8. Это можно сделать с правыми сдвигами в 1, 2 и 3 бит соответственно, предполагая, что ваш процессор имеет логическую инструкцию сдвига вправо.

Во-вторых, деление на 1 - это просто сохранение числа как есть. Это просто уходит, 3, 5, 6, 7 и 9.

Tricky бит начинается здесь:

Для других номеров, вы можете использовать тот факт, что разрыв может быть заменен многосвязной и в смене ,

Предположим, у вас есть 16-разрядный процессор. Для того, чтобы разделить на N, умножить на 256/N и сдвиг вправо 8 бит:

N = 3, multiply by 85 
N = 5, multiply by 51 
N = 6, multiply by 43 
N = 7, multiply by 37 
N = 9, multiply by 28 

Возьмем случайный пример 72/5. Умножить 72 на 51, чтобы получить 3672, то сдвиг вправо 8 бит, чтобы получить 14.

Для того, чтобы это работало, ваши номера, которые вы используете, не должны переполнять 16 бит. Так как ваш худший случай умножить-на-85, вы можете обрабатывать числа до 771.

Причина это работает, потому что сдвиг-вправо 8 бит так же, как деление на 256, а также:

m * (256/n)/256 
= m/(n/256)/256 
= m/n * 256/256 
= m/n * (256/256) 
= m/n 

Если у вас есть 32-битный процессор, значения и диапазоны несколько изменяются, так как это 65536/N:

N = 3, multiply by 21,846, right shift 16 bits, max value roughly 196,600. 
N = 5, multiply by 13,108. 
N = 6, multiply by 10,923. 
N = 7, multiply by 9,363. 
N = 9, multiply by 7,282. 

Опять же, давайте выберем случайное 20000/7: 20000, умноженное на 9,363 является 187260000 и, когда вы правы сдвигаете эти 16 бит, вы получаете 2,857 - реальный результат составляет 2,857.

Следующая тестовая программа на C показывает значения точности для указанных значений. Он использует подписанные значения, поэтому он хорош только до 98 000, но вы можете видеть, что наибольшая ошибка равна 1 и что она встречается в нижней точке 13,110 (только ошибка 0.008%).

#include <stdio.h> 
int res[5] = {0}; 
int low[5] = {-1,-1,-1,-1,-1}; 
int da[] = {3,5,6,7,9}; 
int ma[] = {21846,13108,10923,9363,7282}; 
int main (void) { 
    int n, i; 
    for (n = 0; n < 98000; n++) { 
     for (i = 0; i < sizeof(da)/sizeof(da[0]); i++) { 
      int r1 = n/da[i]; 
      int r2 = (n * ma[i])>>16; 
      int dif = abs (r1-r2); 
      if (dif >= 5) { 
       printf ("%d/%d gives %d and %d\n", n, da[i], r1, r2); 
       return 1; 
      } 
      res[dif]++; 
      if (low[dif] == -1) { 
       low[dif] = n; 
      } 
     } 
    } 
    for (i = 0; i < sizeof(res)/sizeof(res[0]); i++) { 
     printf ("Difference of %d: %6d, lowest value was %6d\n", i, res[i], low[i]); 
    } 
    return 0; 
} 

Это выходы:

Difference of 0: 335874, lowest value was  0 
Difference of 1: 154126, lowest value was 13110 
Difference of 2:  0, lowest value was  -1 
Difference of 3:  0, lowest value was  -1 
Difference of 4:  0, lowest value was  -1 

Answer 3

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