Calculadora de aproximação de Chebyshev

 (stuffmatic.com)
2 pontos por GN⁺ 2024-10-06 | 1 comentários | Compartilhar no WhatsApp
  • Chebyshev approximation calculator é uma ferramenta que gera na web código para aproximação de funções matemáticas
  • O usuário pode especificar a função a aproximar, o intervalo e o número de termos usando f(x), x min, x max e Terms
  • A opção Match x min x max e a área Coefficients oferecem um fluxo para verificar ou ajustar os limites do intervalo e os valores dos coeficientes
  • Na área Generated code, o resultado do cálculo é exibido em forma de código; na tela de exemplo, aparecem os coeficientes de c0 a c10
  • Há um repositório no GitHub vinculado, permitindo conferir diretamente o código de implementação da ferramenta web

Gerador de código de aproximação de Chebyshev

  • Chebyshev approximation calculator gera código para aproximar funções matemáticas de forma eficiente
  • As condições de aproximação são inseridas na UI web
    • f(x): função a aproximar
    • x min: valor mínimo do intervalo
    • x max: valor máximo do intervalo
    • Terms: número de termos a usar
    • Match x min x max: opção relacionada aos limites do intervalo

Verificação de coeficientes e código gerado

  • A tela é dividida entre a área Coefficients e a área Generated code
  • Os coeficientes exibidos como exemplo podem ser verificados de c0 a c10
    • c0 = 0.16793649417016518
    • c1 = -0.12411164956092625
    • c2 = -0.09756341588422193
    • c3 = 0.1800765790518846
    • c4 = -0.06972963647223016
    • c5 = -0.09250127939333941
    • c6 = 0.18076946080324185
    • c7 = 0.15990613621816677
    • c8 = -0.028659588693985123
    • c9 = -0.09494966104347571
    • c10 = -0.04980429834982578
  • A tela também exibe itens de coeficientes de c11 a c39

Repositório de código

Leituras relacionadas

1 comentários

 
GN⁺ 2024-10-06
Opiniões no Hacker News

  • Muito legal. Por volta de 1974, escrevi uma função para calcular raiz quadrada em assembly do IBM 360 e fui pago por isso
    Eu estava no último ano da graduação e me pediram para torná-la o mais eficiente possível. Depois de escalar a entrada para ficar entre 0 e 1, usei uma aproximação de Chebyshev para a estimativa inicial e cheguei à solução aplicando 2 ou 3 iterações desenroladas do método de Newton. Foi meu primeiro dinheiro recebido por escrever código

    • Gosto desse tipo de história. Ainda me lembro de como minha cabeça se abriu na primeira aula de análise numérica, quando percebi pela primeira vez o potencial da computação

  • Muito bem feito. Fiquei fascinado com a eficiência dessas aproximações e passei a entender muito melhor por que as implementações de funções trigonométricas ou outras funções matemáticas em computadores de 8 bits eram feitas daquele jeito
    Também há um ótimo documento original de 1969 do BBC Research Department explicando por que esse método é excelente: https://downloads.bbc.co.uk/rd/pubs/reports/1969-10.pdf
    Se você só viu aproximações de Taylor, no começo pode parecer um pouco mágico

    • Sim. Tanto pelo lado matemático quanto pelo fato de que, na prática, tudo acaba virando algumas linhas de código, parece mesmo bem mágico

  • Já obtive bons resultados com Sollya antes: https://www.sollya.org/
    Dito isso, embora os resultados tenham sido bons, o software em si é meio trabalhoso de usar

    • Sollya provavelmente é a melhor ferramenta moderna para esse tipo de tarefa. Internamente, ele faz uma aproximação de Remez e depois quantiza para ponto flutuante com LLL; não usa Chebyshev diretamente

  • Ao aproximar Math.sin(x)/x, ou seja, a função sinc, no intervalo [-3,3] com 7 termos, todos os coeficientes c0...c6 viram NaN. É um bug?
    Como solução temporária, forcei simplesmente para 1.0 quando x está perto de 0
    if(Math.abs(x) > 1e-8 ){ Math.sin(x)/x } else { 1.0 }

    • É difícil dizer que é exatamente um bug. O código provavelmente avalia a função em pontos de grade como x_j = (xmin) + (xmax - xmin)/2(1 + cos(pi[0..j-1]/(j-1)) para obter os coeficientes de Chebyshev; se um deles for exatamente 0, ele acaba calculando Math.sin(0)/0, resultando em NaN
      Outra forma de contornar é usar um intervalo ligeiramente assimétrico, como [-3,+3.0000001]
    • O problema aqui é que a primeira expressão não está bem definida em x=0, e parece que o código de aproximação tropeçou ali. O código deixa um pouco a desejar
    • Sim, é um bug. Se a função não estiver definida em todos os nós de Chebyshev, o app deveria mostrar um erro. Como você já descobriu, por enquanto dá para contornar facilmente

  • Polinômios de Chebyshev são tão poderosos e versáteis em aproximações que as pessoas acham que são bons demais para ser verdade e acabam não usando
    A primeira tentativa deveria ser Chebyshev. Redes neurais deveriam ser o último recurso

  • Excelente. Recentemente eu quis fazer algo assim, e foi surpreendentemente difícil encontrar código que calculasse a aproximação
    Deixei nos favoritos para usar na próxima vez que precisar aproximar uma função rapidamente

    • Também fiquei surpreso com a dificuldade de encontrar código de aproximação de Chebyshev que realmente funcione. Espero que este projeto mude isso

  • Chebyshev parece magia negra. Mesmo depois de ver a derivação em uma disciplina de pós-graduação, ainda sinto isso

  • Também é obrigatório mencionar o Chebfun, de Nick Trefethen e outros. É uma ferramenta que estende essa ideia em praticamente todas as direções imagináveis
    Chebfuns podem ser vistos como o equivalente, para funções, dos números de ponto flutuante para números matemáticos reais. É um software realmente impressionante
    https://www.chebfun.org

    • Concordo. Os métodos deles são muito poderosos e rápidos. Usando Chebyshev e técnicas baseadas em funções ultrasféricas, dá para aproximar a maioria das funções muito rapidamente com precisão de máquina e depois manipular essa representação com mais facilidade
      Isso permite vários métodos, como encontrar soluções de equações diferenciais algébricas com precisão de máquina ou encontrar mínimos/máximos globais de funções unidimensionais
      Pelo que sei, hoje eles usam outros algoritmos, mas a metodologia básica que o Chebfun usava antigamente pode ser vista no capítulo 6 do livro de Trefethen Spectral Methods in Matlab. A metodologia mais moderna usando funções ultrasféricas aparece no artigo de Olver e Townsend na SIAM Review, A Fast and Well-Conditioned Spectral Method

  • Tenho uma dúvida, embora não saiba se este é o lugar certo para perguntar. Vi um vídeo dizendo que, antigamente, o Nintendo 64 não tinha capacidade para calcular a função seno, então usava uma tabela de consulta de 0 a 2π, com alguns truques inteligentes para reduzir o tamanho da tabela
    Teria sido possível treinar uma rede neural e armazenar os pesos, ou criar uma função e armazenar os coeficientes, para calcular seno e cosseno?

    • Redes neurais frequentemente usam funções trigonométricas internamente, então isso provavelmente exigiria muito mais computação do que o necessário
      Se sobrassem alguns ciclos de CPU, daria para usar uma aproximação híbrida, usando valores de uma tabela de consulta esparsa como estimativa inicial e repetindo algumas vezes algum método de aproximação numérica. Ou então bastaria armazenar alguns dos primeiros coeficientes de uma aproximação polinomial, como no post original
    • Se você não conhece, vale dar uma olhada em CORDIC. Antigamente era um truque comum para funções trigonométricas e ainda é usado até certo ponto em embarcados
      Redes neurais podem ser úteis quando você tem amostras de alguma função mas não sabe como aproximá-la; aqui, não é esse o caso
    • Claro que é possível treinar uma rede neural para calcular qualquer função, mas para uma função bem conhecida como seno isso não faz sentido nenhum
      Redes neurais são uma ótima solução quando você precisa avaliar algo que não é fácil de analisar matematicamente, mas já existem muitas técnicas conhecidas para calcular e aproximar funções trigonométricas
      Treinar uma rede neural para calcular seno é como a versão matemática de usar um LLM para inverter uma string. Dá para fazer, mas é uma ideia que só surge quando você não sabe que o problema é essencialmente resolvido por uma abordagem mais direta
      Antes de usar técnicas de IA/ML, sempre vale verificar se os matemáticos já têm uma solução. Hoje em dia, é bem possível que muito esforço esteja sendo gasto aplicando IA/ML a problemas para os quais já existe uma solução conhecida, eficiente e até ótima, só que desconhecida pelos desenvolvedores
    • Redes neurais são essencialmente ajuste de curvas, então é possível. Este vídeo pode ajudar: https://www.youtube.com/watch?v=FBpPjjhJGhk But what is a neural network REALLY?
      A principal força das redes neurais aparece quando há muitas entradas, não apenas algumas. Em um caso simples como sin(x), existem outros métodos, como a ferramenta publicada aqui
    • A técnica de economia normalmente usada é armazenar em tabela apenas de 0 a π/2 e gerar os outros três quadrantes com 2 bits extras de índice

  • Muito bacana. Fiquei brincando e quis ver quão rápido eu conseguiria criar uma função que não fosse bem aproximada
    Até agora, a melhor foi Math.cos(x * Math.exp(Math.cos(x * x))). Ela tem muita composição, o que gera oscilações rápidas e inclinações íngremes, tornando difícil aproximá-la facilmente com Chebyshev