Calculateur d’approximation de Chebyshev

• Chebyshev approximation calculator est un outil qui génère sur le web du code d’approximation de fonctions mathématiques
• L’utilisateur peut définir la fonction à approximer, l’intervalle et le nombre de termes avec f(x), x min, x max, Terms
• L’option Match x min x max et la zone Coefficients permettent de vérifier ou d’ajuster les valeurs des coefficients ainsi que les bornes de l’intervalle
• La zone Generated code affiche le résultat du calcul sous forme de code, et l’écran d’exemple montre les coefficients de c0 à c10
• Un dépôt GitHub est lié, ce qui permet de consulter directement le code d’implémentation de l’outil web

---

Générateur de code d’approximation de Chebyshev

• Chebyshev approximation calculator génère du code pour approximer efficacement des fonctions mathématiques
• Les conditions d’approximation sont saisies dans l’interface web
  • f(x): fonction à approximer
  • x min: valeur minimale de l’intervalle
  • x max: valeur maximale de l’intervalle
  • Terms: nombre de termes à utiliser
  • Match x min x max: option liée aux bornes de l’intervalle

Vérification des coefficients et code généré

• L’écran est divisé en une zone Coefficients et une zone Generated code
• Dans l’exemple affiché, on peut voir les coefficients de c0 à 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
• Des entrées de coefficients allant de c11 à c39 sont également affichées à l’écran

Dépôt de code

• Dépôt GitHub associé : stuffmatic/chebyshev-calculator

[GN⁺]

Commentaires sur Hacker News

• Super. Vers 1974, j’ai été payé pour écrire une fonction de calcul de racine carrée en assembleur IBM 360.
  J’étais en dernière année de licence, et on m’avait demandé de la rendre aussi efficace que possible. Après avoir mis l’entrée à l’échelle entre 0 et 1, j’utilisais une approximation de Tchebychev pour l’estimation initiale, puis j’appliquais deux ou trois itérations déroulées de la méthode de Newton pour obtenir la solution. C’était le premier argent que j’ai gagné en écrivant du code.

  • J’adore ce genre d’histoire. Je me souviens encore de mon premier cours d’analyse numérique, où j’ai vraiment pris conscience du potentiel du calcul ; ça m’avait ouvert les yeux.

• Vraiment très bien fait. Je suis fasciné par l’efficacité de ce type d’approximation, et j’ai beaucoup mieux compris pourquoi les implémentations des fonctions trigonométriques ou d’autres fonctions mathématiques sur les ordinateurs 8 bits étaient faites de cette manière.
  Il existe aussi un excellent document original du BBC Research Department datant de 1969 qui explique pourquoi cette approche est si bonne : https://downloads.bbc.co.uk/rd/pubs/reports/1969-10.pdf
  Si l’on n’a vu que les approximations de Taylor, cela peut sembler un peu magique au début.

  • Oui. Le côté mathématique, mais aussi le fait qu’en pratique cela se résume à quelques lignes de code, donnent vraiment une impression de magie.

• J’ai déjà obtenu de bons résultats avec Sollya : https://www.sollya.org/
  Cela dit, même si les résultats étaient bons, le logiciel lui-même est un peu pénible à utiliser.

  • Sollya est probablement le meilleur outil moderne pour ce genre de tâche. En interne, il fait plutôt une approximation de Remez, puis quantifie en virgule flottante avec LLL ; il n’utilise pas directement Tchebychev.

• Si l’on approxime Math.sin(x)/x, c’est-à-dire la fonction sinc, sur l’intervalle [-3,3] avec 7 termes, tous les coefficients c0...c6 deviennent NaN. C’est un bug ?
  Comme contournement temporaire, j’ai simplement forcé la valeur à 1.0 quand x est proche de 0.
  if(Math.abs(x) > 1e-8 ){ Math.sin(x)/x } else { 1.0 }

  • Difficile de dire que c’est exactement un bug. Le code évalue probablement la fonction sur des points de grille du type x_j = (xmin) + (xmax - xmin)/2(1 + cos(pi[0..j-1]/(j-1)) pour calculer les coefficients de Tchebychev ; si l’un d’eux vaut exactement 0, il calcule Math.sin(0)/0, ce qui donne NaN.
    Une autre solution de contournement consiste à utiliser un intervalle légèrement asymétrique, comme [-3,+3.0000001].
  • Le problème ici, c’est que la première expression n’est pas bien définie en x=0, et le code d’approximation semble trébucher à cet endroit. Le code est un peu décevant.
  • Oui, c’est un bug. Si la fonction n’est pas définie à tous les nœuds de Tchebychev, l’application devrait afficher une erreur. Comme tu l’as déjà trouvé, c’est facile à contourner pour l’instant.

• Les polynômes de Tchebychev sont tellement puissants et polyvalents pour l’approximation que les gens ont l’impression que c’est trop beau pour être vrai, et finissent par ne pas les utiliser.
  La première méthode à essayer devrait être Tchebychev. Les réseaux de neurones devraient être le dernier recours.

• Excellent. J’avais récemment envie de faire ce genre de chose, et il était étonnamment difficile de trouver du code pour calculer les approximations.
  Je l’ai ajouté à mes favoris pour la prochaine fois que j’aurai besoin d’approximer rapidement une fonction.

  • J’ai moi aussi été surpris de voir à quel point il était difficile de trouver du code d’approximation de Tchebychev qui fonctionne réellement. J’espère que ce projet changera cela.

• Tchebychev, c’est de la magie noire. Même après avoir vu la dérivation en cours de master, c’est toujours l’impression que ça me donne.

• Il faut absolument mentionner aussi Chebfun, de Nick Trefethen et d’autres. C’est un outil qui étend cette idée dans presque toutes les directions imaginables.
  On peut voir les Chebfuns comme l’équivalent, pour les fonctions, des nombres en virgule flottante pour les nombres mathématiques réels. C’est un logiciel vraiment impressionnant.
  https://www.chebfun.org

  • D’accord. Leurs méthodes sont très puissantes et rapides. Avec des techniques fondées sur Tchebychev et les fonctions ultrasphériques, on peut approximer la plupart des fonctions très rapidement à la précision machine, puis manipuler cette représentation plus facilement.
    Cela permet par exemple de trouver des solutions d’équations algébro-différentielles à la précision machine, ou les minimums/maximums globaux de fonctions à une dimension.
    Je crois qu’ils utilisent aujourd’hui d’autres algorithmes, mais la méthodologie de base qu’utilisait Chebfun auparavant se trouve au chapitre 6 du livre de Trefethen, Spectral Methods in Matlab. La méthodologie plus récente fondée sur les fonctions ultrasphériques est décrite dans l’article d’Olver et Townsend dans SIAM Review, A Fast and Well-Conditioned Spectral Method.

• J’ai une question, je ne sais pas si je peux la poser ici. J’avais vu une vidéo expliquant que la Nintendo 64 n’avait pas la capacité de calculer la fonction sinus, donc elle utilisait une table de correspondance de 0 à 2π, avec aussi des techniques astucieuses pour réduire la taille de la table.
  Aurait-il été possible d’entraîner un réseau de neurones et de stocker ses poids, ou de construire une fonction et de stocker ses coefficients, pour calculer sinus et cosinus ?

  • Les réseaux de neurones utilisent souvent des fonctions trigonométriques en interne, ce qui demanderait beaucoup plus de calculs que nécessaire.
    S’il reste quelques cycles CPU, on peut utiliser une approximation hybride : prendre les valeurs d’une table clairsemée comme estimation initiale, puis appliquer quelques itérations de méthodes d’approximation numérique. Ou bien, comme dans l’article d’origine, stocker seulement les premiers coefficients d’une approximation polynomiale.
  • Si tu ne connais pas, regarde CORDIC. C’était autrefois une astuce courante pour les fonctions trigonométriques, et c’est encore utilisé dans une certaine mesure côté embarqué.
    Les réseaux de neurones peuvent être utiles quand on a des échantillons d’une fonction mais qu’on ne sait pas comment l’approximer ; ici, ce n’est pas le cas.
  • Il est évidemment possible d’entraîner un réseau de neurones pour calculer n’importe quelle fonction, mais pour une fonction bien connue comme le sinus, cela n’a aucun sens.
    Les réseaux de neurones sont une excellente solution quand il faut évaluer quelque chose qui n’est pas facile à analyser mathématiquement, mais il existe déjà de nombreuses techniques connues pour calculer et approximer les fonctions trigonométriques.
    Entraîner un réseau de neurones pour calculer le sinus, c’est un peu l’équivalent mathématique d’utiliser un LLM pour inverser une chaîne de caractères. C’est possible, mais c’est une idée qui vient surtout si l’on ignore qu’il existe une approche plus directe qui résout fondamentalement le problème.
    Avant d’utiliser des techniques IA/ML, il vaut toujours la peine de vérifier si les mathématiciens n’ont pas déjà une solution. De nos jours, il est probable que beaucoup d’efforts soient consacrés à appliquer de l’IA/ML à des problèmes pour lesquels il existe déjà des solutions connues, efficaces, voire optimales, simplement parce que les développeurs ne les connaissent pas.
  • Les réseaux de neurones sont fondamentalement de l’ajustement de courbe, donc oui, c’est possible. Cette vidéo peut aider : https://www.youtube.com/watch?v=FBpPjjhJGhk But what is a neural network REALLY?
    La principale force des réseaux de neurones apparaît quand il y a non pas quelques entrées, mais énormément. Pour un cas simple comme sin(x), il existe d’autres méthodes, comme l’outil présenté ici.
  • La technique d’économie habituellement utilisée consiste à ne stocker en table que l’intervalle de 0 à π/2, puis à générer les trois autres quadrants avec 2 bits d’index supplémentaires.

• Très sympa. Par jeu, j’ai voulu voir à quelle vitesse je pouvais fabriquer une fonction difficile à bien approximer.
  Jusqu’ici, la meilleure que j’aie trouvée est Math.cos(x * Math.exp(Math.cos(x * x))). Avec toutes ces compositions, elle produit des oscillations rapides et des pentes raides, ce qui la rend difficile à approximer facilement avec Tchebychev.