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

Question

Я пишу код для микропроцессора с быстрой целочисленной арифметикой и не такой быстрой плавающей арифметикой. Мне нужно разделить целое число на число от 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 бита результата.

То, что вы здесь делаете, на самом деле является формой арифметики с фиксированной запятой. Посмотрите статью Википедии для получения дополнительной информации.

Answer 2

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

Answer 3

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

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

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

Хитрый бит начинается здесь:

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

Допустим, у вас есть 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.

Опять же, давайте выберем случайное число 20 000/7: 20 000, умноженное на 9 363, равное 187 260 000, и, когда вы сдвинете вправо эти 16 битов, вы получите 2857 - реальный результат - 2857.

В следующей тестовой программе на 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