Como C resolve cálculos matemáticos

[Fabio Bairros]

Boa tarde a todos.

Como o C (no final do processo - ou traduz para uma linguagem de máquina) segmenta ou resolve um determinado cálculo matemático ?

Por exemplo: a operação % ou fmod - que retornam o resto inteiro de uma divisão. Como eles são resolvidos em C ?

Att,

Fábio

[Virgilio Fornazin]

cada cpu implementa suas operações matemáticas em assembly usando registradores.

as operações que são mais complexas são implementadas em funções que fazem vártias operações até chegar aos cálculos.

nesse guia ( https://www.felixcloutier.com/x86/ ) você consegue entender um pouco as instruções do intel

mais especificamente, para calcular modulo: https://stackoverflow.com/questions/8021772/assembly-language-how-to-do-modulo

--
http://ccppbrasil.github.io/
https://twitter.com/ccppbrasil
 
[&] C & C++ Brasil - http://www.ccppbrasil.org/
Para sair dessa lista, envie um e-mail para ccppbrasil-...@googlegroups.com
---
Você recebeu essa mensagem porque está inscrito no grupo "ccppbrasil" dos Grupos do Google.
Para cancelar inscrição nesse grupo e parar de receber e-mails dele, envie um e-mail para ccppbrasil+...@googlegroups.com.
Para ver essa discussão na Web, acesse https://groups.google.com/d/msgid/ccppbrasil/afc93726-471b-499f-bd87-223a755bd641n%40googlegroups.com.

[Fabio Bairros]

Bom dia Virgilio.

Valeu. Vou dar uma olhada no material.

Obrigado

Fabio Bairros

Para ver essa discussão na Web, acesse https://groups.google.com/d/msgid/ccppbrasil/CADfydxJm7ip78M7bpMAfZW2QPeX5EUVv5dXpr0M%2B%3DzN%2Bbg5hgg%40mail.gmail.com.

[walter.ma...@gmail.com]

Bom dia Fábio,

  Um bom modo de ver isso ocorrer na prática é usar o godbolt

https://godbolt.org/

  Com ele você consegue ver a "versão de máquina" do seu

código. Para códigos mais complexos (uma fórmula

matematica complicada por exemplo) é dificil prever

o que o otimizador fará, mas com o godbolt

você consegue ver como ele "pensa".

            walter

[Fabio Bairros]

Bom dia Walter e agradeço o retorno.

E é possível saber quais as alternativas que o otimizador possui ? Quais as regras que ele usa ?

Por exemplo: usando o operador módulo % do C - resto inteiro de uma divisão.

(61199 % 256) é tratado da mesma forma que (61199 % 171) ?

Obrigado

Fabio Bairros

Para ver essa discussão na Web, acesse https://groups.google.com/d/msgid/ccppbrasil/d9a8a967-34f6-450e-8d15-dd76f2925bfdn%40googlegroups.com.

[Fabio A Mazzarino]

Vamos por partes.

Nos processadores mais simples, principalmente os de 8 bits, só existiam soma, subtração e rotação de bits (multiplicação e divisão por 2). Nesse caso existem algoritmos para fazer multiplicação através de somas sucessivas, e divisão a partir de rotação de bits, e assim os compiladores utilizavam essas técnicas para fazer operações mais complexas.

Qdo chegaram os processadores de 16 bits eles tinham as quatro operações básicas. Novamente existem algoritmos para fazer executar operações um pouco mais avançadas, como potenciação, e assim funcionam os compiladores para essas plataformas. Ainda assim, muitos sistemas contavam com um co-processador numérico, que continham vários tipos de algoritmos prontos, através de opções de compilação para utilizar os co-processadores.

Nos sistemas de 32 bits os co-processadores começaram a ser integrados no próprio chip, com operações diretamente integradas nos processadores (note que o 386 e o 486 SX não contavam com co-processador integrado), isso já facilitava bastante para o compilador que tinha um conjunto maior de operações disponível.

De qq forma quando falamos de trigonometria e cálculos mais complexos temos técnicas de séries e transformadas que são implementadas de maneira simplificada pelas bibliotecas padrão disponíveis em cada compilador.

Lab C++ - Dicas, Código e Snippets
http://labcpp.com.br

--

[walter.ma...@gmail.com]

Fabio,

   Com gcc, a opção básica para otimizar é -O3. Com ela,  o codigo

int f(int i) {   return i % 171; }

resulta no seguinte em x86-64:

movsx rax, edi

mov edx, edi

imul rax, rax, -1080021015

sar edx, 31

shr rax, 32

add eax, edi

sar eax, 7

sub eax, edx

imul edx, eax, 171

mov eax, edi

sub eax, edx

ret

 Ou seja, o otimizador troca o % (que é basicamente

uma divisão) por operações bem mais baratas

(shifts, muls e subs).  O -1080021015 é calculado

a partir do 171 usando teoria de números. Se

ao invẽs de 171 usassemos outro número conhecido

em tempo de compilação, o código seria parecido,

com -1080021015 substituido por outro valor.

Como a divisão é um operação muito cara,

espero que o código acima seja mais eficiente

que o uso óbvio da instrução para divisão

(mas não medi.)

O ideal seria você aprender a usar o godbolt

e ir fazendo os experimentos você mesmo.

              

           

[Fabio Bairros]

Certo Walter, farei os testes.

Aproveitando, conhece artigos e ou literatura que possa indicar para embasamento ?

Obrigado

Fabio Bairros

Para ver essa discussão na Web, acesse https://groups.google.com/d/msgid/ccppbrasil/72885150-8b87-4af1-9c31-839cd8b50268n%40googlegroups.com.

[walter.ma...@gmail.com]

Fábio,

  outra ferramenta muito útil para aprender essas coisas

é o stackoverflow. Veja a pagina abaixo para mais

detalhes sobre o assunto que estamos discutindo aqui

https://stackoverflow.com/questions/41183935/why-does-gcc-use-multiplication-by-a-strange-number-in-implementing-integer-divi

[Fabio Bairros]

Boa tarde Fabio e agradeço.

Você tem alguma literatura e artigos para indicar sobre este comportamento dos compiladores ?

Obrigado

Fabio Bairros

Para ver essa discussão na Web, acesse https://groups.google.com/d/msgid/ccppbrasil/CALXhAFzdx32SWVFQDKXRfXQwss6RKUp38tLFwyW4DGuuy163MA%40mail.gmail.com.

[walter.ma...@gmail.com]

Fabio,

   Além do que há no stackoverflow, não conheço

referências especificas sobre isso.

    A base do que sei é uma combinação do que aprendi

ao longo dos anos estudando teoria dos números

(para isso busque por "introdução à teoria dos

números no google) e sobre o método de newton

para a divisão (procure por método de newton raphson)

Note porém que para chegar ao código gerado pelo

compilador a partir do que está nos livros de matemática

será necessário um bom esforço. Para gerar esse código,

além de saber a  matemática é necessario conhecer

as instruções disponíveis e ter estimativas sobre o número

de ciclos e a latência delas. Você pode aprender sobre isso

lendo as coisas do Agner  Fog:

https://www.agner.org/optimize/

Alíás, pode ser que haja algo específico sobre otimização

da divisão nos escritos do Agner, mas eu não me lembro,

          walter.

[Fabio Bairros]

Certo Walter, muito obrigado pelo auxílio.

Obrigado

Fabio Bairros

Para ver essa discussão na Web, acesse https://groups.google.com/d/msgid/ccppbrasil/95bf36ec-df2d-48ff-8efb-bd5e13e01da9n%40googlegroups.com.

[de...@roo.com.br]

vale a pena dar uma olhada nas SIMD Extensions (entre outras).

um projeto que "deita e rola" nessas extensoes é esse https://github.com/ermig1979/Simd

https://pt.wikipedia.org/wiki/Streaming_SIMD_Extensions