Qual é a maneira mais rápida de dividir um número inteiro por 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

Isso é o mais rápido, pois o compilador o otimiza, se puder, dependendo do processador de saída.

int a;
int b;

a = some value;
b = a / 3;

Answer 2

O cara que disse "deixe para o compilador" estava certo, mas eu não tenho a "reputação" de modificá -lo ou comentar. Pedi ao GCC para compilar o teste int (int a) {return a / 3; } para um ix86 e depois desmontou a saída. Apenas para interesse acadêmico, o que está fazendo é aproximadamente Multiplicando por 0x55555556 e depois pegando os 32 bits do resultado de 64 bits. Você pode demonstrar isso para si mesmo com por exemplo:

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

A página da Wikipedia em Divisão de Montgomery É difícil de ler, mas felizmente os caras do compilador fizeram isso para que você não precise.

Answer 3

Existe uma maneira mais rápida de fazê -lo se você souber os intervalos dos valores, por exemplo, se você estiver dividindo um número inteiro assinado por 3 e sabe que o alcance do valor a ser dividido é de 0 a 768, então você pode multiplicá -lo por um fator e mude -o para a esquerda por uma potência de 2 para esse fator dividido por 3.

por exemplo.

Intervalo 0 -> 768

Você pode usar a mudança de 10 bits, que multiplicando por 1024, você deseja dividir por 3 para que seu multiplicador seja 1024 /3 = 341,

Então você pode usar agora (x * 341) >> 10
(Verifique se a mudança é uma mudança assinada se estiver usando números inteiros assinados), verifique também se a mudança é realmente uma mudança e não um pouco de rolo

Isso dividirá efetivamente o valor 3 e será executado em cerca de 1,6 vezes a velocidade como uma divisão natural por 3 em uma CPU padrão x86 / x64.

Obviamente, a única razão pela qual você pode fazer essa otimização quando o compilador não é porque o compilador não conhece o alcance máximo de x e, portanto, não pode fazer essa determinação, mas você como o programador pode.

Às vezes, pode ser mais benéfico mover o valor para um valor maior e depois fazer a mesma coisa, ou seja. Se você tiver um INT de alcance total, poderá torná-lo um valor de 64 bits e, em seguida, multiplique e desligue em vez de dividir por 3.

Eu tive que fazer isso recentemente para acelerar o processamento da imagem, precisava encontrar a média de 3 canais de cores, cada canal de cores com um intervalo de bytes (0 - 255). Verde vermelho e azul.

No começo eu simplesmente usei:

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

(Então R + G + B tem um máximo de 768 e um mínimo de 0, porque cada canal é um byte 0 - 255)

Após milhões de iterações, toda a operação levou 36 milissegundos.

Eu mudei a linha para:

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

E isso levou para 22 milissegundos, é incrível o que pode ser feito com um pouco de ingenuidade.

Essa velocidade ocorreu em C#, apesar de eu ter otimizações ativadas e estivesse executando o programa de maneira nativamente sem depuração de informações e não através do IDE.

Answer 4

Ver Como dividir por 3 Para uma discussão prolongada de dividir com mais eficiência por 3, focado em fazer operações aritméticas da FPGA.

Também relevante:

• Otimizando divisões inteiras com multiplicação de mudança em C#

Answer 5

Dependendo da sua plataforma e dependendo do seu compilador C, uma solução nativa como apenas usar

y = x / 3

Pode ser rápido ou pode ser muito lento (mesmo que a divisão seja feita inteiramente em hardware, se for feito usando uma instrução DIV, esta instrução é cerca de 3 a 4 vezes mais lenta que uma multiplicação nas CPUs modernas). Os compiladores C muito bons com sinalizadores de otimização ativados podem otimizar esta operação, mas se você quiser ter certeza, é melhor otimizá -la.

Para otimização, é importante ter um número inteiro de tamanho conhecido. Em C Int, não tem tamanho conhecido (ele pode variar de acordo com a plataforma e o compilador!), Para que você seja melhor usando números inteiros de tamanho fixo C99. O código abaixo pressupõe que você deseja dividir um número inteiro de 32 bits não assinado por três e que o compilador C conhece números inteiros de 64 bits (Nota: Mesmo em uma arquitetura de CPU de 32 bits, a maioria dos compiladores C pode lidar com números inteiros de 64 bits bem):

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

Por mais louco que isso possa parecer, mas o método acima realmente se divide em 3. Tudo o que precisa para isso é uma única multiplicação de 64 bits e uma mudança (como eu disse, multiplicações podem ser 3 a 4 vezes mais rápidas que as divisões em sua CPU ). Em um aplicativo de 64 bits, este código será muito mais rápido do que em um aplicativo de 32 bits (em um aplicativo de 32 bits multiplicando dois números de 64 bits, levam 3 multiplicações e 3 adições em valores de 32 bits) - no entanto, pode ser ainda mais rápido que um Divisão em uma máquina de 32 bits.

Por outro lado, se o seu compilador for muito bom e souber o truque como otimizar a divisão inteira por uma constante (o GCC mais recente faz, acabei de verificar), ele gerará o código acima de qualquer maneira (o GCC criará exatamente esse código para "/3" se você ativar pelo menos o nível de otimização 1). Para outros compiladores ... você não pode confiar ou esperar que ele use truques como esse, mesmo que esse método seja muito bem documentado e mencionado em todos os lugares da Internet.

O problema é que ele funciona apenas para números constantes, não para variáveis. Você sempre precisa conhecer o número mágico (aqui 0XAAAAAAAB) e as operações corretas após a multiplicação (mudanças e/ou adições na maioria dos casos) e ambos são diferentes, dependendo do número que você deseja dividir e ambos levam muito tempo à CPU para Calcule -os em tempo real (que seria mais lenta que a divisão de hardware). No entanto, é fácil para um compilador calculá -los durante o tempo de compilação (onde um segundo mais ou menos tempo de compilação desempenha dificilmente um papel).

Answer 6

E se você verdade Não quer multiplicar ou dividir? Aqui está uma aproximação que acabei de inventar. Funciona porque (x/3) = (x/4) + (x/12). Mas como (x/12) = (x/4)/3, precisamos repetir o processo até que seja bom o suficiente.

#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);
}

O resultado é 330. Pode ser tornado mais preciso usando b = ((b+2) >> 2); Para explicar o arredondamento.

Se você são Permitido a multiplicar, basta escolher uma aproximação adequada para (1/3), com um divisor de potência do 2. Por exemplo, n * (1/3) ~ = n * 43 /128 = (n * 43) >> 7.

Esta técnica é mais útil em Indiana.

Answer 7

Não sei se é mais rápido, mas se você deseja usar um operador bit -bit para realizar a divisão binária, você pode usar o método de mudança e subtraia descrito em esta página:

• Cociente definido para 0
• Alinhe os dígitos mais à esquerda em dividendo e divisor
• Repetir:
  • Se essa parte do dividendo acima do divisor for maior ou igual ao divisor:
    • Então subtraia o divisor daquela parte do dividendo e
    • Concatentado 1 na extremidade direita do quociente
    • Else concatentado 0 na extremidade direita do quociente
  • Mude o divisor um lugar certo
• Até que o dividendo seja menor que o divisor:
• O quociente está correto, o dividendo é restante
• PARE

Answer 8

Para números de 64 bits:

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

No entanto, esta não é a divisão inteira truncadora que você pode esperar. Funciona corretamente se o número já estiver divisível por 3, mas retorna um número enorme, se não for.

Por exemplo, se você o executar, por exemplo, 11, ele retornará 6148914691236517209. Isso parece um lixo, mas é de fato a resposta correta: multiplique por 3 e você recebe o 11!

Se você está procurando a divisão truncadora, basta usar o / operador. Eu duvido muito que você possa ficar muito mais rápido do que isso.

Teoria:

A aritmética não assinada de 64 bits é uma aritmética módulo 2^64. Isso significa para cada número inteiro que é coprime com o módulo 2^64 (essencialmente todos os números ímpares) existe um inverso multiplicativo que você pode usar para se multiplicar em vez de divisão. Este número mágico pode ser obtido resolvendo o 3*x + 2^64*y = 1 equação usando o algoritmo euclidiano estendido.

Answer 9

Se você realmente quer ver este artigo sobre Divisão Inteiro, mas só tem mérito acadêmico ... seria uma aplicação interessante que realmente precisava executar que se beneficiou desse tipo de truque.

Answer 10

Para uma divisão inteira realmente grande (por exemplo, números maiores que 64 bits), você pode representar seu número como um int [] e executar a divisão muito rápido, levando dois dígitos por vez e dividi -los por 3. O restante fará parte dos próximos dois dígitos e assim por diante.

por exemplo. 11004 /3 Você diz

11/3 = 3, restante = 2 (de 11-3*3)

20/3 = 6, restante = 2 (de 20-6*3)

20/3 = 6, restante = 2 (de 20-6*3)

24/3 = 8, restante = 0

daí o resultado 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

Computação fácil ... na maioria das nireções em que n é o seu número de bits:

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

Answer 12

Uma abordagem da tabela de pesquisa também seria mais rápida em algumas arquiteturas.

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];
}