"Potenciar" listas

[Luis Rodrigo Gallardo Cruz]

On Fri, Oct 14, 2005 at 03:53:37PM -0500, ZLAPPER wrote:
> Hola amigos,
> les escribo porque he estado pensando mucho en este problema y no se me ha
> ocurrido un algoritmo para la funcion que necesito hacer.
> La idea es hacer una funcion, la cual:
> Recibe 2 listas y cada una representa un numero entero (por ejemplo [2,3]
> representa el numero 23)
> Retorne una lista que represente el resultado numerico
>  A ver si me hago entender:
> Si hicieramos el llamado: potenciarlistas([2,5],[1,2])
> Retornaría: [5,9,6,0,4,6,4,4,7,7,5,3,9,0,6,2,5]

¿Te importa mucho la velocidad?

Si no:

Haz una función decrementa(l) (usa sumar con -1) y una esCero(l)

potenciar (a, b):
	resultado = [1]

	while !esCero(b):
		resultado = multiplicar(resultado, a)
		decrementa(b)

	return resultado


Si quieres mas velocidad, usa esta misma idea, pero en vez de decrementar
en uno el exponente partelo a la mitad en cada paso, y en vez de multiplicar
(resultado * a) haces (a*a). Hay varios detalles que cuidar aquí, como el que
hacer cuando el exponente es impar y se puede optimizar aún más, dividiendo
el exponente no entre 2, sino entre la potencia de 2 más grande posible.

Inspirate en la multiplicación Karatsuba:
http://mathworld.wolfram.com/KaratsubaMultiplication.html

pero dónde esa dice 'multiplicador' tú usa 'exponente' y dónde esa dice 'suma'
tú dí 'multiplica'.

-- 
Rodrigo Gallardo