Algebraic Functions
Operation | Input | Output | Algorithm | Complexity |
---|---|---|---|---|
Polynomial evaluation | One polynomial of degree n with fixed-size polynomial coefficients | One fixed-size number | Direct evaluation | Θ(n) |
Horner's method | Θ(n) | |||
Polynomial gcd (over Z or F) | Two polynomials of degree n with fixed-size polynomial coefficients | One polynomial of degree at most n | Euclidean algorithm | O(n2) |
Fast Euclidean algorithm | O(n (log n)2 log log n) |
Read more about this topic: Computational Complexity Of Mathematical Operations
Famous quotes containing the words algebraic and/or functions:
“I have no scheme about it,no designs on men at all; and, if I had, my mode would be to tempt them with the fruit, and not with the manure. To what end do I lead a simple life at all, pray? That I may teach others to simplify their lives?and so all our lives be simplified merely, like an algebraic formula? Or not, rather, that I may make use of the ground I have cleared, to live more worthily and profitably?”
—Henry David Thoreau (18171862)
“Nobody is so constituted as to be able to live everywhere and anywhere; and he who has great duties to perform, which lay claim to all his strength, has, in this respect, a very limited choice. The influence of climate upon the bodily functions ... extends so far, that a blunder in the choice of locality and climate is able not only to alienate a man from his actual duty, but also to withhold it from him altogether, so that he never even comes face to face with it.”
—Friedrich Nietzsche (18441900)