abr 24, 2010

Enviado por en Algoritmos, Programacion

Potencias y series de potencias a un gran entero

Como habré hecho notar en la solución para el problema anterior, la solución conlleva elevar una matriz a la N y tomando en cuenta que para multiplicar un par de matrices se requeriría O(L^3) multiplicaciones escalares esto daría un total de O(L^3N) operaciones, lo cual podemos disminuir a O(L^3\log N). Veamos cómo se hace.

También se aplica a potencia de escalares, por lo que vamos a tomar como ejemplo el resultado 4^{1234}. Esto es igual a 4^{617}4^{617}, entonces si calculamos 4^{617} y lo multiplicamos por si mismo nos da 4^{1234} por lo que reducimos de unas 617 operaciones a una sola. Y de la misma forma podemos obtener 4^{617}=4^{308}4^{308}4 ya que el exponente no es par, seguimos así hasta encontrar el caso base con el exponente cero, donde 4^0=1. Se podría aplicar el algoritmo recursivo siguiente,

template <typename _Ty>
_Ty power(const _Ty & x, unsigned int p) {
	if (p == 0) return Identity<_Ty>();	// 1 para _Ty = int.

	// notar que C/C++ omite los decimales en una división.
	_Ty y = power(x, p / 2);
	if (p % 2 == 1)
		return y * y * x;
	else
		return y * y;
}

Lo cual disminuye las 1233 multiplicaciones en un número alrededor de \log_2 1234\approx 10, particularmente 16, multiplicaciones.

Una idea similar se puede usar para calcular series de este tipo:

\displaystyle \sum_{i=1}^n x^i=x^0+x^1+x^2+\dots+x^n

Otro ejemplo con n relativamente pequeño para que se aprecie mejor, calcular \sum_{i=0}^9 x^i. Tenemos que,

\displaystyle \sum_{i=1}^9 x^i=x^0+x^1+x^2+x^3+x^4+x^5+x^6+x^7+x^8+x^9

Lo cual es igual a,

\displaystyle \sum_{i=1}^9 x^i=(x^0+x^1+x^2+x^3+x^4)(x^0+x^5)=(x^0+x^5)\sum_{i=0}^4 x^i

Y seguimos,

\displaystyle \sum_{i=0}^4 x^i=x^0+x^1+x^2+x^3+x^4=(x^0+x^1)(x^0+x^2)+x^4=x^4+(x^0+x^2)\sum_{i=0}^1 x^i \displaystyle \sum_{i=0}^1 x^i=x^0+x^1=(x^0)(x^0+x^1)=(x^0+x^1)\sum_{i=0}^0 x^i

Y llegamos al caso base con n=0. En algoritmo:

template &lt;typename _Ty&gt;
_Ty serie(const _Ty & x, unsigned int p) {
	if (p == 0) return Identity&lt;_Ty&gt;();

	_Ty t = power(x, (p + 1) / 2);
	_Ty y = serie(x, (p - 1) / 2) * (Identity<_Ty>() + t);
	if (p % 2 == 1)
		return y;
	else
		return y + t * t;
}

En base al algoritmo anterior, al calcular \sum_{i=0}^9 x^i se producen 4 sumas y 14 multiplicaciones. Con \sum_{i=0}^{1234} 4^i tenemos 15 sumas y 98 multiplicaciones.

    Posts Relacionados

    Dejar una respuesta

    Debes ser Alojarse para enviar un comentario.