Fast Polynomials - Compute polynomials twice as fast
Fast Polynomials ist ein Online-Tool, das die Auswertung von Polynomen drastisch beschleunigt. Mit einer neuartigen Methode, die auf rationaler Vorverarbeitung basiert, benötigt es nur etwa halb so viele Multiplikationen wie das klassische Horner-Schema. Sie geben einfach ein Polynom ein, wählen einen Körper (z.B. rationale, reelle oder endliche Körper) und erhalten sofort einen optimierten Auswertungsplan – als mathematische Formel, C-Code oder Graph. Die Technik eignet sich für Anwendungen in Kryptografie, Hashing, Codierungstheorie und zur Approximation von Funktionen wie exp, sin oder cos. Das Tool ist ideal für Entwickler und Mathematiker, die Performance-Steigerungen in ihren Projekten suchen.
Mit ein wenig Vorverarbeitung der Koeffizienten genügen für jedes monische Polynom nur ⌊n/2⌋+1 Multiplikationen – das ist fast doppelt so schnell wie Horner!
- pvillano
Das ist super cool. Ich habe eine Menge gelernt, als ich mit der Demo herumgespielt habe. Ich kannte nur Horner und Estrin, aber ich glaube, ich habe die meisten davon jetzt einigermaßen verstanden.
Eine kleine Änderung, die ich empfehlen würde, betrifft die Graph-Visualisierung: Verwende einen separaten Quellknoten für jedes x, x^2, x^4. Eine einzelne x-Quelle macht den Graphen unübersichtlich und verdeckt die Struktur.
- throwaway81523
Wenn du das Polynom vorverarbeitest, willst du es vielleicht an vielen verschiedenen Stellen auswerten. Aber warum dann nicht die FFT verwenden?
- voxelghost
Es springt immer wieder auf 'monic' zurück, z. B. von 'ln(1+x)', wenn man zwischen Algorithmen wechselt, und dann scheint es auf 'monic' festzuhängen? (Übersehe ich etwas?)
Außerdem bin ich neugierig: In deiner Version im Vergleich zu Horner, wie lassen sich beide Algorithmen auf die Anzahl der fmadd-Operationen abbilden?