ISSN:
1436-5057
Keywords:
68C25
;
68C20
;
Analysis of algorithms
;
computational complexity
;
cost complexity
;
Ruffini-Horner method
;
polynomial evaluation
;
polynomial translation
;
computer algebra
;
unlimited precision arithmetic
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Description / Table of Contents:
Zusammenfassung Die Verminderung der Zahl der Multiplikationen bei der Berechnung eines Polynoms und seinen Ableitungen bringt nicht unbedingt eine entsprechende Verminderung der gesamten Berechnungskosten. In dieser Arbeit werden Kosten-Analysen einer Algorithmen-Familie vorgestellt, die alle Ableitungen eines Polynoms mit 3n−2 Multiplikationen oder Divisionen berechnet. Dies repräsentiert eine Verbesserung im Vergleich mit den klassischen Methoden, die 1/2n(n+1) Multiplikationen benötigen. Jedoch offenbart die Analyse die Gegenwart eines Ausgleichs zwischen den Kosten der Multiplikationen bzw. Divivionen und den übrigen Kosten. Dadurch bleibt die Komplexität für alle AlgorithmenO(ξ2 n 3), wie stark auch immer die Verminderung der Zahl der arithmetischen Operationen ist.
Notes:
Abstract Reducing the number of multiplications for the evaluation of a polynomial and its derivatives does not necessarily mean that one should expect a commensurate reduction of the total cost of computation. In this paper we present a cost analysis for a family of algorithms, which computes all derivatives of a polynomial in 3n−2 multiplications or divisions. This represents an improvement over the classical methods, which require 1/2n(n+1) multiplications. The analysis, however, reveals the presence of a multiplications-divisions cost trade-off due to which the cost complexity remainsO(ξ2 n 3) for all algorithms irrespective of any reduction in the number of arithmetic operations.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02246764
Permalink
