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

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

// for instance

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

int b = (n << 1) + n; // <-- potentially faster multiplication
Источник

12 ответов

Решение

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

int a;
int b;

a = some value;
b = a / 3;
Источник

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

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

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

Источник

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

например.

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

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

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

Источник

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

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

Источник

В зависимости от вашей платформы и в зависимости от вашего компилятора 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) и правильные операции после умножения (в большинстве случаев сдвиги и / или сложения), и то и другое зависит от числа, на которое вы хотите разделить, и оба требуют слишком много времени ЦП для рассчитать их на лету (это будет медленнее, чем аппаратное деление). Однако компилятору легко вычислить их во время компиляции (где одна или более секунд меньше или меньше не играет роли).

Источник

Для 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 уравнение с использованием расширенного евклидова алгоритма.

Источник

Что если вы действительно не хотите умножать или делить? Вот приближение, которое я только что изобрел. Это работает, потому что (х /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.

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

Источник

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

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

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

Источник

Для действительно большого целочисленного деления (например, числа больше 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;
}
Источник

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

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];
}
Источник

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

uint8_t divideby3(uint8_t x)
{
  uint8_t answer =0;
  do
  {
    x>>=1;
    answer+=x;
    x=-x;
  }while(x);
  return answer;
}
Источник
Другие вопросы по тегам