Какой самый быстрый способ разделить целое число на 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

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

int a;
int b;

a = some value;
b = a / 3;

Answer 2

Парень, который сказал: «Оставь его к компилятору» было правильным, но у меня нет «репутации» модифицируют его или комментировать. Я спросил GCC для компиляции INT Test (int a) {return a / 3; } Для IX86 и затем разобрал выход. Только для академического интереса, что это делает, это грубо Умножение на 0x555555556 и затем принимая топ-32 бита из 64-битных результатов этого. Вы можете продемонстрировать это для себя, например:

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

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

Answer 3

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

например.

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

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

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

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

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

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

Answer 4

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

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

• Оптимизация целочисленных подразделений с умножением сдвига в C#

Answer 5

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

y = x / 3

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

Для оптимизации важно иметь целочисленное количество известного размера. В C int нет известного размера (он может варьироваться в зависимости от платформы и компилятора!), Так что вы лучше используете целые числа фиксированного размера C99. Приведенный ниже код предполагает, что вы хотите разделить 32-разрядное 32-разрядное целое число на три и что вы Compiler знают около 64-битных целых чисел (Примечание. Даже на 32-разрядной архитектуре CPU, большинство компиляров 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). Для других компиляторов ... Вы не можете полагаться или ожидать, что он будет использовать такие хитрости, даже если этот метод очень хорошо документирован и упоминается повсюду в Интернете.

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

Answer 6

Что делать, если ты В самом деле Не хочу умножить или разделить? Вот это приближение, которое я только что изобрел. Это работает, потому что (x / 3) = (x / 4) + (x / 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-2. Например, N * (1/3) ~ = N * 43/128 = (N * 43) >> 7.

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

Answer 7

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

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

Answer 8

Для 64 битовых номеров:

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

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

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

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

Теория:

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

Answer 9

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

Answer 10

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

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

11/3 = 3, Menseer = 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 11

Простое вычисление ... на большинстве n итераций, где n - ваш номер битов:

uint8_t divideby3(uint8_t x)
{
  uint8_t answer =0;
  do
  {
    x>>=1;
    answer+=x;
    x=-x;
  }while(x);
  return answer;
}

Answer 12

Подход к таблице поиска также будет быстрее в некоторых архитектурах.

uint8_t DivBy3LU(uint8_t u8Operand)
{
   uint8_t ai8Div3 = [0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, ....];

   return ai8Div3[u8Operand];
}