Какой самый быстрый способ делить целое число на 3?

Question

int x = n / 3;  // <-- make this faster

// for instance

int a = n * 3; // <-- normal integer multiplication

int b = (n << 1) + n; // <-- potentially faster multiplication

Answer 1

Парень, который сказал "оставь это компилятору", был прав, но у меня нет "репутации", чтобы модифицировать его или комментировать. Я попросил gcc скомпилировать int test (int a) {return a / 3; } для ix86, а затем разобрал вывод. Просто для академического интереса, то, что он делает, это примерно , умножая на 0x55555556 и затем беря верхние 32 бита 64-битного результата. Вы можете продемонстрировать это себе, например:

$ ruby -e 'puts(60000 * 0x55555556 >> 32)'
20000
$ ruby -e 'puts(72 * 0x55555556 >> 32)'
24
$ 

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

Answer 2

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

int a;
int b;

a = some value;
b = a / 3;

Answer 3

Существует более быстрый способ сделать это, если вы знаете диапазоны значений, например, если вы делите целое число со знаком на 3 и знаете, что диапазон значения, которое нужно разделить, составляет от 0 до 768, то вы можно умножить его на коэффициент и сдвинуть влево на степень 2 к этому коэффициенту, деленному на 3.

например.

Диапазон 0 -> 768

вы можете использовать сдвиг 10 битов, который умножая на 1024, вы хотите разделить на 3, чтобы ваш множитель был 1024/3 = 341,

, так что теперь вы можете использовать (x * 341) >> 10
(Убедитесь, что сдвиг является сдвигом со знаком, если используются целые числа со знаком), также убедитесь, что сдвиг действительно сдвиг, а не бит ROLL

Это эффективно разделит значение 3 и будет работать примерно в 1,6 раза быстрее, чем естественное деление на 3 на стандартном процессоре x86 / x64.

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

Иногда может быть даже выгоднее переместить значение в большее значение, а затем сделать то же самое, т.е. если у вас есть int полного диапазона, вы можете сделать его 64-битным значением, а затем сделать умножение и сдвиг вместо деления на 3.

Мне пришлось сделать это недавно, чтобы ускорить обработку изображений, мне нужно было найти среднее из 3 цветовых каналов, каждый из которых имеет диапазон байтов (0 - 255). красный зеленый и синий.

Сначала я просто использовал:

avg = (r + g + b) / 3;

(Таким образом, r + g + b имеет максимум 768 и минимум 0, потому что каждый канал является байтом 0 - 255)

После миллионов итераций вся операция заняла 36 миллисекунд.

Я изменил строку на:

avg = (r + g + b) * 341 >> 10;

И это заняло 22 миллисекунды, это удивительно, что можно сделать с небольшой изобретательностью.

Это ускорение произошло в C #, хотя у меня были включены оптимизации и я запускал программу без отладочной информации и без встроенной среды.

Answer 4

См. Как делить на 3 для расширенного обсуждения более эффективного деления на 3, сфокусированного на выполнении арифметических операций ПЛИС.

Также актуально:

• Оптимизация целочисленных делений с помощью Multiply Shift в C #

Answer 5

В зависимости от вашей платформы и в зависимости от вашего компилятора C, нативное решение, такое как просто

y = x / 3

Может быть быстрым или ужасно медленным (даже если деление выполняется полностью на аппаратном уровне, если оно выполняется с помощью инструкции DIV, эта инструкция примерно в 3–4 раза медленнее, чем умножение на современных процессорах). Очень хорошие компиляторы C с включенными флагами оптимизации могут оптимизировать эту операцию, но если вы хотите быть уверены, вам лучше оптимизировать ее самостоятельно.

Для оптимизации важно иметь целые числа известного размера. В C int нет известного размера (он может варьироваться в зависимости от платформы и компилятора!), Поэтому лучше использовать целые числа C99 фиксированного размера. В приведенном ниже коде предполагается, что вы хотите разделить 32-разрядное целое число без знака на три и что ваш компилятор C знает о 64-разрядных целых числах ( ПРИМЕЧАНИЕ. Даже в 32-разрядной архитектуре ЦП большинство компиляторов C могут обрабатывать 64-разрядные целые числа просто прекрасный ):

static inline uint32_t divby3 (
    uint32_t divideMe
) {
    return (uint32_t)(((uint64_t)0xAAAAAAABULL * divideMe) >> 33);
}

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

С другой стороны, если ваш компилятор очень хороший и знает хитрость, как оптимизировать целочисленное деление на константу (последний GCC делает, я только что проверил), он все равно сгенерирует приведенный выше код (GCC создаст точно этот код для "/ 3", если вы включите хотя бы уровень оптимизации 1). Что касается других компиляторов ... вы не можете полагаться или ожидать, что он будет использовать подобные приемы, даже если этот метод очень хорошо документирован и упоминается повсюду в Интернете.

Проблема в том, что он работает только для постоянных чисел, а не для переменных. Вам всегда нужно знать магическое число (здесь 0xAAAAAAAB) и правильные операции после умножения (в большинстве случаев сдвиги и / или сложения), и то и другое зависит от числа, на которое вы хотите разделить, и оба требуют слишком много времени ЦП для рассчитать их на лету (это будет медленнее, чем аппаратное деление). Тем не менее, компилятору легко вычислить их во время компиляции (где одна или более секунд меньше или меньше не играет роли).

Answer 6

Что если вы действительно не хотите умножать или делить? Вот приближение, которое я только что изобрел. Это работает, потому что (х / 3) = (х / 4) + (х / 12). Но поскольку (x / 12) = (x / 4) / 3, нам просто нужно повторить процесс, пока он не станет достаточно хорошим.

#include <stdio.h>

void main()
{
    int n = 1000;
    int a,b;
    a = n >> 2;
    b = (a >> 2);
    a += b;
    b = (b >> 2);
    a += b;
    b = (b >> 2);
    a += b;
    b = (b >> 2);
    a += b;
    printf("a=%d\n", a);
}

Результат - 330. Его можно сделать более точным, используя b = ((b + 2) >> 2); для учета округления.

Если вам разрешено умножать , просто выберите подходящее приближение для (1/3) с делителем степени 2. Например, n * (1/3) ~ = n * 43/128 = (n * 43) >> 7.

Эта техника наиболее полезна в Индиана.

Answer 7

Для 64-битных чисел:

uint64_t divBy3(uint64_t x)
{
    return x*12297829382473034411ULL;
}

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

Например, если вы запустите его, например, на 11, он возвращает 6148914691236517209. Это выглядит как мусор, но на самом деле это правильный ответ: умножьте его на 3, и вы получите обратно 11!

Если вы ищете усеченное деление, просто используйте оператор /. Я очень сомневаюсь, что вы можете получить намного быстрее, чем это.

Теория:

64-битная арифметика без знака является арифметикой по модулю 2 ^ 64. Это означает, что для каждого целого числа, которое является взаимно простым с модулем 2 ^ 64 (по существу, все нечетные числа), существует мультипликативное обратное, которое вы можете использовать для умножения вместо деления. Это магическое число может быть получено путем решения уравнения 3*x + 2^64*y = 1 с использованием расширенного евклидова алгоритма.

Answer 8

Я не знаю, быстрее ли это, но если вы хотите использовать побитовый оператор для выполнения двоичного деления, вы можете использовать метод сдвига и вычитания, описанный в этой странице :

• Установить отношение к 0
• Выравнивание крайних левых цифр в делителе и делителе
• Повтор:
  • Если эта часть дивиденда выше делителя больше или равна делителю:
    • Затем вычтите делитель из этой части дивиденда и
    • Объединение 1 с правым концом частного
    • Иное присоединение 0 к правому концу частного
  • Сдвиньте делитель на одно место вправо
• Пока дивиденд не меньше делителя:
• коэффициент верный, дивиденд остаток
• СТОП

Answer 9

Для действительно большого целочисленного деления (например, числа больше 64 бит) вы можете представить свое число как целое [] и выполнить деление довольно быстро, взяв две цифры за раз и разделив их на 3. Остальная часть будет частью следующие две цифры и пр.

например. 11004/3 вы говорите

11/3 = 3, остаток = 2 (из 11-3 * 3)

20/3 = 6, остаток = 2 (от 20-6 * 3)

20/3 = 6, остаток = 2 (от 20-6 * 3)

24/3 = 8, остаток = 0

отсюда и результат 3668

internal static List<int> Div3(int[] a)
{
  int remainder = 0;
  var res = new List<int>();
  for (int i = 0; i < a.Length; i++)
  {
    var val = remainder + a[i];
    var div = val/3;

    remainder = 10*(val%3);
    if (div > 9)
    {
      res.Add(div/10);
      res.Add(div%10);
    }
    else
      res.Add(div);
  }
  if (res[0] == 0) res.RemoveAt(0);
  return res;
}

Answer 10

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