Algoritmo de Horner para polinómios

Discussão e duas implementações: imperativa vs funcional

As funções mais simples em matemática são os polinómios. Um polinómio é uma função com a forma latex2png equation Como é fácil de ver para calcular o valor do polinómio num ponto é apenas necessário fazer umas quantas multiplicações e somas. A maneira mais eficiente de calcular o valor do polinómio num ponto, isto é, efectuando o menor número de produtos e somas, é conseguido através do algoritmo de Horner. Consiste em factorizar o polinómio na seguinte forma: latex2png equation

A maneira mais simples de pensar numa implementação computacional é considerar a sucessão latex2png equation onde o resultado final é latex2png equation

Mais geralmente pode por-se latex2png equation com latex2png equation

Apesar da sua forma simples e definida por recurrência a sucessão de valores é mais clara e simples quando construída de uma forma imperativa do que a sua versão funcional. Se não veja-se. A implementação funcional fica:

(defun horner-eval (x coef)
  (accumulate (lambda (a b)
                (+ a (* b x)))
              0
              coef))

(defun accumulate (op initial sequence)
  (if (not sequence)
      initial
      (funcall op (car sequence)
          (accumulate op initial (cdr sequence)))))

enquanto a versão imperativa do mesmo algoritmo tem a forma:

(defun polyval (x coef)
  (let ((coefx coef) (px 0))
    (while coefx
      (setq px (+ (* x px)  (car coefx)))
      (setq coefx (cdr coefx)))
    px))
Palavras chave/keywords: algoritmo, Horner, Lisp, Emacs

Última actualização/Last updated: 2014-02-20 [14:38]


1999-2014 (ç) Tiago Charters de Azevedo

São permitidas cópias textuais parciais/integrais em qualquer meio com/sem alterações desde que se mantenha este aviso.

Verbatim copying and redistribution of this entire page are permitted provided this notice is preserved.