Multiplicando dois números de 32 bits sem usar 64 bits int

Question

Estamos fazendo uma multiplicação de 32 bits * 32 bits usando o seguinte algoritmo

Vamos queremos multiplicar um (32 bits) com B (32 bits), ambos assinados,

a = ah * 2^16 + al [ah - 16 bits, al - menor 16 bits

B = BH * 2^16 + BL [BH - 16 bits, BL - 16 bits inferiores

Estamos efetivamente fazendo

Resultado = (al * bl) + (((ah * bl) + (al * bh)) * 2 ^ 16) + ((ah * bh) * 2 ^ 32) ~~~

---

Minha pergunta,

A maneira melhor deles é fazer isso?

Answer 1

Em qualquer compilador convencional, a emulação de INTs de 64 bits em uma plataforma de 32 bits será tão eficiente quanto fazer a matemática do Mutli-Step. Mas será muito mais confiável.

Ao fazer aritmética simples com valores grandes o suficiente para transbordar, mesmo a biblioteca de matemática mais sintonizada que eu vi apenas usa o INT64.

Answer 2

Google "Karatsuba Multiplication".

Oih, e em seu código, altere a constante 2^15 (aparece duas vezes) para 2^16.

Answer 3

A resposta é não que não exista uma maneira melhor de fazer as coisas, além de usar mudanças e máscaras em vez de 2^n. Nomeadamente:

a * 2^n <=> a << n

Em segundo lugar, seus INTs são assinados ou não assinados? Se eles são assinados, isso muda as coisas.

Terceiro, não tenho certeza se o seu 2^15 está certo. Se não é assinado, pelo menos, você deseja mudar de bits por 16 e não 15.

Por fim, você deve prestar atenção para o excesso inteiro na ordem de baixa ordem. Se você adicionar números juntos na ordem baixa e que transborda sua capacidade, você precisará incrementar corretamente o alto pedido.

Answer 4

Você precisa saber (especificar) como o valor de 64 bits deve ser armazenado-presumivelmente, é um par de valores de 32 bits, possivelmente dois elementos de uma matriz ou dois elementos de uma estrutura. Você também precisa considerar como as informações do sinal serão armazenadas no resultado.

Mecanicamente, você provavelmente deseja converter os dois valores assinados para não assinar e, em seguida, faça a divisão e a remoção ao longo das linhas que mostrou, tomando cuidado para garantir que os carregamentos do valor de 32 bits de ordem baixa sejam gerenciados adequadamente na alta ordem de 32 bits valor.

Dependendo das suas decisões iniciais de design, você também pode precisar gritar a representação do sinal do resultado e talvez até todos os outros bits.

Comentários semelhantes se aplicam à multiplicação de dois números de 16 bits sem resultados de 32 bits, algo que antes era importante, mas a maioria das pessoas não precisa se preocupar.