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!
- emil-lp
Ich habe dein arXiv-Paper gestern gelesen (oder war es vorgestern).
Glaubst du, dass man damit die algebraische Methode für k-Path beschleunigen kann?
Wenn ja, solltest du nächstes Jahr an der PACE Challenge teilnehmen.
- IsTom
Ziemlich cool, besonders in endlichen Körpern. Allerdings scheinen die Koeffizienten in Q ziemlich schnell zu explodieren?
- 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 verstanden.
Eine kleine Änderung, die ich empfehlen würde, ist, für die Graphvisualisierung einen separaten Quellknoten für jedes verwendete x, x^2, x^4 zu haben. Eine einzelne x-Quelle macht den Graphen unübersichtlich und verdeckt die Struktur.
- throwaway81523
Wenn du das Polynom vorverarbeiten willst, möchtest du es vielleicht an vielen verschiedenen Punkten 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 den Algorithmen wechselt, und dann scheint es auf 'monic' festzuhängen? (Übersehe ich etwas?)
Außerdem bin ich neugierig: Wie lassen sich beide Algorithmen in deiner Version vs. Horner auf die Anzahl der fmadd-Operationen abbilden?