Cálculos precisos e rápidos para números de ponto flutuante usando o exemplo da função seno. Parte 2: libm

Continuo a série de artigos sobre como trabalhar com ponto flutuante. No primeiro artigo, fiz uma breve introdução matemática e mostrei a maneira mais simples e óbvia de calcular o seno com exemplos de programas com diferentes "armadilhas". O artigo de hoje terá um estilo um pouco diferente. Não haverá prática aqui, mas vamos cavar mais fundo na matemática e entrar no Santo dos Santos - o código da biblioteca padrão. Também darei uma resposta à pergunta no final do primeiro artigo. Então vamos.



Alguma matemática de novo



Obviamente, quanto mais rápido a série de Taylor diminui no módulo, menos termos são necessários para atingir a precisão necessária. E assim, ao que parece, o resultado será mais preciso (abaixo isso será discutido com mais detalhes). Para comparação, por exemplo, tome um termo do sétimo grau da série de Taylor (x77!) em x=1.0 e x=0,1... Os valores da expressão serão1,198dez-4 e 1,198dez-onzerespectivamente. Uma grande diferença, não é? Portanto, vamos tentar encontrar uma maneira de reduzir o limite superior do intervalo de cálculo da função seno.



Expansão da série em torno de determinados valores



Para entender esse método, precisamos voltar ao primeiro ano do instituto e relembrar as definições da série Taylor ( wiki ). Resumindo: conhecendo a função e suas derivadas em algum ponto, você pode encontrar os valores da função nas proximidades desse ponto expandindo para uma série de Taylor. Para a função seno, isso significa o seguinte

pecado(x0+Δx)pecado(x0)+pecado(x0)Δx1!+pecado(x0)Δx22!+pecado(x0)Δx33!+



O que essa abordagem nos dá de um ponto de vista prático? Imagine que temos um intervalo de0 antes π/2... Vamos escolher 10 pontos distribuídos linearmente neste intervalo (a escolha não é ótima):x0=0, x1=π/20, x2=2π/20, xEu=Euπ/20... Para cada ponto, calcule a placa com o seno e suas derivadas neste ponto. Agora você pode modificar a função para que ao obter o valorx a função assume o valor mais próximo xEu e dispostas em uma fileira ao redor do ponto xEu, não perto de zero (Δx=x-xEu)



Usando transformações trigonométricas



Se voltarmos ainda mais longe, para as classes superiores da escola, então podemos nos lembrar de uma fórmula muito importante:

pecado(x0+Δx)=pecado(x0)cos(Δx)+cos(x0)pecado(Δx)



E então tudo é igual ao do parágrafo anterior. Selecionamos pontos dentro do intervalo, calculamos o seno e cosseno para eles e, ao chamar a função seno, procuramos o mais próximo e, usando a fórmula acima, calculamos o seno usando um valor pequenoΔx...

Pense em qual desses dois métodos é melhor escolher, mas por enquanto vamos passar da matemática para os cálculos práticos.



Propriedade de distribuição de multiplicação no mundo de ponto flutuante



Tive de pedir conselhos à Internet, como se chama uma(b+c)=umab+umac... Acontece que é uma propriedade distributiva. Voltemos à pergunta que fiz no final da primeira parte. Ou seja, por que expressões matematicamente equivalentesuma(b+c) e umab+umacpode dar resultados diferentes em cálculos de ponto flutuante? A maneira mais fácil de ilustrar isso é com um exemplo. Vamos pegar um sistema hipotético que funciona com números de ponto flutuante no formato decimal com 4 dígitos de precisão. Vamos fingir queb=1,000E0, c=1.234E-2, e uma=5,678E-2... Primeiro, vamos pegar uma expressão com colchetes e calculá-la passo a passo, lembrando de arredondar a cada passo:

1)b+c=1,000E0+1.234E-2=1.012E0

2) uma(b+c)=5,678E-2×1.012E0=5,746E-2

Resposta recebida y=5,746E-2

Agora vamos calcular a segunda expressão da mesma maneira, passo a passo:

umab+umac=5,678E-2×1,000E0+5,678E-2×1.234E-2=5,678E-2+7,007E-4=5.748E-2

Resposta recebida y=5.748E-2

A verdadeira resposta é 0,0574806652.



Como você pode ver, a resposta obtida no segundo caso é muito mais próxima da verdadeira do que no primeiro. Se explicarmos isso nos dedos, imagine que, no primeiro caso, adicionamos o número a 1,0c=1.234E-2nós apenas descartamos os dois últimos dígitos. Eles não existem mais. No segundo caso, o descarte ocorre bem no final, após a multiplicação. Essa. no segundo caso, a (s) operação (ões) de multiplicação são mais precisas.



Parece que você pode terminar com isso, mas dê uma olhada no primeiro método e me diga qual será o resultado do cálculob+c-b... E ... temos uma maneira de arredondar números de ponto flutuante! Não perca este exemplo. Dê a si mesmo tempo para descobrir. O arredondamento de números será usado de forma muito intensa por nós posteriormente neste e nos artigos seguintes.



Vamos notar mais uma característica desta expressão. Imagine que a precisão de 4 dígitos da variável não seja suficiente para nós. O que fazer? E aqui já temos a resposta - para representar o número no formuláriob+ce armazene-o na memória como a soma de dois dígitos. E, consequentemente, execute operações (por exemplo, multiplicação) separadamente para ambos os termos. Essa técnica é descrita com mais detalhes no artigo Adicionando dois números de ponto flutuante sem perda de precisão .



No artigo anterior, também escrevi que o métodouma(b+c)há uma característica desagradável. E é o seguinte. Númeroc sempre truncado no último dígito significativo de um número b... Isso significa que independentemente do númeroc, se um b+cb, então um erro no último sinal é sempre possível, mesmo para pequenas c... Isso não é permitido na abordagem do próximo capítulo.



Como funciona usando a biblioteca GNU como exemplo



Como é? Você escolheu qual dos dois métodos descritos no início do artigo você escolheu para o cálculo preciso do seno? Seja qual for o método escolhido, ambos estão corretos. Além disso, eles são absolutamente idênticos. Acredite em mim, dê uma olhada. Abaixo, usarei fórmulas escolares. Eles são mais fáceis de explicar.



Armado com o conhecimento adquirido no artigo anterior e neste artigo, você pode entender facilmente o código da biblioteca padrão. Vamos abrir o arquivo s_sin.c e encontrar a função __sin lá :

imagem

Seu código é bastante simples. É fácil entender que ele chama um conjunto diferente de funções dependendo dos limites da variável de entrada. Neste artigo, discutiremos a seção de código 218-224 para ângulos 2 ^ -26 <| x | <0,855469. Você pode ver que nesta seção do código, a função do_sin (x, 0) é chamada. Abordaremos esta função com mais detalhes:



imagem



  1. , dx=0 .
  2. 129-130 , abs(x)<0.126, .. x , . , , , .
  3. 136-137. , . x 2 . u x. , 0.345678. u=0.34, 0.005678.
  4. 140-142. ( s ) ( c ) x . , cos(x)=1-c, 1.0, (. ), .
  5. 143. u. , u=0.34 34. sin(u)=sn+ssn, cos(u)=cs+ccs. sn cs — «» u, ssn ccs — .
  6. 144-145. sin(u+x)=(sn+ssn)*(1-c)+(cs+ccs)*s. , , 144-145. — .


Na verdade, descrevi apenas a parte mais simples do cálculo do seno dessa maneira. Há muita matemática deixada para trás. Por exemplo, como você calcula o tamanho de uma mesa e os elementos nela? De onde vieram os números mágicos 0,126 e 0,855469? Quando cortar o cálculo pelo número de Taylor? Correções nos coeficientes da série de Taylor para refinar o resultado.



Tudo isso, é claro, é interessante, mas, objetivamente, o método apresentado tem muitas desvantagens: é necessário calcular o seno (s) e o cosseno (c) simultaneamente, o que exige o dobro de cálculos da série de Taylor 1 . A multiplicação por valores tabulares, como podemos ver, também não é gratuita. Além disso, armazenar uma tabela de 3520 bytes na RAM, obviamente, não é um problema, mas acessá-la (mesmo no cache) pode ser caro.



Portanto, na próxima parte tentaremos nos livrar da placa e calcular o seno no intervalo [0,126, 0,855469] diretamente, mas com mais precisão do que no primeiro capítulo.



Antes de terminar - uma questão de raciocínio rápido. O grande número neste exemplo é 52776558133248 = 3 * 2 44 . De onde veio esse número, não, por exemplo, 2 45 ? Vou formular a questão com mais precisão. Por que o número 3 * 2 N é ideal ao arredondar os números , e não, por exemplo, 2 N + 1 ? Outra pergunta, qual N você deve escolher para arredondar um número para um inteiro?



1 É importante notar que uma vantagem significativa dessa abordagem pode aparecer quando o seno e o cosseno são calculados simultaneamente a partir do mesmo ângulo. A segunda função pode ser calculada quase de graça.



All Articles