FFT rapide : la promesse d’OpenAI à l’épreuve du réel
Une FFT d’OpenAI peut-elle vraiment surpasser l’algorithme classique ? Analysez les coûts cachés, le modèle de calcul et les conséquences pratiques.
FFT rapide : quand le progrès théorique ne fait pas gagner de temps
On annonce une nouvelle FFT plus efficace, et forcément ça attire l'attention. La transformée de Fourier rapide (FFT) est un algorithme central du traitement du signal : on la retrouve en audio, en imagerie, en télécommunications et dans beaucoup de calculs scientifiques. Donc si on peut réduire encore le coût, même un peu, ça ressemble à une bonne nouvelle.
Sauf que dans beaucoup d'annonces théoriques, une question manque : plus rapide dans quel modèle de calcul, et pour des problèmes de quelle taille ? Une complexité asymptotiquement meilleure ne garantit ni un temps d'exécution plus court dans un vrai programme, ni même une méthode réellement exécutable sur la machine du monde réel. Les constantes cachées, la précision numérique et les besoins mémoire peuvent tout changer.
C'est précisément le cœur d'une critique liée à un travail d'OpenAI sur la FFT : le résultat peut être intéressant sur le plan mathématique tout en restant peu exploitable en pratique. Pour comprendre l'écart, il faut revenir à la FFT classique, distinguer la notation Big O de la performance mesurée, puis regarder le modèle de calcul supposé. Voici une façon simple d'évaluer ce type de promesse sans confondre progrès théorique et gain opérationnel.
Pourquoi la FFT classique est déjà rapide
La transformée de Fourier discrète (TFD) décompose un signal en fréquences. Concrètement, on peut la voir comme une série de produits scalaires : pour chaque fréquence analysée, on combine les échantillons du signal avec des coefficients complexes. Si le signal contient n valeurs et qu'on calcule séparément les n fréquences, l'approche directe coûte de l'ordre de n² opérations.
Cette approche reste compréhensible sur de petites tailles. Mais dès que n grandit, ça explose vite : multiplier la taille du signal par dix multiplie presque par cent le nombre d'opérations. Pour de gros volumes, ce n'est pas un détail.
Le principe de Cooley-Tukey
La FFT classique réduit ce coût en exploitant la structure de la transformée. L'algorithme associé à James Cooley et John Tukey (publié en 1965) réorganise les calculs : il découpe en des transformées plus petites, puis combine les résultats. En répétant cette décomposition, on obtient un coût en O(n log n) au lieu de O(n²).
L'idée clé est là : la FFT ne recalcule pas naïvement tout depuis zéro. Elle réutilise des calculs intermédiaires. Pour donner un ordre de grandeur : à n = 1 000, on passe d'environ un million d'opérations (approche directe) à quelque chose de l'ordre de dizaines de milliers (FFT). À n plus grand, l'écart se creuse encore.
Les chiffres exacts dépendent de l'implémentation, de la taille, du matériel et du type d'opération compté. Une estimation « pédagogique » n'est donc pas un benchmark. Mais le point solide reste simple : la FFT fait déjà basculer un calcul quadratique vers un comportement quasi linéaire.
Pourquoi chercher encore mieux ?
La recherche est légitime. Si on doit produire n valeurs en sortie, on s'attend au minimum à un coût qui croît avec n, ne serait-ce que pour écrire la sortie. La FFT classique ajoute un facteur logarithmique. Réduire ce surcoût peut compter, notamment quand on enchaîne les transformations à grande fréquence.
Mais « meilleur » ne veut rien dire tout seul. Une amélioration théorique se discute sur le comportement quand n tend vers l'infini. Une équipe qui traite des signaux sur un serveur, un appareil embarqué ou une infrastructure cloud veut plutôt savoir : combien de temps et de mémoire ça coûte sur les tailles qu'on rencontre vraiment.
C'est là que la discussion autour du résultat attribué à OpenAI devient utile : pas parce qu'un nouvel exposant serait automatiquement une victoire, mais parce que la complexité seule ne répond pas à toutes les questions d'ingénierie.
Ce que la notation Big O ne vous dit pas
La notation O(F(n)) dit qu'à partir d'un certain seuil, le temps d'exécution est borné par une constante multipliée par F(n). C'est une description asymptotique. Utile pour comparer des familles d'algorithmes quand le problème devient très grand, mais insuffisant pour prédire un temps d'exécution concret.
Deux algorithmes peuvent être en O(n) et pourtant avoir des performances très différentes. L'un peut faire quelques dizaines d'opérations par élément. L'autre peut en faire des millions. Et parfois, la borne asymptotique ne devient pertinente qu'au-delà d'une taille qu'on n'atteint jamais en pratique. Le « O » ne vous dit ni si la constante est petite, ni si le seuil est raisonnable.
La constante cachée et le seuil de bascule
Imaginez deux coûts simplifiés : une méthode classique en a n log n et une nouvelle méthode en C n log log n. Sur le papier, la seconde peut gagner car log log n grandit plus lentement que log n. Sauf que si C est énorme, la nouvelle méthode ne devient « meilleure » qu'à des tailles de problème hors d'atteinte.
Le point de bascule dépend donc de la constante, des autres termes et de la machine. Un résultat qui prouve l'existence d'une constante ne garantit pas qu'on sache quelle valeur elle prend, ni si elle est compatible avec des tailles réalistes. Dans la critique du résultat d'OpenAI, l'auteur décrit l'algorithme comme « galactique » : ses constantes seraient tellement grandes que la FFT classique resterait plus rapide pour toutes les tailles qu'on peut raisonnablement manipuler.
Il faut lire cette formulation comme un argument de la critique, pas comme un benchmark indépendant. Mais ça pointe vers un vrai problème : une amélioration asymptotique peut être rigoureusement vraie et pourtant ne rien changer pour un produit.
Un exemple plus concret que l'exposant
Avant de remplacer une FFT utilisée en production, il faut répondre à des questions simples :
- Quelle taille de signal traite-t-on réellement (aujourd'hui et à moyen terme) ?
- Quel est le temps d'exécution sur le matériel cible ?
- Combien de mémoire supplémentaire l'algorithme consomme ?
- À partir de quelle taille bat-il la FFT de référence ?
- Ce seuil est-il mesuré ou déduit d'une borne ?
Si une FFT met quelques millisecondes et que la nouvelle approche ne gagne qu'au-delà d'une taille qui ne tient pas en mémoire, la différence de complexité ne justifie pas une migration. À l'inverse, une amélioration modeste mais mesurée sur vos tailles réelles peut valoir de l'or, même si elle ne change pas l'exposant asymptotique.
En pratique, il faut séparer trois affirmations : « la borne est meilleure », « l'algorithme est implémentable », « le programme est plus rapide sur notre charge ». Elles sont liées, mais ce n'est pas la même chose.
Le modèle de calcul peut rendre un résultat impraticable
Une analyse de complexité dépend d'un modèle : elle compte des opérations selon une hypothèse. Le modèle classique suppose souvent que chaque opération arithmétique sur un nombre coûte une unité, quelle que soit la taille réelle du nombre. C'est commode pour raisonner. C'est rarement une description fidèle de ce qu'un ordinateur fait réellement.
Dans le cas discuté, l'algorithme s'appuierait sur une arithmétique complexe exacte, avec des nombres dont la magnitude augmente très vite avec la taille du problème. L'objection critique est simple : sur une machine réelle, représenter un nombre plus grand (ou plus précis) demande plus de bits. Donc le coût d'une multiplication ne reste pas constant.
Une opération n'a pas toujours un coût unitaire
Les processeurs travaillent avec des nombres à précision finie. Certaines bibliothèques utilisent aussi des formats à précision arbitraire, mais alors elles doivent stocker plus de chiffres et effectuer davantage de travail interne. Une multiplication sur des nombres de plusieurs milliers de bits n'a rien à voir, en coût, avec une multiplication sur des nombres « machine » classiques.
Si un algorithme suppose qu'une multiplication de deux entiers (ou nombres complexes) arbitrairement grands coûte une étape, sa complexité compte une opération abstraite, pas le travail complet d'une implémentation réelle. La différence peut se traduire en temps, en mémoire, et même en stabilité numérique. Le fait que « le théorème est propre » dans son propre modèle ne corrige pas ça.
En ingénierie, ce cas est familier : un modèle peut être cohérent et utile pour une question précise, tout en oubliant exactement les coûts qui font (ou cassent) un système. Le problème apparaît quand on sort le résultat de ses hypothèses et qu'on le présente comme une accélération directement déployable.
Précision numérique et stabilité
Les calculs de Fourier utilisent des nombres complexes et enchaînent des opérations. Avec des données finies, les arrondis s'accumulent. Donc on ne juge pas seulement « combien d'opérations » : il faut aussi vérifier que les erreurs restent acceptables pour l'usage visé.
En analyse théorique de la FFT, des travaux classiques discutent des limites de vitesse avec des hypothèses sur les coefficients et sur la stabilité. L'article source cite notamment des travaux de Jacques Morgenstern et de Nir Ailon. Ces résultats ne suffisent pas à eux seuls pour régler les détails d'implémentation : les hypothèses et les modèles ne sont pas forcément les mêmes. Mais ils rappellent un point : la vitesse et le comportement numérique ne sont pas des sujets séparés.
En audio, une petite erreur peut ne pas être audible. En calcul scientifique, ou dans une chaîne où l'erreur se propage, la tolérance n'a rien d'automatique. La précision acceptable doit être définie par l'application, pas « supposée universelle ».
« Théoriquement plus rapide » n'est pas « prêt à déployer »
Pour transformer un résultat abstrait en outil, il faut au minimum : une description assez précise pour écrire l'algorithme, une estimation réaliste du coût des opérations, une analyse mémoire, une discussion de stabilité, et des tests reproductibles. Sans ça, on n'a pas encore une solution de production.
La théorie n'est pas inutile pour autant. Elle peut montrer qu'une possibilité existe sous certaines hypothèses et ouvrir des pistes. Mais il faut appeler les choses par leur nom : une avancée dans un modèle de calcul, pas forcément une FFT plus rapide sur les machines que vous utilisez.
Comment évaluer une annonce d'algorithme
Face à une annonce de progrès algorithmique, l'objectif n'est pas de choisir entre enthousiasme et rejet. Il faut d'abord comprendre ce que prouve exactement la démonstration, puis vérifier si ça répond au besoin concret. Cette méthode marche pour la FFT, mais aussi pour la multiplication matricielle, le chiffrement ou l'optimisation.
1. Vérifier la tâche et la comparaison
Commencez par clarifier le problème. L'algorithme calcule-t-il exactement la même transformée, avec les mêmes contraintes de précision et les mêmes exigences de sortie ? La comparaison porte-t-elle sur une FFT largement utilisée, une implémentation naïve, ou un algorithme théorique « de référence » ? Une borne n'a de sens que si l'objet comparé est clairement défini.
Regardez aussi si les hypothèses concernent des entrées arbitraires ou un cas particulier. Un gain qui marche pour certaines tailles, certaines structures de données ou certaines distributions peut être utile. Mais il ne faut pas le vendre comme général si ce n'est pas le cas.
2. Lire le modèle de calcul avant le résultat
Avant de regarder les équations, identifiez ce que l'analyse compte comme une opération élémentaire. Les nombres ont-ils une précision fixe ? Les opérations sur des nombres « longs » sont-elles comptées en fonction de leur taille ? La mémoire est-elle prise en compte ? Le modèle autorise-t-il une opération exacte irréalisable sur du matériel réel ?
Ce n'est pas une manière de disqualifier à l'aveugle. C'est surtout pour savoir à quelle question le résultat répond.
3. Examiner les constantes et le seuil pratique
Si la publication donne des constantes, essayez d'estimer le coût sur les tailles qui vous intéressent. Si elle ne les donne pas, demandez ce qui empêche de les calculer ou de borner le seuil.
Une complexité asymptotique sans estimation du seuil de bascule ne suffit pas à décider une migration d'architecture.
Un bon test consiste à construire une comparaison honnête : mêmes entrées, même précision, même matériel, mêmes contraintes mémoire. Et les cas de test doivent couvrir les tailles courantes comme les situations défavorables, pas seulement un exemple qui maximise l'avantage.
4. Demander un algorithme exécutable et des mesures
Une preuve d'existence, un pseudo-code, une implémentation de recherche et une bibliothèque maintenue ne sont pas le même livrable. Si vous voulez adopter quelque chose en pratique, vous devez savoir comment reproduire le résultat, avec quels paramètres, et si les performances tiennent en dehors d'une démo.
Les mesures ne remplacent pas la théorie : un benchmark isolé ne prouve pas une complexité « meilleure ». Mais inversement, la théorie ne remplace pas les mesures quand on doit choisir un composant pour un système en production. Les deux servent à répondre à des questions différentes.
Grille de décision rapide
- Preuve sans implémentation : résultat théorique à suivre, pas candidat direct au déploiement.
- Implémentation sans comparaison complète : prototype à auditer et à benchmarker.
- Gain mesuré sur vos tailles et votre matériel : piste sérieuse, à condition de vérifier précision et maintenance.
- Gain seulement au-delà de tailles irréalistes : intérêt mathématique possible, bénéfice opérationnel nul pour votre cas.
Cette distinction évite deux erreurs symétriques : croire qu'un résultat théorique est forcément une innovation utilisable, ou supposer qu'un résultat peu pratique n'a aucune valeur scientifique. La vraie question reste : quel problème le résultat résout, et dans quel horizon ?
Conclusion : demander des mesures, pas seulement une borne
Une nouvelle borne de complexité peut être mathématiquement remarquable sans pour autant accélérer les calculs d'une équipe. Dans le cas discuté, la critique met en avant deux obstacles concrets : des constantes potentiellement énormes et un modèle d'arithmétique exacte éloigné des contraintes matérielles. Autrement dit : la preuve et l'usage pratique ne posent pas la même question.
La bonne approche consiste à vérifier : le problème traité, les hypothèses de calcul, les coûts « invisibles », le seuil de bascule, et les mesures sur le matériel cible. Si le résultat ne s'implémente pas facilement, ou s'il ne gagne que pour des tailles irréalistes, il faut le présenter comme un résultat théorique, pas comme une amélioration opérationnelle.
En ingénierie, une solution imparfaite mais déployable, mesurée et adaptée au besoin vaut souvent mieux qu'une promesse élégante sans chemin vers l'exécution. Avant de remplacer votre bibliothèque FFT, documentez vos tailles réelles, vos contraintes de précision, et mettez en place un protocole de benchmark reproductible. C'est là que commence la décision technique.
Pour approfondir l'argument d'origine, consultez l'analyse publiée sur argmin.