Implementações variadas à regra de Horner (Horner's Rules)

Variadic functions são funções que aceitam um número arbitrário de argumentos. No C++, existe uma forma dinâmica de resolução deste tipo de função herdada do C através de variadic arguments. Além de outra, introduzida no C++ moderno, que é de resolução estática e baseada em templates, denominada de variadic templates.

Neste post, o objetivo é mostrar a implementação do método de Horner utilizando estas duas abordagens com variadic, uma que é resolvida em tempo de execução (variadic arguments) e outra em tempo de compilação (variadic templates).



O método de Horner é um algoritmo para transformar um polinômio em um monômio e deixá-lo computacionalmente eficiente. Por exemplo, trocando potência por um encadeamento de multiplicações, onde pode se explorar a caracteristicas de operações similares a SAXPY. Um breve exemplo deste esquema é encontrado em Horner’s Rule na Wolfram MathWorld. Consistindo na transformação do polinômio:Em:

Implementação com variadic arguments

No C++, basta utilizar o header cstdarg, que possui o tipo va_list e as macros: va_start, va_arg e va_end. Que servem para identificar o ponto dos argumentos variadic, bem como iterá-los. Em essência, é muito simples utilizar estes recursos, conforme o código do exemplo a seguir.  Note que nesta implementação o polinômio de maior grau está a esquerda (terceiro argumento) e o primeiro argumento é a quantidade de argumentos da função variadic:

[code language="cpp"]
/* variadic functions */
#include <cstdarg>

//an * x^n + ... + a2 * x^2 + a1 * x^1 + a0
//fold right: (x * (x * ((argn * x) + argm) + argo) ...)
template <typename T>
T va_horner_method(int n, T x, T argn, T argm, ...)
{
T result = axpy(x, argn, argm);
va_list args;
va_start(args, argm);
for (int i = 3; i < n; ++i)
{
T arg = va_arg(args, T);
result = axpy(x, result, arg);
}
va_end(args);
return result;
}
/* variadic functions */
[/code]

Apesar da simplicidade, é necessário ter o mesmo tipo de cuidado que se têm quando se manipula ponteiros. Por exemplo, se você iterar além do número de elementos fornecidos, poderá obter um comportamento não definido e/ou ler dados inválidos.

Implementação com variadic templates

No C++ moderno, uma ampliação no mecanismo de templates foi introduzido para suportar um número variável de argumentos parametrizáveis. Isto é resolvido em tempo de compilação. Neste caso, a expansão deste argumentos podem ser resolvidos por recursividade, demandando uma especialização parcial como caso base. No código abaixo isto deverá ficar um pouco mais claro:

[code language="cpp"]
/* variadic templates */
template <typename T, typename... Ts>
struct Horner
{
constexpr static T apply(T x, T arg0, Ts... args)
{
return axpy(x, Horner<Ts...>::apply(x, args...), arg0);
}
};

template <typename T>
struct Horner<T, T>
{
constexpr static T apply(T x, T arg0, T arg1)
{
return axpy(x, arg1, arg0);
}
};
/* variadic templates */
[/code]

Veja as seguintes chamadas:

[code language="cpp"]
double a = Horner<double, double>::apply(1.0, 2.0, 3.0);
double b = Horner<double, double, double>::apply(1.0, 2.0, 3.0, 4.0);
[/code]

Na primeira chamada, somente o método apply do caso base do tipo Horner será invocado, onde apenas 2 argumentos de template e 3 argumentos no método são requisitos para isso. Na segunda chamada, ocorrerá a seguinte expansão de chamadas:

[code language="cpp"]
axpy(1.0, axpy(1.0, 4.0, 3.0), 2.0);
[/code]

Para obtermos o beneficio da dedução dos argumentos dos templates a função helper abaixo é fornecida:

[code language="cpp"]
/* variadic templates */
//a0 + a1 * x^1 + a2 * x^2 + ... + an * x^n
//fold left: (x * (x * ((argn * x) + argm) + argo) ...)
template <typename T, typename... Ts>
constexpr inline T horner_method(T x, Ts... args)
{
return Horner<Ts...>::apply(x, args...);
}
/* variadic templates */
[/code]

Logo uma chamada com 5 argumentos (e 4 argumentos templates) é feita desta maneira:

[code language="cpp"]
double c = horner_method(1.0, 2.0, 3.0, 4.0, 5.0);
[/code]

Possuindo uma expansão na forma:

[code language="cpp"]
axpy(1.0, axpy(1.0, axpy(1.0, 5.0, 4.0), 3.0), 2.0);
[/code]

Note que nesta implementação o polinômio de maior grau está a direita (último argumento). Mesmo sendo definido em termos de recursão, a implementação quando compilada em modo otimizado, eliminará as chamadas recursivas tornando tudo uma sequência inline, conforme demonstrado nas expansões anteriores. Dependendo da "agressividade" do otimizador uma expansão similar ao exemplo anterior se transforma em apenas uma única linha de código assembly:



Referências:

http://en.cppreference.com/w/cpp/language/variadic_arguments

http://en.cppreference.com/w/cpp/language/parameter_pack

Fonte:

https://github.com/SimplyCpp/examples/blob/master/horner_method_and_variadic/horner_method_program.cpp