Eu estive pesquisando desmontagens .NET e o código-fonte do GCC, mas parece que não consigo encontrar em lugar algum a implementação real sin()
e outras funções matemáticas ... elas sempre parecem fazer referência a outra coisa.
Alguém pode me ajudar a encontrá-los? Eu sinto que é improvável que TODO o hardware em que C seja executado suporte funções trigonométricas no hardware, então deve haver um algoritmo de software em algum lugar , certo?
Estou ciente de várias maneiras pelas quais as funções podem ser calculadas e escrevi minhas próprias rotinas para calcular funções usando a série taylor por diversão. Estou curioso para saber o quão real são as linguagens de produção, pois todas as minhas implementações são sempre várias ordens de magnitude mais lentas, embora eu ache que meus algoritmos são bastante inteligentes (obviamente não são).
fonte
Respostas:
Na GNU libm, a implementação de
sin
depende do sistema. Portanto, você pode encontrar a implementação, para cada plataforma, em algum lugar no subdiretório apropriado do sysdeps .Um diretório inclui uma implementação em C, contribuída pela IBM. Desde outubro de 2011, esse é o código que é executado quando você liga
sin()
para um sistema Linux x86-64 típico. Aparentemente, é mais rápido que afsin
instrução de montagem. Código-fonte: sysdeps / ieee754 / dbl-64 / s_sin.c , procure__sin (double x)
.Este código é muito complexo. Nenhum algoritmo de software é o mais rápido possível e também preciso em toda a faixa de valores x ; portanto, a biblioteca implementa vários algoritmos diferentes, e seu primeiro trabalho é examinar x e decidir qual algoritmo usar.
Quando x é muito muito próximo de 0,
sin(x) == x
é a resposta certa.Um pouco mais adiante,
sin(x)
usa a familiar série Taylor. No entanto, isso é preciso apenas próximo de 0, então ...Quando o ângulo é superior a cerca de 7 °, um algoritmo diferente é usado, computando aproximações da série Taylor tanto para sin (x) quanto cos (x), usando valores de uma tabela pré-computada para refinar a aproximação.
Quando | x | > 2, nenhum dos algoritmos acima funcionaria; portanto, o código começa calculando algum valor mais próximo de 0 que pode ser alimentado
sin
oucos
usado.Existe ainda outro ramo para lidar com x sendo um NaN ou infinito.
Esse código usa alguns hacks numéricos que eu nunca vi antes, embora, pelo que sei, possam ser bem conhecidos entre os especialistas em ponto flutuante. Às vezes, algumas linhas de código levam vários parágrafos para explicar. Por exemplo, essas duas linhas
são usados (algumas vezes) na redução de x para um valor próximo de 0 que difere de x por um múltiplo de π / 2, especificamente
xn
× π / 2. A maneira como isso é feito sem divisão ou ramificação é bastante inteligente. Mas não há nenhum comentário!As versões mais antigas de 32 bits do GCC / glibc usavam a
fsin
instrução, que é surpreendentemente imprecisa para algumas entradas. Há uma postagem de blog fascinante ilustrando isso com apenas 2 linhas de código .A implementação do fdlibm
sin
em C puro é muito mais simples que a do glibc e é bem comentada. Código fonte: fdlibm / s_sin.c e fdlibm / k_sin.cfonte
sin()
; digitegdb a.out
, entãobreak sin
, entãorun
, entãodisassemble
.__kernel_sin
é definido no k_sin.c, porém, e é puro C. Clique novamente - eu estraguei o URL pela primeira vez.Funções como seno e cosseno são implementadas em microcódigo dentro de microprocessadores. Os chips Intel, por exemplo, têm instruções de montagem para eles. O compilador de CA gerará código que chama essas instruções de montagem. (Por outro lado, um compilador Java não avaliará. O Java avalia funções trigonométricas no software e não no hardware e, portanto, é muito mais lento.)
Os chips não usam a série Taylor para calcular funções trigonométricas, pelo menos não inteiramente. Antes de tudo, eles usam o CORDIC , mas também podem usar uma série curta de Taylor para aprimorar o resultado do CORDIC ou para casos especiais, como calcular o seno com alta precisão relativa em ângulos muito pequenos. Para mais explicações, consulte esta resposta StackOverflow .
fonte
OK, crianças, hora dos profissionais .... Essa é uma das minhas maiores reclamações com engenheiros de software inexperientes. Eles vêm calculando funções transcendentais do zero (usando a série de Taylor) como se ninguém tivesse feito esses cálculos antes em suas vidas. Não é verdade. Esse é um problema bem definido e foi abordado milhares de vezes por engenheiros muito inteligentes de software e hardware e tem uma solução bem definida. Basicamente, a maioria das funções transcendentais usa os polinômios de Chebyshev para calculá-los. O uso de polinômios depende das circunstâncias. Primeiro, a Bíblia sobre esse assunto é um livro chamado "Computer Approximations", de Hart e Cheney. Nesse livro, você pode decidir se possui um somador, multiplicador, divisor etc., e decide quais operações são mais rápidas. Por exemplo, se você tivesse um divisor muito rápido, a maneira mais rápida de calcular seno pode ser P1 (x) / P2 (x) em que P1, P2 são polinômios de Chebyshev. Sem o divisor rápido, pode ser apenas P (x), onde P tem muito mais termos do que P1 ou P2 .... então seria mais lento. Portanto, o primeiro passo é determinar o seu hardware e o que ele pode fazer. Em seguida, você escolhe a combinação apropriada de polinômios de Chebyshev (geralmente é da forma cos (ax) = aP (x) para cosseno, por exemplo, novamente onde P é um polinômio de Chebyshev). Então você decide qual precisão decimal deseja. por exemplo, se você deseja uma precisão de 7 dígitos, procure na tabela apropriada do livro que mencionei e ele fornecerá (para precisão = 7,33) um número N = 4 e um número polinomial 3502. N é a ordem do polinômio (então é p4.x ^ 4 + p3.x ^ 3 + p2.x ^ 2 + p1.x + p0), porque N = 4. Então você procura o valor real de p4, p3, p2, p1, valores de p0 na parte de trás do livro em 3502 (eles estarão em ponto flutuante). Em seguida, você implementa seu algoritmo em software na forma: (((p4.x + p3) .x + p2) .x + p1) .x + p0 .... e é assim que você calcula o cosseno com 7 decimais lugares nesse hardware.
Observe que a maioria das implementações de hardware de operações transcendentais em uma FPU geralmente envolve alguns microcódigos e operações como essa (depende do hardware). Os polinômios de Chebyshev são usados para a maioria dos transcendentais, mas não todos. Por exemplo, a raiz quadrada é mais rápida para usar uma iteração dupla do método Newton Raphson usando uma tabela de pesquisa primeiro. Mais uma vez, o livro "Aproximações por Computador" dirá isso.
Se você planeja implementar essas funções, recomendo a todos que obtenham uma cópia desse livro. É realmente a Bíblia para esses tipos de algoritmos. Observe que existem vários meios alternativos para calcular esses valores, como cordics, etc., mas esses tendem a ser melhores para algoritmos específicos, nos quais você só precisa de baixa precisão. Para garantir sempre a precisão, os polinômios chebyshev são o caminho a seguir. Como eu disse, problema bem definido. Foi resolvido há 50 anos ... e é assim que é feito.
Agora, dito isso, existem técnicas pelas quais os polinômios de Chebyshev podem ser usados para obter um único resultado de precisão com um polinômio de baixo grau (como o exemplo do cosseno acima). Em seguida, existem outras técnicas para interpolar entre valores para aumentar a precisão sem precisar ir para um polinômio muito maior, como o "Método de tabelas precisas de Gal". Esta última técnica é a que se refere o post referente à literatura da ACM. Mas, em última análise, os polinômios de Chebyshev são o que é usado para obter 90% do caminho até lá.
Aproveitar.
fonte
Para
sin
especificamente, o uso da expansão Taylor daria a você:sen (x): = x - x ^ 3/3! + x ^ 5/5! - x ^ 7/7! + ... (1)
você continuaria adicionando termos até que a diferença entre eles seja menor que um nível de tolerância aceito ou apenas para uma quantidade finita de etapas (mais rápidas, mas menos precisas). Um exemplo seria algo como:
Nota: (1) funciona devido à aproximação sin (x) = x para pequenos ângulos. Para ângulos maiores, é necessário calcular cada vez mais termos para obter resultados aceitáveis. Você pode usar um argumento while e continuar com uma certa precisão:
fonte
Sim, também existem algoritmos de software para cálculo
sin
. Basicamente, o cálculo desse tipo de coisa com um computador digital geralmente é feito usando métodos numéricos como aproximar a série de Taylor representa a função.Os métodos numéricos podem aproximar as funções a uma quantidade arbitrária de precisão e, como a quantidade de precisão que você tem em um número flutuante é finita, eles se adaptam bem a essas tarefas.
fonte
Use a série Taylor e tente encontrar uma relação entre os termos da série para não calcular as coisas repetidamente
Aqui está um exemplo para cosinus:
usando isso, podemos obter o novo termo da soma usando o já usado (evitamos o fatorial ex 2p )
fonte
É uma pergunta complexa. A CPU semelhante à Intel da família x86 possui uma implementação de hardware da
sin()
função, mas faz parte da FPU x87 e não é mais usada no modo de 64 bits (onde os registros SSE2 são usados). Nesse modo, uma implementação de software é usada.Existem várias implementações desse tipo por aí. Um está no fdlibm e é usado em Java. Até onde eu sei, a implementação glibc contém partes do fdlibm e outras partes contribuídas pela IBM.
Implementações de software de funções transcendentais, como
sin()
normalmente usam aproximações por polinômios, geralmente obtidas na série Taylor.fonte
sin
ecos
são mais rápidas que as instruções de hardware na FPU. Bibliotecas mais simples e ingênuas tendem a usar as instruçõesfsin
efcos
.FSIN
com precisão total. Ficaria muito grato se você me disser os nomes dessas bibliotecas rápidas, é interessante dar uma olhada.sin()
acontece cerca de duas vezes mais rápido que ofsin
calculado (justamente porque é feito com menos precisão). Observe que o x87 é conhecido por ter um pouco menos de precisão real do que os anunciados 79 bits.Os polinômios de Chebyshev, como mencionado em outra resposta, são os polinômios em que a maior diferença entre a função e o polinômio é a menor possível. Esse é um excelente começo.
Em alguns casos, o erro máximo não é o que você está interessado, mas o erro relativo máximo. Por exemplo, para a função seno, o erro próximo de x = 0 deve ser muito menor do que para valores maiores; você quer um pequeno erro relativo . Portanto, você calcularia o polinômio de Chebyshev para sin x / x e multiplicaria esse polinômio por x.
Em seguida, você precisa descobrir como avaliar o polinômio. Você deseja avaliá-lo de forma que os valores intermediários sejam pequenos e, portanto, os erros de arredondamento sejam pequenos. Caso contrário, os erros de arredondamento podem se tornar muito maiores que os erros no polinômio. E com funções como a função seno, se você for descuidado, pode ser possível que o resultado que você calcule para o pecado x seja maior que o resultado para o pecado y mesmo quando x <y. Portanto, é necessária uma escolha cuidadosa da ordem de cálculo e do cálculo dos limites superiores para o erro de arredondamento.
Por exemplo, sen x = x - x ^ 3/6 + x ^ 5/120 - x ^ 7/5040 ... Se você calcular ingenuamente sin x = x * (1 - x ^ 2/6 + x ^ 4 / 120 - x ^ 6/5040 ...), então essa função em parênteses está diminuindo, e isso vai acontecer que, se y é o próximo número maior para x, então às vezes pecam y será menor do que o pecado x. Em vez disso, calcule sin x = x - x ^ 3 * (1/6 - x ^ 2/120 + x ^ 4/5040 ...) onde isso não pode acontecer.
Ao calcular polinômios de Chebyshev, você geralmente precisa arredondar os coeficientes para dobrar a precisão, por exemplo. Mas enquanto um polinômio de Chebyshev é ideal, o polinômio de Chebyshev com coeficientes arredondados para precisão dupla não é o polinômio ideal com coeficientes de precisão dupla!
Por exemplo, para sin (x), onde você precisa de coeficientes para x, x ^ 3, x ^ 5, x ^ 7 etc., faça o seguinte: Calcule a melhor aproximação do pecado x com um polinômio (ax + bx ^ 3 + cx ^ 5 + dx ^ 7) com precisão maior que o dobro, depois arredonde a para precisão dupla, dando A. A diferença entre a e A seria muito grande. Agora calcule a melhor aproximação de (sin x - Ax) com um polinômio (bx ^ 3 + cx ^ 5 + dx ^ 7). Você obtém coeficientes diferentes, porque eles se adaptam à diferença entre a e A. Arredonde b para dobrar a precisão B. Em seguida, aproxime (sen x - Ax - Bx ^ 3) com um polinômio cx ^ 5 + dx ^ 7 e assim por diante. Você obterá um polinômio quase tão bom quanto o polinômio Chebyshev original, mas muito melhor que o Chebyshev arredondado para dobrar a precisão.
Em seguida, você deve levar em consideração os erros de arredondamento na escolha do polinômio. Você encontrou um polinômio com erro mínimo no polinômio que ignora o erro de arredondamento, mas deseja otimizar o polinômio mais o erro de arredondamento. Depois de obter o polinômio Chebyshev, você pode calcular os limites para o erro de arredondamento. Digamos que f (x) é sua função, P (x) é o polinômio e E (x) é o erro de arredondamento. Você não quer otimizar | f (x) - P (x) |, você deseja otimizar | f (x) - P (x) +/- E (x) | Você obterá um polinômio ligeiramente diferente que tenta manter os erros polinomiais baixos onde o erro de arredondamento é grande e relaxa os erros polinomiais um pouco, onde o erro de arredondamento é pequeno.
Tudo isso fará com que você facilmente arredonde erros de no máximo 0,55 vezes o último bit, onde +, -, *, / tenha erros de arredondamento de no máximo 0,50 vezes o último bit.
fonte
No que se refere função trigonométrica como
sin()
,cos()
,tan()
não houve nenhuma menção, depois de 5 anos, de um aspecto importante de funções trigonométricas alta qualidade: redução Gama .Um passo inicial em qualquer uma dessas funções é reduzir o ângulo, em radianos, para um intervalo de 2 * π. Mas π é irracional, de modo que reduções simples como
x = remainder(x, 2*M_PI)
introduzir erro comoM_PI
ou pi de máquina são uma aproximação de π. Então, como fazerx = remainder(x, 2*π)
?As bibliotecas antigas usavam precisão estendida ou programação criada para fornecer resultados de qualidade, mas ainda em um intervalo limitado de
double
. Quando um valor grande era solicitadosin(pow(2,30))
, os resultados eram sem sentido ou0.0
e talvez com um sinalizador de erro definido como algo comoTLOSS
perda total de precisão ouPLOSS
perda parcial de precisão.Uma boa redução de valores grandes para um intervalo como -π a π é um problema desafiador que rivaliza com os desafios da função trigonométrica básica, como
sin()
ela própria.Um bom relatório é a redução de argumentos para grandes argumentos: bom até o último bit (1992). Ele abrange a questão assim: discute a necessidade e como as coisas eram em várias plataformas (SPARC, PC, HP, 30+ outro) e fornece um algoritmo de solução a dá resultados de qualidade para todos
double
a partir-DBL_MAX
deDBL_MAX
.Se os argumentos originais estiverem em graus, ainda que possam ter um valor grande, use
fmod()
primeiro para obter maior precisão. Uma mercadoriafmod()
não apresentará erros e, portanto, proporcionará uma excelente redução de alcance.Várias identidades trigonométricas e
remquo()
oferecem ainda mais melhorias. Amostra: sind ()fonte
A implementação real das funções da biblioteca depende do compilador e / ou provedor da biblioteca específicos. Seja em hardware ou software, seja uma expansão de Taylor ou não, etc., variará.
Sei que isso não ajuda em nada.
fonte
Eles geralmente são implementados em software e não usam as chamadas de hardware correspondentes (isto é, montagem) na maioria dos casos. No entanto, como Jason apontou, estes são específicos da implementação.
Observe que essas rotinas de software não fazem parte das fontes do compilador, mas serão encontradas na biblioteca de correspodificação como o clib ou glibc para o compilador GNU. Consulte http://www.gnu.org/software/libc/manual/html_mono/libc.html#Trig-Functions
Se você deseja maior controle, avalie cuidadosamente o que precisa exatamente. Alguns dos métodos típicos são a interpolação de tabelas de consulta, a chamada de montagem (que geralmente é lenta) ou outros esquemas de aproximação, como Newton-Raphson, para raízes quadradas.
fonte
Se você deseja uma implementação em software, não em hardware, o lugar para procurar uma resposta definitiva para essa pergunta é o Capítulo 5 de Receitas numéricas . Minha cópia está em uma caixa, então não posso dar detalhes, mas a versão curta (se bem me lembro) é que você toma
tan(theta/2)
como sua operação primitiva e calcula as outras a partir daí. O cálculo é feito com uma aproximação de série, mas é algo que converge muito mais rapidamente do que uma série de Taylor.Desculpe, não posso me lembrar mais sem colocar minha mão no livro.
fonte
Não há nada como acessar a fonte e ver como alguém realmente fez isso em uma biblioteca de uso comum; vejamos uma implementação de biblioteca C em particular. Eu escolhi o uLibC.
Aqui está a função sin:
http://git.uclibc.org/uClibc/tree/libm/s_sin.c
que parece lidar com alguns casos especiais e, em seguida, realiza alguma redução de argumento para mapear a entrada para o intervalo [-pi / 4, pi / 4] (dividindo o argumento em duas partes, uma grande parte e uma cauda) antes de ligar
http://git.uclibc.org/uClibc/tree/libm/k_sin.c
que então opera nessas duas partes. Se não houver cauda, uma resposta aproximada será gerada usando um polinômio de grau 13. Se houver uma cauda, você receberá uma pequena adição corretiva com base no princípio de que
sin(x+y) = sin(x) + sin'(x')y
fonte
Sempre que essa função é avaliada, em algum nível, é mais provável:
Se não houver suporte de hardware, o compilador provavelmente usará o último método, emitindo apenas código do assembler (sem símbolos de depuração), em vez de usar a biblioteca ac - tornando complicado rastrear o código real no depurador.
fonte
Como muitas pessoas apontaram, isso depende da implementação. Mas, pelo que entendi, você estava interessado em uma verdadeira implementação software das funções matemáticas, mas simplesmente não conseguiu encontrar uma. Se for esse o caso, aqui está você:
dosincos.c
localizado em pasta glibc root \ sysdeps \ ieee754 \ dbl-64 descompactadaVocê também pode dar uma olhada nos arquivos com a
.tbl
extensão, seu conteúdo nada mais é do que enormes tabelas de valores pré-computados de diferentes funções em uma forma binária. É por isso que a implementação é tão rápida: em vez de calcular todos os coeficientes de qualquer série que eles usem, eles fazem uma pesquisa rápida, que é muito mais rápida. Aliás, eles usam a série Tailor para calcular seno e cosseno.Eu espero que isso ajude.
fonte
Vou tentar responder pelo caso de
sin()
um programa C, compilado com o compilador C do GCC em um processador x86 atual (digamos, um Intel Core 2 Duo).Na linguagem C, a Biblioteca C padrão inclui funções matemáticas comuns, não incluídas na própria linguagem (por exemplo
pow
,sin
ecos
para poder, seno e cosseno, respectivamente). Os cabeçalhos estão incluídos no math.h .Agora em um sistema GNU / Linux, essas funções de bibliotecas são fornecidas pelo glibc (GNU libc ou GNU C Library). Mas o compilador GCC deseja que você vincule à biblioteca matemática (
libm.so
) usando o-lm
sinalizador do compilador para permitir o uso dessas funções matemáticas.Não sei por que não faz parte da biblioteca C padrão.Essa seria uma versão de software das funções de ponto flutuante ou "flutuação suave".Além disso: O motivo para separar as funções matemáticas é histórico e pretendia apenas reduzir o tamanho dos programas executáveis em muito sistemas Unix antigos, possivelmente antes que as bibliotecas compartilhadas estivessem disponíveis, até onde eu saiba.
Agora, o compilador pode otimizar a função da biblioteca C padrão
sin()
(fornecida porlibm.so
) para ser substituída por uma chamada para uma instrução nativa da função sin () interna da CPU / FPU, que existe como uma instrução FPU (FSIN
para x86 / x87) em processadores mais recentes, como a série Core 2 (isso está correto desde o i486DX). Isso dependeria dos sinalizadores de otimização passados para o compilador gcc. Se o compilador fosse instruído a escrever o código que seria executado em qualquer processador i386 ou mais recente, isso não faria tal otimização. O-mcpu=486
sinalizador informaria ao compilador que era seguro fazer essa otimização.Agora, se o programa executasse a versão do software da função sin (), o faria com base no algoritmo CORDIC (Computador de Coordenação de Rotação Coordenada) ou BKM , ou mais provavelmente em um cálculo de tabela ou série de potências que é usado agora para calcular tais funções transcendentais. [Src: http://en.wikipedia.org/wiki/Cordic#Application]
Qualquer versão recente (desde 2,9x aprox.) Do gcc também oferece uma versão interna do sin,
__builtin_sin()
que será usada para substituir a chamada padrão para a versão da biblioteca C, como uma otimização.Tenho certeza de que isso é tão claro quanto a lama, mas espero que lhe dê mais informações do que você esperava e muitos pontos de partida para aprender mais.
fonte
Se você quiser examinar a implementação real do GNU dessas funções em C, confira o último tronco da glibc. Veja a Biblioteca C GNU .
fonte
Não use a série Taylor. Os polinômios de Chebyshev são mais rápidos e precisos, conforme apontado por algumas pessoas acima. Aqui está uma implementação (originalmente da ROM do ZX Spectrum): https://albertveli.wordpress.com/2015/01/10/zx-sine/
fonte
Computar seno / cosseno / tangente é realmente muito fácil de fazer através do código usando a série Taylor. Escrever um você mesmo leva cerca de 5 segundos.
Todo o processo pode ser resumido com esta equação aqui:
Aqui estão algumas rotinas que escrevi para C:
fonte
Versão aprimorada do código da resposta de Blindy
fonte
A essência de como isso ocorre está no trecho da Análise Numérica Aplicada de Gerald Wheatley:
Alguns pontos a serem mencionados acima são que alguns algoritmos interpolam a partir de uma tabela, embora apenas nas primeiras iterações. Observe também como ele menciona que os computadores utilizam polinômios aproximados sem especificar qual tipo de polinômio aproximado. Como outros membros do segmento apontaram, os polinômios de Chebyshev são mais eficientes do que os polinômios de Taylor nesse caso.
fonte
se você quiser
sin
entãose você quiser
cos
entãose você quiser
sqrt
entãoentão, por que usar código impreciso quando as instruções da máquina serão úteis?
fonte